#include<iostream>
#include<cstring>
using namespace std;

const int MAXN = 55;
long long n, p, k, r;

struct node{
    long long a[MAXN][MAXN];
    node(){
        memset(a, 0, sizeof(a));
    }
    node operator * (const node &x)const{
        node c;
        for(int i = 1;i <= k;i ++)
			for(int j = 1;j <= k;j ++)
				for(int q = 1;q <= k;q ++)
					c.a[i][j] = (c.a[i][j] + (a[i][q] * x.a[q][j]) % p) % p;
		return c;
    }
}A, B;

node qpow(node x, long long y){
    node res;
    for(int i = 1;i <= k;i ++) res.a[i][i] = 1;
    while(y){
        if(y & 1) res = res * x;
        x = x * x;
        y >>= 1;
    }
    return res;
}

int main(){
    freopen("problem.in", "r", stdin);
    freopen("problem.out", "w", stdout);
    cin >> n >> p >> k >> r;
    for(int i = 1;i <= k;i ++){
        B.a[i][i] = 1;
        if(i == 1) B.a[i][k] = 1;
        else B.a[i][i - 1] = 1;
    }
    B = qpow(B, n * k);
    A.a[1][1] = 1;
    A = A * B;
    cout << A.a[1][r + 1] << '\n';
    return 0;
}