# include <bits/stdc++.h>

using i64 = long long ;
using namespace std ;

namespace IO
{
    template < typename T > inline T Read ()
    {
        T v = 0, f = 1 ; char c = getchar () ;

        while ( !isdigit ( c ) )
        {
            if ( c == '-' ) f = -1 ;
            c = getchar () ;
        }

        while ( isdigit ( c ) )
        {
            v = ( v << 3 ) + ( v << 1 ) + ( c - '0' ) ;
            c = getchar () ;
        }

        return v *= f ;
    }

    template < typename T > inline void Write ( T v )
    {
        if ( v < 0 ) putchar ( '-' ), v = -v ;
        if ( v > 9 ) Write ( v / 10 ) ;
        return putchar ( v % 10 + '0' ), void () ;
    }
}

using IO :: Read ;
using IO :: Write ;

namespace Program
{
    const int MAXN = 55 ;

    int n, p, k, r ;
    int C[MAXN][MAXN] ;
    
    vector <int> f ;

    inline int Get ( int v ) { return v - ( v >= p ) * p ; }

    inline void Init ()
    {
        C[0][0] = 1 ;
        for ( register int i = 1; i <= k; ++i )
        {
            C[i][0] = 1 ;
            for ( register int j = 1; j <= i; ++j ) C[i][j] = Get ( C[i - 1][j] + C[i - 1][j - 1] ) ;
        }
        
        f.resize ( k ), f[0] = 2 % p ;
        for ( register int i = 1; i < k; ++i ) f[i] = C[k][i] ;

        return ;
    }

    inline vector <int> Multiply ( vector <int> &a, vector <int> &b )
    {
        vector <int> res ; res.resize ( k ) ;
        for ( register int i = 0; i < k; ++i ) for ( register int j = 0; j < k; ++j ) res[( i + j ) % k] = Get ( res[( i + j ) % k] + 1LL * a[i] * b[j] % p ) ;
        return res ;
    }

    inline void Solve ( vector <int> &a, int b )
    {
        vector <int> res ( k ) ; res.resize ( k ), res[0] = 1 ;
        while ( b )
        {
            if ( b & 1 ) res = Multiply ( res, a ) ;
            a = Multiply ( a, a ), b >>= 1 ;
        }
        return Write ( res[r] ), putchar ( '\n' ), void () ;
    }

    inline int Run ()
    {
        n = Read <int> (), p = Read <int> (), k = Read <int> (), r = Read <int> (), Init (), Solve ( f, n ) ;
        return 0 ;
    }
}

int main () { return Program :: Run () ; }