#include<bits/stdc++.h>
using namespace std;
long long n,r,k,p,a[1000006],b[1000006];
long long fp(long long x,long long y){
    if(y==1)return x;
    if(y==0)return 1;
    long long t=fp(x,y/2)%p;
    t=t*t%p;t%=p;
    if(y&1)t*=x%p;
    return t%p;
}
long long C(long long x,long long y){
    if(x>y)return 0;
    return (a[y]*b[x])%p*b[y-x]%p;
}
int main(){
    freopen("problem.in","r",stdin);
    freopen("problem.out","w",stdout);
    scanf("%lld%lld%lld%lld",&n,&p,&k,&r);
    if(p==2){cout<<0;return 0;}
    if(k==1||k==2){
        long long ans=fp(2,k*n);
        if(k==2)ans/=2;
        printf("%lld",ans);return 0;
    }
    a[0]=1;b[0]=1;
    for(int i=1;i<=1e6+2;i++){
        a[i]=a[i-1]*i;
        a[i]%=p;
        b[i]=fp(a[i],p-2)%p;
    }
    long long ans=0;
    for(int i=0;i<=n;i++){
        ans+=C(i*k+r,n*k)%p;
        ans%=p;
    }
    printf("%lld",ans);
    return 0;
}