#include<bits/stdc++.h>
#define int long long
#define ll long long
#define pir pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
inline int re()
{
    int f=1,num=0;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    return num*f;
}
int T;
void clear();
const int N=50;
int n,r,k,MOD;
void add(int &a,int b)
{
    a+=b;
    if(a>=MOD) a-=MOD;
    return;
}
struct Matrix
{
    int a[N][N];
    Matrix(){memset(a,0,sizeof(a));}
    Matrix operator *(const Matrix &b)const
    {
        Matrix res;
        for(int i=0;i<k;i++) for(int j=0;j<k;j++) for(int l=0;l<k;l++) add(res.a[i][j],a[i][l]*b.a[l][j]%MOD);
        return res;
    }
}ans,g;
void qpow(int b)
{
    while(b)
    {
        if(b&1) ans=ans*g;
        g=g*g;b>>=1;
    }
    return;
}
void work()
{
    clear();
    n=re();MOD=re();k=re();r=re();
    ans.a[0][0]=1;
    for(int i=0;i<k;i++) g.a[i][i]++;
    g.a[k-1][0]++;for(int i=1;i<k;i++) g.a[i-1][i]++;
    qpow(n*k);
    printf("%lld\n",ans.a[0][r]);
    return;
}
signed main()
{
    freopen("problem.in","r",stdin);
    freopen("problem.out","w",stdout);
    T=1;
    while(T--) work();
    return 0;
}
void clear()
{
    return;
}