模意义下开 k 次方

【题目描述】

每个测试用例由 $T$ 组数据组成。

给定 $K, Y, P(P: \textrm{质数})$。

输出任意满足 $X^K \equiv Y \pmod{P}$ 的 $X$；如果不存在这样的 $X$，则输出 $-1$。

注意，在本题中规定 $0^0\equiv 1 \pmod{P}$。

【输入】

$T$
$K_0$ $Y_0$ $P_0$
$K_1$ $Y_1$ $P_1$
$\vdots$
$K_{T-1}$ $Y_{T-1}$ $P_{T-1}$

【输出】

对于每一行，输出 $X$ 或 $-1$。

【输入样例】

5
0 10 11
10 9 11
1 1 2
5 4 13
0 8 11

【输出样例】

-1
-1
1
10
-1

【数据范围】

• $1 \leq T \leq 5000$
• $0 \leq K \leq 1000000000$
• $2 \leq P \leq 1000000000$
• $0 \leq Y < P$
• $P$ 是质数。

【来源】

Library Checker（yosupo06） kth_root_mod

本题为 special judge（输出任意合法解），暂不可本地评测。