#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,p,k,r;
long long f[N],inv[N];
long long C(int x,int y)
{
    return f[y]*inv[x]%p*inv[y-x]%p;
}
long long qpow(int x,int y)
{
    long long ans=1,cnt=x;
    while (y)
    {
        if (y%2==1) ans=ans*cnt%p;
        cnt=cnt*cnt%p;
        y/=2;
    }
    return ans;
}
void solve1()
{
    f[0]=inv[0]=f[1]=inv[1]=1;
    for (int i=2;i<=n*k;i++) 
    {
        f[i]=f[i-1]*i%p;
        inv[i]=qpow(f[i],p-2); 
    }
    long long ans=0;
    for (int i=0;i<=n;i++)
    {
        if (i*k+r<=n*k) ans=(ans+C(i*k+r,n*k))%p;
    }
    cout<<ans;
}
void solve2()
{
    cout<<(n*k%2==1 && (r+(r==0 ? 0 : k-r))%2==1);
}
void solve3()
{
    cout<<qpow(2,n);
}
int main() {
    freopen("problem.in","r",stdin);
    freopen("problem.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>p>>k>>r;
    if (n*k<=1e6) solve1();
    else if (p==2) solve2();
    else if (k==1) solve3();
}