#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define in inline
#define re register
#define pii pair<int,int>
#define fi first 
#define se second
#define pb(x) push_back(x)
#define D(i,a,b) for(re long double i = a;i >= b;i--)
#define F(i,a,b) for(re long long i = a;i <= b;i++)
const int N = 1e5+10;
const ll inf = 1e17;

ll read(){
    ll x = 0,f = 1;char c = getchar();
    for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
    for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
    return x * f;
}

ll n,p,k,r;
struct Matrix{
    ll a[60][60],n,m;
    void clear(){memset(a,0,sizeof a),n = m = 0;}
    Matrix operator * (const Matrix &x)const{
        Matrix y;y.clear();
        y.n = n,y.m = m;
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                for(int k = 0;k < m;k++)y.a[i][j] = (y.a[i][j] + a[i][k] * x.a[k][j] % p) % p;
            }
        }
        return y;
    }
}U,F;


int main(){
    freopen("problem_heoi2017.in","r",stdin);
    freopen("problem_heoi2017.out","w",stdout);
    n = read(),p = read(),k = read(),r = read();
    U.n = 1,U.m = k;
    if(k == 1)U.a[0][0] = 2 % p;
    else U.a[0][0] = U.a[0][1] = 1;//初始化 
    F.n = F.m = k;
    F(i,0,k-1){
        F.a[(i-1+k)%k][i] += 1;
        F.a[i][i] += 1;
    }
    n = n * k - 1;
    while(n){
        if(n & 1)U = U * F;
        F = F * F;
        n >>= 1; 
    }//矩阵快速幂 
    printf("%lld\n",U.a[0][r]);
    
    
	return cerr << "Time : " << clock() << " ms" << endl, 0;
        
}