快速幂板子。

#include <cstdio>

#define ll long long

namespace Cirno {
    ll FastPower(ll base, ll power, ll mod) {
        ll result = 1;
        while (power) {
            if (power & 1) result = result * base % mod;
            power = power >> 1;
            base = base * base % mod;
        }
        return result;
    }
}
ll m;
ll a, b, p;

int main() {
    scanf("%lld", &m);
    while (m--) {
        scanf("%lld %lld %lld", &a, &b, &p);
        printf("%lld\n", Cirno::FastPower(a, b, p));
    }
    return 0;
}