迭代幂次取模

【题目描述】

每个测试文件包含 $T$ 组数据。

给定 $A, B, M$，输出 ${A \uparrow \uparrow B} (\bmod M)$。

注意本题中规定 $0^0 = 1$。

【输入】

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

【输出】

对每组数据输出一行，表示 ${A \uparrow \uparrow B} (\bmod M)$。

【输入样例】

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

【输出样例2】

0
0
1
0
4
0
1
0
3
2

【数据范围】

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

【来源】

Library Checker（yosupo06） tetration_mod