KBASEEN - Acceptable numbers

Sitting in front of computer has made Byteasar's eye sight very bad. He has to wear glasses to fix it. But Byteasar doesn't like it. So everything associated with glasses is disliked by him.

Byteasar has been working with different numeral systems. When listing numbers, he knows exactly which of them aren't liked by him. Of course these numbers have two zeros next to each other. Now he is wondering: how many n-digits numbers in k-base numeral system he is able to accept. There could be many of them so print the result modulo m.

Input

First there is a t (0 < t < 1001), number of test cases.
Each test contains three number: n (0 < n < 1018), k (1 < k < 1018) and m (1 < m < 1018). n is a length of the number, k - digits quantity in given numeral system.

Output

For each test print answer divided modulo m.

Example

Input:
2
4 2 100
3 10 10000

Output: 5
891

Added by:Grzegorz Spryszyński
Date:2015-09-19
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2016-07-10 13:10:29 Ketan Chandak
Given the constraints, even long long will give WA. Why keep constraints like that?
Edit: I did submit in Python to avoid overflow. Still getting WA. Can you please check?

Last edit: 2016-07-11 05:51:49
2015-10-10 08:06:40 Alex Anderson
Would have been a little trickier if it he accepted only those with "00".
2015-10-02 11:30:03 Grzegorz Spryszyñski
Thanks. You are not the first one who made this mistake.
And yes, leading zeros don't count.

Last edit: 2015-10-02 13:51:50
2015-09-30 17:04:02
Okay, for test case 1 (4 2 100)
We have combinations for 4-digits in base-2:
0000
0001
0010
0011
0100
0101 (accepted)
0110 (accepted)
0111 (accepted)
1000
1001
1010 (accepted)
1011 (accepted)
1100
1101 (accepted)
1110 (accepted)
1111 (accepted)

So 8 numbers are accepted..
Hence 8%100 = 8. So output should be 8, right?
How come it's 5 ? Or, am I wrong somewhere??

Edit:
I get it now.. By n-digit number, you mean that the n'th digit must not be 0.. So,
1000
1001
1010 (accepted)
1011 (accepted)
1100
1101 (accepted)
1110 (accepted)
1111 (accepted)
Hence 5%100=5 .
I don't know if this is a noobic mistake, or a common misunderstanding by others too..
Anyway, good problem :)

Last edit: 2015-09-30 17:12:51
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.