#include <bits/stdc++.h>
using namespace std;
long long n, k;
int inl, inm;
long long mat[4][4] = {{1, 1, 0, 0}, {1, 0, 0, 1}, {0, 0, 1, 1}, {0, 0, 1, 1}};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> k >> inl >> inm;
  if (log2(k) >= inl || inm == 1) {
    cout << 0 << endl;
    return 0;
  }
  long long e = n - 1, ret[4] = {1, 1, 0, 0};
  while (e) {
    if (e & 1) {
      long long newret[4] = {};
      for (int l = 0; l < 4; l++) {
        for (int r = 0; r < 4; r++) {
          newret[r] += ret[l] * mat[l][r];
          newret[r] %= inm;
        }
      }
      for (int i = 0; i < 4; i++) {
        ret[i] = newret[i];
      }
    }
    long long newmat[4][4] = {};
    for (int l = 0; l < 4; l++) {
      for (int m = 0; m < 4; m++) {
        for (int r = 0; r < 4; r++) {
          newmat[l][r] += mat[l][m] * mat[m][r];
          newmat[l][r] %= inm;
        }
      }
    }
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
        mat[i][j] = newmat[i][j];
      }
    }
    e >>= 1;
  }
  long long iszero = ret[0] + ret[1];
  long long isone = ret[2] + ret[3];
  long long ans = 1;
  for (int i = 0; i < inl; i++, k >>= 1) {
    ans *= (k & 1) ? isone : iszero;
    ans %= inm;
  }
  cout << ans << endl;
  return 0;
}
