P4607 [SDOI2018] 反回文串

“回文串什么的最讨厌了……” 小 $Q$ 讨厌任何形式的回文串： - 如果一个字符串从左往右读和从右往左读是一样的，那么小 $Q$ 讨厌它；例如 $aa$ 和 $aba$。 - 对于一个字符串来说，若将某个前缀子串移除并拼接到字符串的尾部，能得到一个小 $Q$ 讨厌的字符串，那么小 $Q$ 也会讨厌原来的这个字符串；例如 $aab$ 和 $baa$。 那么问题来了，如果任意字符串只可以由 $k$ 种已知的字符组成，那么长度为 $n$ 的所有字符串里，有多少字符串是小 $Q$ 讨厌的？ 答案可能很大，你只需要给出答案对 $p$ 取模的值。

无

无

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