矩阵板子题

#include<bits/stdc++.h>
#define int long long
#define db double
using namespace std;
int n,MOD,p,q,a1,a2;
struct mat{
	int m[3][3];
}ans,base;
mat operator * (const mat a,const mat b){
	mat c;
	memset(c.m,0,sizeof c.m);
	for(int i = 1;i <= 2;i++){
		for(int j = 1;j <= 2;j++){
			for(int l = 1;l <= 2;l++) c.m[i][j] = (c.m[i][j] + a.m[i][l] * b.m[l][j]) % MOD;
		}
	}
	return c;
}
mat fp(int p){
	while(p){
		if(p & 1) ans = ans * base;
		base = base * base;
		p >>= 1;
	}
	return ans;
}
signed main(){
	cin >> p >> q >> a1 >> a2 >> n >> MOD;
	ans.m[1][1] = a2,ans.m[1][2] = a1;
	base.m[1][1] = p,base.m[2][1] = q,base.m[1][2] = 1;
	if(n == 1){
		cout << a1;
		return 0;
	}
	if(n == 2){
		cout << a2;
		return 0;
	}
	ans = fp(n - 2);
	cout << ans.m[1][1] % MOD;
    return 0;
}