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