P4607 [SDOI2018] Anti-Palindromic String

“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$.

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$.

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

- 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