#include <map>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define F(i,j,k) for (int i=j;i<=k;++i)

#define D(i,j,k) for (int i=j;i>=k;--i)

#define ll long long

#define mp make_pair

int n,p,k,r;

ll c;

struct Matrix{

    int x[51][51];

    void init(){memset(x,0,sizeof x);return;}

    void buildt()

    {init();F(i,0,k-1)x[i][i]++,x[i][(i+1)%k]++;return;}

    void builds()

    {init();x[0][0]=1;return;}

    Matrix operator * (Matrix a) {

        Matrix ret;

        ret.init();

        F(i,0,k-1) F(j,0,k-1) F(l,0,k-1)

            ret.x[i][j]=(ret.x[i][j]+(ll)x[i][l]*a.x[l][j])%p;

        return ret;

    }

}A,B;

int main()

{

    scanf("%d%d%d%d",&n,&p,&k,&r); c=(ll)n*k;

    A.builds(); B.buildt();

    for (;c;c>>=1,B=B*B) if (c&1LL) A=A*B;

    printf("%d\n",A.x[0][r]);

}