[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

样例输出

#5330. [Sdoi2018]反回文串

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示