题解 | 好多次方

import java.util.Scanner;

public class Main {
    static final int P = 1_000_000_007;
    static final int PHI_P = 1_000_000_006;

    // 欧拉函数 (模板)
    public static long phi(long n) {
        long result = n;
        for (long i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                while (n % i == 0)
                    n /= i;
                result -= result / i;
            }
        }
        if (n > 1)
            result -= result / n;
        return result;
    }

    public static long power(long base, long exp, long mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }

    public static long powerCapped(long base, long exp, long cap) {
        long res = 1;
        while (exp > 0) {
            if (exp % 2 == 1) {
                if (base != 0 && res > cap / base) return cap;
                res *= base;
                if (res >= cap) return cap;
            }
            if (exp > 1) {
                if (base != 0 && base > cap / base) return cap;
                base *= base;
                if (base >= cap) return cap;
            }
            exp /= 2;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            long a = sc.nextLong();
            long b = sc.nextLong();
            long c = sc.nextLong();

            long exp;
            long bcCapped = powerCapped(b, c, PHI_P);
            
            if (bcCapped < PHI_P) {
                exp = bcCapped;
            } else {
                exp = power(b, c, PHI_P) + PHI_P;
            }
            
            System.out.println(power(a, exp, P));
        }
    }
}