题解 | 好多次方

注意到 $M={{10}^9+7}$ 是质数，且 $a\not\equiv0\mod M$ ，故可以使用费马小定理（ $a^{M-1}\equiv 1\mod M$ ），设 $b^c=d$ ，则 $a^d=a^{d\%\left(M-1\right)+\left\lfloor\frac d{M-1}\right\rfloor\left(M-1\right)}\equiv a^{d\%\left(M-1\right)}\mod M$ 。而 $b^c\%\left(M-1\right)$ 也可通过快速幂求出。算法需要两次快速幂，故时间复杂度为 $O\!\left(\log c+\log M\right)$ 。

import sys

MOD = 10 ** 9 + 7

sys.stdin.readline()
for line in sys.stdin:
    a, b, c = map(int, line.split())
    print(pow(a, pow(b, c, MOD - 1), MOD))