#include <bits/stdc++.h>
using namespace std;
struct mat {
  long long mapp[2][2];
};
mat res = {1, 0, 0, 1}, init = {1, 1, 1, 0};
mat mul_mat(mat a, mat b, long long mod) {
  mat c;
  memset(c.mapp, 0, sizeof(c.mapp));
  for (int k = 0; k < 2; k++) {
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        (c.mapp[i][j] += a.mapp[i][k] * b.mapp[k][j] % mod) %= mod;
      }
    }
  }
  return c;
}
mat ksm_mat(mat n, long long k, long long mod) {
  mat t = n, ans = res;
  while (k) {
    if (k & 1) ans = mul_mat(ans, t, mod);
    t = mul_mat(t, t, mod);
    k /= 2;
  }
  return ans;
}
long long ksm(long long n, long long k, long long mod) {
  long long temp = n, ans = 1;
  while (k) {
    if (k % 2) ans = (ans * temp) % mod;
    k /= 2;
    temp = (temp * temp) % mod;
  }
  return ans % mod;
}
int main() {
  mat ma;
  long long n, k, l, m;
  long long ans;
  while (~scanf("%lld %lld %lld %lld", &n, &k, &l, &m)) {
    ans = 0;
    if (l == 64 || (1uLL << l) > k) {
      ans++;
      ma = init;
      ma = ksm_mat(ma, n + 1, m);
      long long t1 = ma.mapp[0][0];
      long long t2 = (m + ksm(2, n, m) - t1) % m;
      for (long long i = 0; i < l; i++) {
        if (k & (1uLL << i)) {
          ans = (ans * t2) % m;
        } else {
          ans = (ans * t1) % m;
        }
      }
    }
    printf("%lld\n", ans % m);
  }
}
