#include<bits/stdc++.h>
#define int long long
using namespace std;
ifstream fin("problem_heoi2017.in");
ofstream fout("problem_heoi2017.out");
auto mread = [](){int x;fin >> x;return x;};
const int N = 55;
int n = mread(), MOD = mread(), k = mread(), r = mread();
struct node{
    int a[N][N];
    int n;
    node(){
        for(int i = 0; i < N; i ++){
            for(int j = 0; j < N; j ++)
            a[i][j] = 0;
        }
    }
    friend node operator * (node a, node b){
        node ans;
        ans.n = a.n;
        for(int i = 0; i <= a.n; i ++){
            for(int j = 0; j <= a.n; j ++){
                for(int k = 0; k <= a.n; k ++)
                (ans.a[i][j] += a.a[i][k] * b.a[k][j] % MOD) %= MOD;
            }
        }
        return ans;
    }
};
node ksm(node x, int k){
    node ans, now = x;
    ans.n = x.n;
    for(int i = 0; i <= x.n; i ++)
    ans.a[i][i] = 1;
    while(k){
        if(k & 1)
        ans = ans * now;
        now = now * now;
        k >>= 1;
    }
    return ans;
}
signed main(){
    node f;
    f.n = k - 1;
    f.a[0][0] = 1;
    node s;
    s.n = k - 1;
    s.a[k - 1][0] ++, s.a[0][0] ++;
    for(int i = 1; i < k; i ++){
        s.a[i][i] ++, s.a[i - 1][i] ++;
    }
    f = f * ksm(s, n * k);
    fout << f.a[0][r];
    return 0;
}