#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;
int n, p, k, r;

const int N = 50;
struct Matrix{
    int a[N][N];

    Matrix(){
        memset(a, 0, sizeof a);
        for(int i = 0; i < N; i++){
            a[i][i] = 1;
        }
    }

    Matrix operator*(const Matrix &t) const {
        Matrix ans;
        memset(ans.a, 0, sizeof ans.a);
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                for(int k = 0; k < N; k++){
                    ans.a[i][j] = (ans.a[i][j] + 1LL * a[i][k] * t.a[k][j]) % p;
                }
            }
        }
        return ans;
    }

};

Matrix qpow(Matrix a, LL b){
    Matrix ans = Matrix();
    while(b){
        if (b & 1) ans = ans * a;
        b >>= 1;
        a = a * a;
    }
    return ans;
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    cin >> n >> p >> k >> r;
    Matrix a;
    memset(a.a, 0, sizeof a.a);
    for(int i = 0; i < k; i++){
        a.a[i][i] += 1;
        a.a[i][(i + 1) % k] += 1;
    }
    auto ans = qpow(a, 1LL * n * k);
    cout << ans.a[0][r] << '\n';

}