RT，本人已经做了快一个月了，还是没调出来。

Code:

#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
ll MOD;
map<ll,ll> mp;
map<ll,ll>::iterator it;
ll a[40005],b[14005],r,fib[55],tsm;
void shai(int n){
	a[0]=a[1]=1;
	for(int i=2;i<=n;i++){
		if(!a[i]){
			b[++r]=i;
		}
		for(int j=1;j<=r&&i*b[j]<=n;j++){
			a[i*b[j]]=1;
			if(i%b[j]==0){
				break;
			}
		}
	}
}
inline ll read(){
    ll x(0),f(1);
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}
ll eular(ll x){
	ll ans=x;
	for(int i=1;b[i]*b[i]<=x&&i<=r;i++){
		if(x%b[i]==0){
			ans=ans/b[i]*(b[i]-1);
			while(x%b[i]==0){
				x/=b[i];
			}
		}
	}
	if(x>1){
		ans=ans/x*(x-1);
	}
	return ans;
}
ll dg(ll n){
	if(n<=2){
		return 1ll;
	}
	it=mp.find(n);
	if(it!=mp.end()){
		return mp[n];
	}
	if(!(n&1)){
		return mp[n]=((dg(n/2-1)*2+dg(n>>1))%MOD*dg(n>>1))%MOD;
	}
	return mp[n]=(dg(n/2+1)*dg(n/2+1)%MOD+MOD+dg(n>>1)*dg(n>>1)%MOD)%MOD;
}
ll fre(ll x,ll eed){
	int cur;
	cur=lower_bound(fib+1,fib+tsm+1,eed)-fib;
	if(cur!=1){
		cur--;
	}
	return x<cur;
}
ll pre(ll x,ll s,ll k){
	ll ans=1;
	while(s){
		if(s&1){
			ans=(ans*x)%k;
		}
		x=(x*x)%k;
		s>>=1;
	}
	return ans;
}
int main(){
	int t,a,b,p,n,cnt=0;
	ll eul,tx,ty;
	t=read();
	shai(40000);
	fib[1]=1;fib[2]=1;
	for(int i=3;i<=1e5;i++){
		fib[i]=fib[i-1]+fib[i-2];
		if(fib[i]>=1e9){
			tsm=i-1;
			break;
		}
	} 
	while(t--){
		cnt++;
		a=read(),b=read(),p=read(),n=read();
		eul=eular(p);
		MOD=eul;
		if(eul==1){
			printf("Case #");
			write(cnt);
			printf(": ");
			write(0);
			printf("\n");
			continue;
		}
		if(__gcd(a,p)==1){
			tx=pre(a,dg(n-2),p);
			ty=pre(b,dg(n-1),p);
		}
		else{
			tx=pre(a,dg(n-2)+eul*fre(n-2,eul),p);
			ty=pre(a,dg(n-1)+eul*fre(n-1,eul),p);
		}
		mp.clear();
		printf("Case #");
		write(cnt);
		printf(": ");
		write((tx*ty)%p);
		printf("\n");
	}
	return 0;
}