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 ndigits numbers in kbase 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 < 10^{18}), k (1 < k < 10^{18}) and m (1 < m < 10^{18}). 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:
20180814 16:13:20
@vaibhav2303, see the description. Only two (or more) zeros are prohibited. Separate 0 is fine 

vaibhav2303:
20180808 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:
20180304 04:31:33
I'm confused... what if k>10? 

ashutosh1598:
20171218 17:34:54
What is the answer when n==1? Do we consider 0 or not?


Grzegorz Spryszyñski:
20171020 13:21:09
@mahilewets. I don't know that problem or contest.


mahilewets:
20170916 07:32:59
Problem copied from Timus Kbased numbers version 3


Grzegorz Spryszyñski:
20160727 12:41:35
26072016 Test cases change and rejudge 

Grzegorz Spryszyñski:
20160711 13:50:32
@Ketan


Ketan Chandak:
20160710 13:10:29
Given the constraints, even long long will give WA. Why keep constraints like that?


Alex Anderson:
20151010 08:06:40
Would have been a little trickier if it he accepted only those with "00". 
Added by:  Grzegorz Spryszyński 
Date:  20150919 
Time limit:  1s2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 