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
2022-02-02 15:56:29
Start with dp then work towards a O(log N) solution.
Beware of overflows when multiplying large integers under large modulo.

More testcases:
5
592518631964567589 771059296515615347 313612264251980191
76472931880652042 556284273596909868 466440516009973321
930297518000893889 348535884259226821 553490522358260865
881094902386814255 278285682416401469 992562278435321028
880068538282328714 410607107873246529 715441549630381053
211344985222007752
329397219244798612
549883588437645645
450063361428842796
45332181734129121


Last edit: 2022-02-02 15:57:07
2021-12-11 00:33:36 David
Awesome problem!
@ashutosh1598 below really means "Do NOT forget mod for n = 1".
2018-08-14 16:13:20 Grzegorz Spryszyñski
@vaibhav2303, see the description. Only two (or more) zeros are prohibited. Separate 0 is fine
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.
2018-03-04 04:31:33
I'm confused... what if k>10?
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
2017-10-20 13:21:09 Grzegorz Spryszyñski
@mahilewets. I don't know that problem or contest.
The idea of this problem was taken from the completely different source
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
2016-07-27 12:41:35 Grzegorz Spryszyñski
26-07-2016 Test cases change and rejudge
2016-07-11 13:50:32 Grzegorz Spryszyñski
@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.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.