大体思路就是求循环节+快速幂，能过样例，但提交 WA

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int a,b;
int p,T,f[100200];
int qpow(int a,int b)
{
	int ret=1,base=a%p;
	while(b)
	{
		if(b&1)ret=(ret*base)%p;
		base=base*base%p;
		b>>=1;
	}
	return ret;
}
signed main()
{
	scanf("%llu",&T);
	while(T--)
	{
		scanf("%llu%llu%llu",&a,&b,&p);
		f[1]=f[2]=1;
		for(int i=3;i<=p*p;i++)
		{
			f[i]=(f[i-1]+f[i-2])%p;
			if(f[i]==1&&f[i-1]==1)
			{
				p=i-2;
				break;
			}
		}
		printf("%llu\n",f[qpow(a,b)]);
	}
	return 0;
}