题目描述
Problem Description
"Palindrome strings are the most annoying..."
Little $Q$ dislikes any form of palindrome strings:
-
If a string reads the same forwards and backwards, then Little $Q$ dislikes it; for example, $aa$ and $aba$.
-
For a string, if removing a prefix substring and appending it to the end results in a string that Little $Q$ dislikes, then Little $Q$ also dislikes the original string; for example, $aab$ and $baa$.
The question is, if a string can only be composed of $k$ known characters, how many strings of length $n$ does Little $Q$ dislike?
The answer might be very large, so you only need to provide the answer modulo $p$.
Input Format
The first line contains a positive integer $T$, indicating the number of test cases.
The next $T$ lines, each describing a test case, contain 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$.
Sample Input and Output
Input Sample #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
Output Sample #1
1
2
8
21
6
15
28
605
16765
530937
Input Sample #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
Output Sample #2
896784901
911577797
674524325
392648220
646549222
879297585
384496639
889650008
957785169
413147483
Notes
-
For $30\%$ of the data, $1 ≤ n ≤ 10^{10}$.
-
For $60\%$ of the data, $1 ≤ n ≤ 10^{14}$.
-
For $100\%$ of the data, $1 ≤ T ≤ 10, 1 ≤ n ≤ 10^{18}, 1 ≤ k ≤ n, 10^9 ≤ p ≤ 2^{30}$.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分