GHALIBC - GHALIBS CHALLENGE

no tags 

"har ek baat pe kehte ho tum ke 'too kya hai?'
tumheen kaho ke yeh andaaz-e-guftgoo kya hai?"

Ghalib was a great poet and was very higly regarded by the emperor. Some of the nobles did not like this, so concocted a plan to reduce his influence on the emperor. They gave him a challenge, he could be given n bags of marbles. The first bag has 1 marble, second bag has 2 marbles and so on. Each of the marble has a unique radius between 1 and i, where i is the number of the bag. Ghalib has to tell the number of ways arranging these marbles. (The marbles in each of the bag have to be arranged separately and the number of ways summed up for all the bags).

Ghalib complained to the king that this task is too difficult. So the king tried to help him a bit. (n+1) will only be divisible by a single prime - p (i.e. (n+1)=p^a) and he has to only find ways of rearranging those bags of marbles whose size is equal to r mod(p-1) and (p+1)/2<=r<=p-1. Also he doesnt need to count any arrangement of marbles containing a subsequence of 3 marbles with increasing length.
Ghalib still finds this task too difficult and is asking for your help. Since the answer can be very big, output the remainder when the answer is divided by p*p.

Input

1<=t<=10 :-  the number of test cases

followed by t llines of

r p a :- as given in the question

(p+1)/2<=r<=p-1

5<=p<=1000

1<=a<=10^8

Output

A single number representing the required answer

Example

Input:
2
5 7 2
5 7 1 Output:
42
42

hide comments
[Rampage] Blue.Mary: 2016-02-22 04:21:29

The sample is very helpful (in guessing the meaning & the algorithm) :-)

Min_25: 2014-03-24 13:42:57

In this problem, r = p - 1 (mod p - 1) is the same as r = 0 (mod p - 1).

Francky: 2013-03-22 16:36:25

PSYCO is back, and this good problem is now possible in python ;-)
edit : In fact, on Cube cluster, I think now psyco was always available... sorry, the news is irrelevant. We're still waiting for pypy, the future for python here imho.

Last edit: 2013-03-23 10:28:21
Francky: 2013-03-14 19:49:09

Please explain the second case, my understanding of the problem give me a different answer.
(edit) OK, I can find 42 for the second case, I had a misunderstood with "subsequence".
(edit2) OK, now I understand well the first case too.
r=p-1 is possible, and it makes things harder, cool...
edit Harghh, finally AC. Silly debug. This problem is not easy to understand, and after that not easy to solve.

Last edit: 2013-03-17 14:32:14
3qu@t!0n: 2013-03-14 16:28:12

what's the meaning of this line--
"bags of marbles whose size is equal to r mod(p-1) and (p+1)/2<=r<=p-1."
when (p-1)>=r then r mod(p-1) will be always 'r' or '0';

please make description clear......

3qu@t!0n: 2013-03-14 15:48:28

lines written in sttmnt..

http://www.youtube.com/watch?v=6x_4TyYUT7k&list=WLwllfOSeNlJClDYnK19TJ1aA9UWz9xnJj

[Rampage] Blue.Mary: 2013-03-05 13:36:38

[Deleted after AC.]

Last edit: 2016-02-22 04:21:50
praveen123: 2013-03-05 13:36:38

I was really pleased to see mention of great urdu shayar Mirza Ghalib ji.
For more interested people , I am posting a link to youtube which has ghazals of Ghalib sung by Jagjit singh ji.
http://www.youtube.com/watch?v=gECJFQftAzo

Last edit: 2013-03-04 17:33:34

Added by:TouristGuide
Date:2013-02-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Bytecode 2013