wa on #14 # 19

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, p, k, r;
int d[55][55], a[55][55], c[55][55];
void pow(int x){
	while(x){
		if(x & 1){
			for(int i = 0; i < k; i++){
				for(int j = 0; j < k; j++){
					c[i][j] = 0;
					for(int l = 0; l < k; l++){
						c[i][j] += a[i][l] * d[l][j];
						c[i][j] %= p; 
					}
				}
			}
			for(int i = 0; i < k; i++){
				for(int j = 0; j < k; j++){
					a[i][j] = c[i][j];
				}
			}
		}
		for(int i = 0; i < k; i++){
			for(int j = 0; j < k; j++){
				c[i][j] = 0;
				for(int l = 0; l < k; l++){
					c[i][j] += d[i][l] * d[l][j];
					c[i][j] %= p;
				}
			}
		}
		for(int i = 0; i < k; i++){
			for(int j = 0; j < k; j++){
				d[i][j] = c[i][j];
			}
		}
		x >>= 1;
	}
}
signed main(){
	scanf("%lld%lld%lld%lld", &n, &p, &k, &r);
	for(int i = 0; i < k; i++){
		d[i][i] = d[i ? i - 1 : k - 1][i] = 1;
		a[i][i] = 1;
	}
	pow(n * k);
    // for(int i = 0; i < k; i++){
    //     for(int j = 0; j < k; j++){
    //         printf("%d ", a[i][j]);
    //     }
    //     printf("\n");
    // }
	printf("%lld\n", a[0][r]);
	return 0;
}