# Tetration Mod

AC一覧

## Problem Statement問題文

Each test cases consist of $T$ cases.

Given $A, B, M$. Print ${A \uparrow \uparrow B} (\bmod M)$.

We note that $0^0 = 1$ (at least in this problem).

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

$A, B, M$ が与えられます。

${A \uparrow \uparrow B} (\bmod M)$ を求めてください。 なお、$0^0 = 1$ とします。

## Constraints制約

• $1 \leq T \leq 1000$
• $0 \leq A, B \leq 10^9$
• $1 \leq M \leq 10^9$

## Input入力

$T$
$A_0$ $B_0$ $M_0$
$A_1$ $B_1$ $M_1$
:
$A_{T-1}$ $B_{T-1}$ $M_{T-1}$


## Output出力

For each line, print ${A \uparrow \uparrow B} (\bmod M)$.

## Sampleサンプル

### # 1

10
0 0 10
0 1 10
1 0 10
1 1 10
7 3 10
1 3 33
998 244 353
998244353 1333 1000000000
998244353 998244353 1333
1000000000 1000000000 133333

1
0
1
1
3
1
140
998121473
170
94527


### # 2

10
2 2 1
2 2 2
2 2 3
2 2 4
2 2 5
3 3 1
3 3 2
3 3 3
3 3 4
3 3 5

0
0
1
0
4
0
1
0
3
2


Timelimit: 10 secs

Before submitting, please confirm terms and conditions