# Kth Root(Mod)

AC一覧

## Problem Statement問題文

Each test case consists of $T$ cases.

Given $K, Y, P(P: \textrm{prime})$.

Print any $X$ s.t. $X^K \equiv Y \pmod{P}$, or $-1$ if there is no such $X$.

We note that $0^0\equiv 1 \pmod{P}$ in this problem.

この問題は $T$ ケース与えられます。

$K, Y, P(P: \textrm{prime})$ が与えられます。

$X^K \equiv Y \pmod{P}$ なる $X$ を1つ求めてください。

ただし $0^0\equiv 1 \pmod{P}$ とします。

## Constraints制約

• $1 \leq T \leq 5{,}000$
• $0 \leq K \leq 10^{9}$
• $2 \leq P \leq 10^{9}$
• $0 \leq Y < P$
• $P$ is prime
$P$ は素数

## Input入力

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


## Output出力

For each line, print $X$ or $-1$.

## Sampleサンプル

### # 1

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

-1
-1
1
10
-1


Timelimit: 5 secs

Before submitting, please confirm terms and conditions