#include <bits/stdc++.h>

#define R register
#define ll long long
#define vec std::vector
#define sum(a, b, mod) (((a) + (b)) % mod)
#define meow(cat...) fprintf(stderr, cat)

int n, r, p, k;

inline int read()
{
    int x = 0;
    char ch = getchar();
    while(ch > '9' || ch < '0')
        ch = getchar();
    while(ch <= '9' && ch >= '0') 
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}

vec<int> operator*(const vec<int>&l, const vec<int>&r)
{
    vec<int> res(k);
    for(int i = 0; i < k; i++)
        for(int j = 0; j < k; j++)
            res[(i + j) % k] = sum(res[(i + j) % k], 1ll * l[i] * r[j], p);
    return res;
}

signed main()
{       
    n = read(), p = read(), k = read(), r = read();
    vec<int> a(k), ans(k);
    if(k == 1) a[0] = 2 % p, ans[0] = 1;
    else a[0] = a[1] = 1, ans[0] = 1;
    auto num = 1ll * n * k;
    while(num > 0)
    {
        if(num & 1)
            ans = ans * a;
        a = a * a, num >>= 1;
    }
    printf("%d\n", ans[r]);
    return 0;
}