#5330. [Sdoi2018]反回文串

内存限制:512 MiB 时间限制:66 Sec

题目描述

“回文串什么的最讨厌了……”
小Q讨厌任何形式的回文串:
(1)如果一个字符串从左往右读和从右往左读是一样的,那么小Q讨厌它;例如aa和aba
(2)对于一个字符串来说,若将某个前缀子串移除并拼接到字符串的尾部,能得到一个小Q讨厌的字符串,
那么小Q也会讨厌原来的这个字符串;例如aab和baa。
现在问题来了,如果任意字符串只可以由k种已知的字符组成(也就是说字符集的大小为k),
那么长度为n的所有字符串里,有多少字符串是小Q讨厌的?
答案可能很大,你只需要给出答案对p取模后的值。

输入格式

第一行包含一个正整数T,表示有T组测试数据。
接下来T行,每行描述一组测试数据,包含三个正整数n,k和p。
1<=T<=10,1<=n<=10^18,1<=k<=n,10^9<=p<=2^30

输出格式

对于每组测试数据,输出一行,包含一个整数,表示答案对p取模的值。

样例

样例输入


			
10
9311702400 2063322107 1032035101
9311702400 3847844404 1014424217
9311702400 6992683534 1067435323
9311702400 1356819643 1024817347
9311702400 6944668829 1042812553
9311702400 9162670852 1003177793
9311702400 6567188538 1062813337
9311702400 3910301217 1018910293
9311702400 2463242636 1018694167
9311702400 4797739673 1050709027

样例输出


			
618961590
28597316
1016219343
977847638
108994801
100559666
694084378
492868358
336126742
176095716

数据范围与提示