8998: [yosupo] Number Theory - Tetration Mod
[Creator : ]
Description
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).
Given $A, B, M$. Print ${A \uparrow \uparrow B} (\bmod M)$.
We note that $0^0 = 1$ (at least in this problem).
Input
$T$
$A_0$ $B_0$ $M_0$
$A_1$ $B_1$ $M_1$
:
$A_{T-1}$ $B_{T-1}$ $M_{T-1}$
$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)$.
Constraints
$1 \leq T \leq 1000$
$0 \leq A, B \leq 10^9$
$1 \leq M \leq 10^9$
$0 \leq A, B \leq 10^9$
$1 \leq M \leq 10^9$
Sample 1 Input
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
Sample 1 Output
1
0
1
1
3
1
140
998121473
170
94527
Sample 2 Input
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
Sample 2 Output
0
0
1
0
4
0
1
0
3
2