FUNMODSEQ - Funny Modular Sequence

Lets define a funny modular sequence as a sequence such that:

  • a1 x a2 = 1 (mod p)
  • a2 x a3 = 1 (mod p)
  • ...
  • an-1 x an = 1 (mod p)

Also, a1, a2, a3 ... an must be less than p and greater than or equal to 0. Given one element, a1, find the sum of the entire funny modular sequence of length n. If, for any ai, where i>=1, there exists no ai+1 such that aix ai+1 = 1 (mod p), output -1.

Note: p is not necessarily prime.

Input

The first line contains T, the number of test cases. T lines follow, each containing a1, p, and n.

Output

For each test case, output one line, the required sum.

Constraints

1<=T<=105
1<=a1<=105
1<=n<=109
a1 < p <=109

Sample

Input:
2
2 3 2
3 7 2

Output:
4
8

Explanation

In the first test case, the funny modular sequence will be 2, 2, which has a sum of 4.

In the second test case, it will be 3, 5, which has a sum of 8.


Added by:Piyush Kumar
Date:2016-06-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Hackerearth Monthly Contest

hide comments
2019-03-20 04:46:33
Testcases are uncompromising, which is a shame as I've had a blast exploring the patterns here and building and optimizing a solution based on my findings, on and off for 2 days, only to find out it has to TLE. Finally had to turn to wikipedia and after 15mins a played out NT trick did the job. And the fun was over. Disappointed.
2016-09-13 00:44:40 :D
It must be added that a{i+1} in the condition for -1 can be out of the sequence.
2016-06-27 13:58:17 TKD
sequence in increasing order??

can sequence be 535353 for p=7

Last edit: 2016-06-27 13:58:46
2016-06-25 13:10:06 Min_25
[ Note ]
Some input file does not end with '\n'.

Last edit: 2016-06-25 13:39:48
2016-06-25 02:25:38
@Piyush: could you please check submission 17172921 ? Shouldn't time limit be increased for Java programs ? I can see one Python submission in 1.84 sec whereas limit on this page is 1 sec Thank you for looking

Re: The time 1.84 sec tells you the total time it took to run all test files whereas the TL mentioned on the description is for one test file. The TL for Java looks tight but I think a decent code can pass. There are a lot of optimizations you can make in your code. Best of Luck!

Last edit: 2016-06-25 09:29:36
2016-06-22 22:08:06 geeta
should the sequence be in increasing order?? plz give a test case for which output is -1!!

Re: If it helps=> 5706 24466 28146

Last edit: 2016-06-23 06:22:17
2016-06-17 17:10:35
Nice Question :) !!
1WA for Overlook
AC :)
2016-06-17 13:30:20 wisfaq
If you ask me to calculate something mod p it is very deceptive to use p's that aren't prime.

Re: Although, the problem statement doesn't give any reason to believe that p is prime, I will add a note.

Last edit: 2016-06-17 14:17:40
2016-06-17 12:09:02 lt
Awesome problem! Ac in one go. :)

Re: Congrats! Glad you liked it :)

Last edit: 2016-06-17 12:17:31
2016-06-17 07:26:57
@Piyush i think the sample input given in the problem must be

2
2 3 2
3 7 2

Re: Thanks! Updated!

Last edit: 2016-06-17 07:28:30
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.