已过
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cctype>
#define int long long
#define N 105
#define re register
using namespace std;
int n,q,p,a1,a2,mod;
struct map{
long long m[N][N];
map(){memset(m,0,sizeof m);}
inline void csh(){for(int i=1;i<=3;++i)m[i][i]=1;}
}a,b;
map chen(map x,map y){
map z;
for(int k=1;k<=3;++k)
for(int i=1;i<=3;++i)
for(int j=1;j<=3;++j)
z.m[i][j]=(z.m[i][j]+x.m[i][k]*y.m[k][j]%mod)%mod;
return z;
}
long long k;
signed main(){
scanf("%lld%lld%lld%lld%lld%lld",&p,&q,&a1,&a2,&n,&mod);
if(n==1){printf("%lld",a1);return 0;}
if(n==2){printf("%lld",a2);return 0;}
a.m[1][1]=a2,a.m[1][2]=a1;
b.m[1][1]=p,b.m[2][1]=q,b.m[1][2]=1;
map ans;ans.csh();
k=n-2;
while(k){if(k&1)ans=chen(ans,b);b=chen(b,b);k>>=1;}
printf("%lld",chen(a,ans).m[1][1]%mod);
return 0;
}
```
by 黑影洞人 @ 2022-02-23 13:40:32