Description

“I really hate palindromic strings...”

Xiao $Q$ hates any form of palindromic string:

• If a string reads the same from left to right and from right to left, then Xiao $Q$ hates it; for example, $aa$ and $aba$.

• For a string, if by removing some prefix substring and appending it to the end of the string you can obtain a string that Xiao $Q$ hates, then Xiao $Q$ also hates the original string; for example, $aab$ and $baa$.

Now the question is: if any string may only be formed from $k$ known characters, among all strings of length $n$, how many strings are hated by Xiao $Q$?

The answer can be large. You only need to output the answer modulo $p$.

Input Format

The first line contains a positive integer $T$, indicating that there are $T$ test cases. The next $T$ lines each describe a test case, containing three positive integers $n$, $k$, and $p$.

Output Format

For each test case, output one line containing an integer, which is the answer modulo $p$.

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
8
21
6
15
28
605
16765
530937

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

896784901
911577797
674524325
392648220
646549222
879297585
384496639
889650008
957785169
413147483

Hint

• For $30\%$ of the testdata, $1 \le n \le 10^{10}$.

• For $60\%$ of the testdata, $1 \le n \le 10^{14}$.

• For $100\%$ of the testdata, $1 \le T \le 10$, $1 \le n \le 10^{18}$, $1 \le k \le n$, $10^9 \le p \le 2^{30}$.

Translated by ChatGPT 5