迭代幂次取模 (Tetration Mod)

时间限制：10 秒

题目描述

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

给定 $A, B, M$。输出 $A \uparrow\uparrow B \pmod M$（即 $B$ 个 $A$ 的迭代幂次对 $M$ 取模）。

注意，$0^0 = 1$（至少在本题中如此约定）。

约束条件

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

输入

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 \pmod 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

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