记录编号	577974	评测结果	AAAAAAAAAA
题目名称	[SRM 377] 外星语言	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-01-03 08:33:04	内存使用	0.00 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int,int>
#define vi vector<int>
#define si set<int>
#define qi queue<int>
#define sti stack<int>
#define fi first
#define se second
#define pb push_back
const int N=5;
ll p,q,n=3,m,mod;
struct sdf{
	ll p[N][N];
	sdf(){
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++)p[i][j]=0;
		}
	}
	sdf operator*(const sdf&x)const{
		sdf tmp;
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++){
				for (int k=1;k<=n;k++){
					tmp.p[i][j]=(tmp.p[i][j]+p[i][k]*x.p[k][j]%mod)%mod;
				}
			}
		}
		return tmp;
	}
}A,B,C,id,mp;
void fst(int x){
	if (!x){
		B=id;return ;
	}
	if (x&1){
		fst(x-1);B=B*A;return ;
	}
	else{
		fst(x/2);B=B*B;return ;
	}
}
ll calc(ll x){
	A=B=C;
	A.p[1][1]=1;
	A.p[1][3]=A.p[2][3]=2*x;
	A.p[1][2]=A.p[2][2]=A.p[2][3]=A.p[3][3]=x;
	fst(m);
	return B.p[1][3];
}
int main(){
	freopen ("alienlanguage.in","r",stdin);
	freopen ("alienlanguage.out","w",stdout);
	scanf("%lld%lld%lld%lld",&p,&q,&m,&mod);
	for (int i=1;i<=n;i++)id.p[i][i]=1;
	ll x=calc(p),y=calc(q);
	printf("%lld\n",(x*y%mod+x+y)%mod);
	return 0;
}