SP19722 MTETRA - Modular Tetration

在数学中，加法、乘法和幂运算这三种基础运算可以自然地拓展为一系列超运算。以下是几个例子： ``` 3×7 = 3 + 3 + 3 + 3 + 3 + 3 + 3 ; 这里有 7 个 "3" 3^7 = 3 × 3 × 3 × 3 × 3 × 3 × 3 ; 这里有 7 个 "3" 3^^7 = (3^(3^(3^(3^(3^(3^3)))))) ; 这里有 7 个 "3" ``` 为了将运算进一步拓展到幂运算以外，Knuth 定义了一种“双箭头”运算符来表示迭代幂运算，也称为 tetration。这种运算能够产生非常大的数。因此本题的任务是计算迭代幂的模值。对于所有 $X$，定义 $X^0=1$，因为这是一个空乘积。同样地，$X\text{^^}0=1$。

输入的第一行为整数 $T$，表示测试用例的数量。在接下来的 $T$ 行中，每行包含三个整数 $X$、$N$ 和 $M$。

对每个测试用例，输出 $X\text{^^}N \bmod M$ 的结果。

$$1 \le T \le 100, \quad 1 \le X, N, M \le 10^9$$ **本翻译由 AI 自动生成**