#include<bits/stdc++.h>
using namespace std;
long long n,p,k,r,s1[2000005],s2[2000005],as;
long long C(long long x,long long y){
    if(x<0||y<0||y<x) return 0;
    return s1[y]*s2[x]%p*s2[y-x]%p;
}
inline long long pw(long long x,long long y){
    long long ss=1;
    while(y){
        if(y&1) ss*=x,ss%=p;
        x*=x,x%=p;
        y>>=1;
    }
    return ss;
}
int main(){
    freopen("problem.in","r",stdin);
    freopen("problem.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n>>p>>k>>r,s1[0]=s2[0]=s2[1]=1;
    if(k==1){
        cout<<pw(2,n);
        return 0;
    }else if(k==2){
        cout<<pw(2,n+n-1);
        return 0;
    }else if(p==2){
        cout<<0;
        return 0;
    }
    if(n*k<=1e6){
        for(int i=1;i<=n*k;i++) s1[i]=s1[i-1]*i%p;
        for(int i=2;i<=n*k;i++) s2[i]=(p-p/i)*s2[p%i]%p;
        for(int i=1;i<=n*k;i++) s2[i]=s2[i]*s2[i-1]%p;
        for(int i=0;i<=n;i++){
            as+=C(i*k+r,n*k);
            as%=p;
        }
        cout<<as;
    }
    return 0;
}