//这题重点是要发现 f[i]%n会出现循环，然后找出他的循环节m取 a^b%m 即可 #include<iostream>#include<cstdio>#include<cstring>using namespace std;typedef  unsigned long long ull;ull f[1000009];int re[1009],t;int pow_mod(ull a,ull b,ull mod){    if(b==0) return 1;    ull tmp=pow_mod(a,b/2,mod);    tmp=tmp*tmp%mod;    if(b&1) tmp=a*tmp%mod;    return tmp;}int main(){    for(int i=2;i<=1000;i++){        ull pre=1,pree=0,now,mod=i;        for(int j=2;j<=1000000;j++){            now=(pre+pree)%mod;            if(now==1&&pre==0){                re[i]=j-1;                break;            }            pree=pre;pre=now;        }    }    f[0]=0;f[1]=1;    ull a,b;    int n;    scanf("%d",&t);    while(t--){        scanf("%llu%llu%d",&a,&b,&n);        if(n==1||a==0){            printf("0\n");            continue;        }        int p=pow_mod(a%re[n],b,re[n]);        //cout<<p<<endl;        for(int i=2;i<=p;i++)            f[i]=(f[i-1]+f[i-2])%n;        printf("%llu\n",f[p]);    }    return 0;}