#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int n,p,k,r,ans,f[N+10],b[N+10];
int qsm(int x,int y){
    int sum=y,cnt=x,ans=1;
    while(sum>0){
        if(sum%2==1) ans=(cnt*ans)%p;
        cnt=(cnt*cnt)%p;
        sum=sum/2;
    }
    return ans;
}
int C(int a,int b1){
	if(a<0||b1<0||a>b1) return 0;
    return f[b1]*b[a]%p*b[b1-a]%p;
} 
signed main(){
  freopen("problem.in","r",stdin);
  freopen("problem.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>p>>k>>r;
    if(k==1){
        cout<<qsm(2,n)%p;
        return 0;
    }
    if(p==1){
        cout<<0;
        return 0;
    }
    f[0]=1;
    for(int i=1;i<N;i++) f[i]=(f[i-1]*i)%p;
    for(int i=0;i<N;i++) b[i]=qsm(f[i],p-2);
    for(int i=0;i<=n;i++){
        if(r+i*k<=n*k)
            ans=(ans+C(r+i*k,n*k))%p;
    }
	cout<<ans%p<<endl;
    return 0;
}