不明原因过了样例爆炸求掉

#include <bits/stdc++.h>
using namespace std;

long long x[3][3],y[3][3],t[3][3];
long long mod,k,n;
void jzksm(){
	x[1][1]=0,x[1][2]=mod-1,x[2][1]=1,x[2][2]=k%mod;
	y[1][1]=y[2][2]=1;
	while(n){
		if (n%2){
			memset(t,0,sizeof(t));
			for(int i=1;i<=2;i++){
				for(int j=1;j<=2;j++){
					for(int k=1;k<=2;k++){
						t[i][j]+=(x[i][k]*y[k][j]);
						t[i][j]=(t[i][j]+mod)%mod;
					}
				}
			}
			for(int i=1;i<=2;i++){
				for(int j=1;j<=2;j++){
					y[i][j]=t[i][j];
				}
			}
		}
		memset(t,0,sizeof(t));
		for(int i=1;i<=2;i++){
			for(int j=1;j<=2;j++){
				for(int k=1;k<=2;k++){
					t[i][j]+=(x[i][k]*x[k][j]);
					t[i][j]=(t[i][j]+mod)%mod;
				}
			}
		}
		for(int i=1;i<=2;i++){
			for(int j=1;j<=2;j++){
				x[i][j]=t[i][j];
			}
		}	
		n/=2;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin>>mod>>k>>n;
	if (n==0){
		cout<<0<<endl;
		return 0;
	}
	n--;
	jzksm();
	long long p[2],r[2];
	p[1]=k;
	p[2]=(k*k-2);
	p[1]=(p[1]+mod)%mod;
	p[2]=(p[2]+mod)%mod;
	r[1]=r[2]=0;
	for(int i=1;i<=2;i++){
		for(int k=1;k<=2;k++){
			r[i]=(r[i]+p[k]*y[k][i]%mod+mod)%mod; 
		}
	}
	cout<<r[1]%mod<<endl;
	return 0;
}