KBASEEN - Acceptable numbers

no tags 

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

hide comments
Grzegorz Spryszyñski: 2018-08-14 16:13:20

@vaibhav2303, see the description. Only two (or more) zeros are prohibited. Separate 0 is fine

vaibhav2303: 2018-08-08 17:53:54

Problem statement and/or the test cases is incorrect because when N=1, 0 is being considered as a accepted number which is not the case for other Ns.

do_mi: 2018-03-04 04:31:33

I'm confused... what if k>10?

ashutosh1598: 2017-12-18 17:34:54

What is the answer when n==1? Do we consider 0 or not?
Edit: forgot to do %m when n==1.

Last edit: 2017-12-18 17:40:32
Grzegorz Spryszyñski: 2017-10-20 13:21:09

@mahilewets. I don't know that problem or contest.
The idea of this problem was taken from the completely different source

mahilewets: 2017-09-16 07:32:59

Problem copied from Timus K-based numbers version 3

Edit: partially copied, concept is the same, statement is improved.

Last edit: 2017-09-16 08:34:51
Grzegorz Spryszyñski: 2016-07-27 12:41:35

26-07-2016 Test cases change and rejudge

Grzegorz Spryszyñski: 2016-07-11 13:50:32

@Ketan
You give wrong answers for low cases. And there is something else. I'll investigate it later.
Avoiding overflow is one of the problem in this task.

Ketan Chandak: 2016-07-10 13:10:29

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
Alex Anderson: 2015-10-10 08:06:40

Would have been a little trickier if it he accepted only those with "00".


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