题目描述

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

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

1. 如果一个字符串从左往右读和从右往左读是一样的，那么小 Q 讨厌它；例如 aa 和 aba 。

2. 对于一个字符串来说，若将某个前缀子串移除并拼接到字符串的尾部，能得到一个小 Q 讨厌的字符串，那么小 Q 也会讨厌原来的这个字符串；例如 aab 和 baa 。

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

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

输入格式

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

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

输出格式

对于每组测试数据，输出一行，包含一个整数，表示答案对 $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

数据范围与提示

对于 $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}$。