#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll n,mod,k,r,m;
ll fac[210000],inv[210000];
ll ans;

ll mpow(ll aa,ll bb){
    ll res=1;
    while (bb){
        if (bb&1) res=res*aa%mod;
        aa=aa*aa%mod;
        bb>>=1;
    }
    return res;
}

ll C(ll aa,ll bb){
	if (aa<bb||aa<0||bb<0) return 0;
	return fac[aa]*inv[bb]%mod*inv[aa-bb]%mod;
}


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>>mod>>k>>r;
	m=n*k;
	if (k==1){
		cout<<mpow(2,n)<<'\n';
		return 0;
	}
	if (mod==2){
		cout<<0<<'\n';
		return 0;
	}
	if (k==2){
		cout<<mpow(2,2*n-1);
		return 0;
	}
	fac[0]=1;
	for (int i=1;i<=200100;i++){
		fac[i]=(fac[i-1]*i)%mod;
	}
	for (int i=0;i<=200100;i++){
		inv[i]=mpow(fac[i],mod-2);
	}
	for (int i=r;i<=m;i+=k){
		ans+=C(m,i);
		ans%=mod;
	}
	cout<<ans<<'\n';
    return 0;
}