#include<bits/stdc++.h>
#define ll long long
#define N 1000001
using namespace std;
ll n,p,k,r,fac[N],inv[N],num,ans;
ll fpow(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1) res=res*a%p;
		a=a*a%p;
		b>>=1;
	}
	return res;
}
ll C(ll a,ll b){
	if(a<0||b<0||a>b) return 0;
	return fac[b]*inv[a]%p*inv[b-a]%p;
}
int main(){
    freopen("problem.in","r",stdin);
    freopen("problem.out","w",stdout);
    cin>>n>>p>>k>>r;
    if(n*k>=N&&p==2){
        cout<<0<<endl;
        return 0;
    }
    if(k==1){
        cout<<fpow(2,n)%p<<endl;
        return 0;
    }
    if(k==2){
        cout<<fpow(2,n*k-1)%p<<endl;
        return 0;
    }
    fac[0]=inv[0]=1;
	for(int i=1;i<N;i++){
	    fac[i]=(fac[i-1]*i)%p;
        inv[i]=fpow(fac[i],p-2);
    }
	while(num*k+r<=n*k){
	    ans=(ans+C(num*k+r,n*k))%p;
	    num++;
    }
    cout<<ans<<endl;
    return 0;
}