#include <bits/stdc++.h>
using namespace std;

const int K = 55;

int n, mod, k, r;

struct M {
	int a[K][K];

	M () {
		memset(a, 0, sizeof(a));
	}

	M operator * (const M &rhs) const {
		M res;
		for (int i = 0; i < k; i++) {
			for (int j = 0; j < k; j++) {
				for (int x = 0; x < k; x++) {
					res.a[i][x] += 1ll * a[i][j] * rhs.a[j][x] % mod;
					if (res.a[i][x] >= mod) {
						res.a[i][x] -= mod;
					}
				}
			}
		}
		return res;
	}
} U, I;

M qpow(M x, long long y) {
	M res = U;
	while (y) {
		if (y & 1) {
			res = res * x;
		}
		x = x * x;
		y >>= 1;
	}
	return res;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> mod >> k >> r;
	for (int i = 0; i < k; i++) {
		U.a[i][i] = 1;
	}
	for (int i = 0; i < k; i++) {
		I.a[i][i]++;
		I.a[i][(i + 1) % k]++;
	}
	M res = qpow(I, 1ll * n * k);
	cout << res.a[0][r] << '\n';

	return 0;
}