#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,p,k,r;
ll a[1000][1000];
ll ans;
ll ksm(ll x,ll y)
{
    if(!y) return 1;
    ll ans1=ksm(x,y/2);
    ans1=ans1*ans1%p;
    if(y%2) ans1=ans1*x%p;
    return ans1;
}
ll b[1000010],c[1000010];
int main()
{
    freopen("problem.in","r",stdin);
    freopen("problem.out","w",stdout);
    cin>>n>>p>>k>>r;
    if(n<=30&&k<=30)
    {
        for(int i=0;i<=n*k;i++) a[i][0]=1;
        for(int i=1;i<=n*k;i++)
            for(int j=1;j<=i;j++) a[i][j]=(a[i-1][j]+a[i-1][j-1])%p;
        for(int i=r;i<=n*k;i+=k) ans=(ans+a[n*k][i])%p;
        cout<<ans<<'\n';
    }
    else if(k==1) cout<<ksm(2,k*n)<<'\n';
    else if(k==2) cout<<ksm(1,k*n-1)<<'\n';
    else
    {
        b[0]=c[0]=1;
        for(int i=1;i<=1e6;i++)
        {
            b[i]=i*b[i-1]%p;
            c[i]=ksm(b[i],p-2);
        }
        ll tmp=1;
        for(int i=1;i<=n*k;i++) tmp=tmp*i%p;
        for(int i=r;i<=n*k;i+=k)
        {
            ans=(ans+tmp*c[i]%p*c[n*k-i])%p;
        }
        cout<<ans<<'\n';
    }
    return 0;
}