#include <cstdio>

#include <cstring>

#include <algorithm> 

#define setIO(s) freopen(s".in","r",stdin)

#define N 60

#define ll long long

#define mod p

using namespace std;

int k,r;

long long n,p;

struct matrix{

    long long mat[N][N];

};

void init(matrix &a){

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

        for(int j=0;j<k;++j) a.mat[i][j]=0;

}

void get(matrix &a){

    init(a);

    for(int i=0;i<k;++i) a.mat[i][i]=1;

}

matrix operator*(matrix a,matrix b){

    matrix c;

    init(c);

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

        for(int j=0;j<k;++j)

            for(int kk=0;kk<=k;++kk)

                c.mat[i][j]=(c.mat[i][j]+(long long)(a.mat[i][kk]*b.mat[kk][j]))%mod;

    return c;

}

matrix operator^(matrix a,ll p){

    matrix res;

    get(res);

    while(p>0){

        if(p&1) res=res*a;

        a=a*a;

        p>>=1;

    }

    return res;

}

int main(){

    //setIO("input");

    scanf("%lld%lld%d%d",&n,&mod,&k,&r);

    matrix ans,a;

    init(ans),init(a),ans.mat[0][0]=1;

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

        a.mat[i?i-1:k-1][i]++,a.mat[i][i]++;

    n*=k;

    ans=ans*(a^n);

    printf("%lld\n",ans.mat[0][r]);

    return 0;

}