#include<cstdio>

#include<cmath>

#include<algorithm>

typedef unsigned long long u64;

typedef long double ld;

const ld pi=std::acos(-);

struct cplx{

    ld a,b;

    cplx(ld x=,ld y=):a(x),b(y){}

    cplx operator+(cplx x){return cplx(a+x.a,b+x.b);}

    cplx operator-(cplx x){return cplx(a-x.a,b-x.b);}

    cplx operator*(cplx x){return cplx(a*x.a-b*x.b,a*x.b+b*x.a);}

    cplx conj(){return cplx(a,-b);}

}A[],B[],E[][][];

u64 n,pwx[],ts[];

int m,k,x,ppx=,C[][],N,K;

int ans[],tmp[],tmp2[],rev[];

void dft(cplx*a,int t){

    for(int i=;i<N;++i)if(i<rev[i])std::swap(a[i],a[rev[i]]);

    for(int i=,z=;i<N;i<<=,++z){

        cplx*e=E[t][z];

        for(int j=;j<N;j+=i<<){

            cplx*b=a+j,*c=b+i;

            for(int k=;k<i;++k){

                cplx x=b[k],y=c[k]*e[k];

                b[k]=x+y;

                c[k]=x-y;

            }

        }

    }

    if(t)for(int i=;i<N;++i)a[i].a/=N;

}

void mul(int*a,int*b){

    for(int i=;i<=k;++i)B[i]=cplx(a[i],b[i]);

    for(int i=k+;i<N;++i)B[i]=;

    dft(B,);

    B[N]=B[];

    for(int i=;i<N;++i){

        cplx x=B[i],y=B[N-i].conj();

        A[i]=cplx(,0.25)*(y+x)*(y-x);

    }

    dft(A,);

    for(int i=;i<=k;++i)a[i]=((long long)(A[i].a+0.49))%m;

}

int main(){

    scanf("%llu%d%d%d",&n,&m,&k,&x);

    C[][]=;

    for(int i=;i<;++i){

        for(int j=;j<=i;++j){

            (C[i+][j]+=C[i][j])%=m;

            (C[i+][j+]+=C[i][j])%=m;

        }

    }

    for(pwx[ppx++]=;(pwx[ppx]=pwx[ppx-]*x)<=n;++ppx);

    for(int i=ppx-;i>=;--i){

        ts[i]=n/pwx[i];

        ts[i]-=ts[i]/x;

    }

    for(N=,K=;N<k*+;N<<=,++K);

    for(int i=;i<N;++i)rev[i]=rev[i>>]>>|(i&)<<K;

    for(int i=,z=;i<N;i<<=,++z){

        for(int j=;j<i;++j){

            E[][z][j]=cplx(cos(j*pi/i),sin(j*pi/i));

            E[][z][j]=E[][z][j].conj();

        }

    }

    ans[]=;

    for(int i=;i<ppx;++i){

        ts[i]-=ts[i+];

        for(int j=;j<=k;++j)tmp[j]=(i+-j>=?C[i+-j][j]:),tmp2[j]=;

        tmp2[]=;

        for(u64 t=ts[i];t;t>>=,mul(tmp,tmp))if(t&)mul(tmp2,tmp);

        mul(ans,tmp2);

    }

    printf("%d\n",ans[k]);

    return ;

}