#[2563].「SDOI2018」反回文串

内存限制：512 MB 时间限制：2000 ms

「回文串什么的最讨厌了……」

小 Q 讨厌任何形式的回文串：

如果一个字符串从左往右读和从右往左读是一样的，那么小 Q 讨厌它；例如 aa 和 aba 。
对于一个字符串来说，若将某个前缀子串移除并拼接到字符串的尾部，能得到一个小 Q 讨厌的字符串，那么小 Q 也会讨厌原来的这个字符串；例如 aab 和 baa 。

现在问题来了，如果任意字符串只可以由 $k$ 种已知的字符组成（也就是说字符集的大小为 $k$），那么长度为 $n$ 的所有字符串里，有多少字符串是小 Q 讨厌的？

答案可能很大，你只需要给出答案对 $p$ 取模后的值。

第一行包含一个正整数 $T$，表示有 $T$ 组测试数据。

接下来 $T$ 行，每行描述一组测试数据，包含三个正整数 $n$, $k$ 和 $p$。

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

对于 $30\%$ 的数据，有 $1 \leq n \leq 10^{10}$。
对于 $60\%$ 的数据，有 $1 \leq n \leq 10^{14}$。
对于 $100\%$ 的数据，有 $1 \leq T \leq 10, 1 \leq n \leq 10^{18}, 1 \leq k \leq n, 10^9 \leq p \leq 2^{30}$。

样例输入 1

10
1 1 1000000001
2 2 1000000003
3 2 1000000005
3 3 1000000007
4 2 1000000009
4 3 1000000011
4 4 1000000013
5 5 1000000015
7 7 1000000017
9 9 1000000019

样例输出 1

样例输入 2

10
8821612800 758922381 1073365919
8380532160 166822173 1001828119
9311702400 7367823578 1015387267
6983776800 1646145481 1030885259
6692786100 1953515781 1073365919
7138971840 2649942813 1001828119
6469693230 2585876408 1015387267
8031343320 1646145481 1030885259
9995200351 645412247 1030328983
9302162851 1649517328 1053299347

样例输出 2

2563 「SDOI2018」反回文串

题目描述

输入格式

输出格式

样例 1

样例 2

数据范围与提示

样例

样例输入 1

样例输出 1

样例输入 2

样例输出 2