快速幂模板题。
注意范围很大，可能会超过ull所以在加一个龟速乘防止爆掉

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll mul(ll,ll,ll);
///快速幂模板
ll power(ll a,ll b,ll p)
{
    ll ans=1;
    for(; b; b>>=1)
    {
        if(b&1)
            ans=mul(ans,a,p);
        a=mul(a,a,p);
    }
    return ans;
}

///快速乘模板
ll mul(ll a,ll b,ll p)
{
    ll ans=0;
    for(; b; b>>=1)
    {
        if(b&1)
            ans=(ans+a)%p;
        a=a*2%p;
    }
    return ans;
}

int main()
{
    int t;
    cin>>t;
    while(t--){
    ll a,b,p;
    while(~scanf("%llu%llu%llu",&a,&b,&p))
        printf("%llu\n",power(a%p,b,p));}
    return 0;
}