#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,K,b,N;LL P;
struct node
{
    LL a[3][3];
    node(){memset(a,0,sizeof a);}
};

node operator*(node A,node B)
{
    node C; 
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            for (int k=1;k<=n;k++)
                C.a[i][j]=(C.a[i][j]+ A.a[i][k]*B.a[k][j])%P;
    return C;
}
node operator+ (node A,node B)
{
    node C; 
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
                C.a[i][j]=(A.a[i][j]+B.a[i][j])%P;
    return C;
}
node qpow(node A,int b)
{
    node C;for(int i=1;i<=n;i++)C.a[i][i]=1;
    for(;b;b>>=1)
    {
        if(b&1)C=C*A; 
        A=A*A;
    }
    return C;
}
node solve(node A,int b)
{
    if(b==1) return A;
    node t=solve(A,b/2);
    if(b&1) return t + t * qpow(A,b/2) + qpow(A,b);
    else    return t + t * qpow(A,b/2);
}
int main()
{
    scanf("%d%d%d%lld",&K,&b,&N,&P);n=2;
    node A;//A的第一行为（f0,f1） 
    A.a[1][1]=0;A.a[1][2]=1;
    node ff;
    ff.a[1][1]=0;
    ff.a[2][1]=1;
    
    ff.a[1][2]=1;
    ff.a[2][2]=1;
    A=A*qpow(ff,b);
    ff=qpow(ff,K);
    node ans=A+A*solve(ff,N-1);
    printf("%lld\n",ans.a[1][1]);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,K,b,N;LL P;
struct node
{
    LL a[3][3];
    node(){memset(a,0,sizeof a);}
};
node operator*(node A,node B)
{
node C;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
for (int k=1;k<=n;k++)
C.a[i][j]=(C.a[i][j]+ A.a[i][k]B.a[k][j])%P;
return C;
}
node operator+ (node A,node B)
{
node C;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
C.a[i][j]=(A.a[i][j]+B.a[i][j])%P;
return C;
}
node qpow(node A,int b)
{
node C;for(int i=1;i<=n;i++)C.a[i][i]=1;
for(;b;b>>=1)
{
if(b&1)C=CA;
A=A*A;
}
return C;
}
node solve(node A,int b)
{
if(b==1) return A;
node t=solve(A,b/2);
if(b&1) return t + t * qpow(A,b/2) + qpow(A,b);
else    return t + t * qpow(A,b/2);
}
int main()
{
scanf("%d%d%d%lld",&K,&b,&N,&P);n=2;
node A;//A的第一行为（f0,f1）
A.a[1][1]=0;A.a[1][2]=1;
node ff;
ff.a[1][1]=0;
ff.a[2][1]=1;
ff.a[1][2]=1;
ff.a[2][2]=1;
A=A*qpow(ff&#44;b);
ff=qpow(ff&#44;K);
node ans=A+A*solve(ff&#44;N-1);
printf("%lld\n"&#44;ans.a[1][1]);
return 0;

}