#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = ;

struct mat {

    ll a[N][N];

} x, g;

ll n, k, p, r;

void build()

{

    x.a[][] = ; //0个物品选0个的方案数为1

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

    {

        ++g.a[i][i]; ++g.a[i][(i + ) % k]; //矩阵的系数 f[i][j]=f[i-1][j]+f[i-1][j-1] 所以j=1,j-1=1

    }

}

mat operator * (const mat &A, const mat &B)

{

    mat ret; memset(ret.a, , sizeof(ret.a));

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

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

            for(int x = ; x < k; ++x) ret.a[i][j] = (ret.a[i][j] + A.a[i][x] * B.a[x][j]) % p;

    return ret;

}

void power(mat A, ll t)

{

    for(; t; A = A * A, t >>= ) if(t & ) x = x * A;

}

int main()

{

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

    build();

    power(g, n * k);

    printf("%lld\n", x.a[][r]);

    return ;

}