#include <bits/stdc++.h>
using namespace std;
map<long long, int> f;
long long N, K, L;
int res, p, to, MOD, i;
int F(long long N) {
  if (f.count(N)) return f[N];
  long long k = N / 2;
  if (N % 2 == 0)
    return f[N] = (1ll * F(k) * F(k) + 1ll * F(k - 1) * F(k - 1)) % MOD;
  else
    return f[N] = (1ll * F(k) * (F(k - 1) + F(k + 1))) % MOD;
}
int fastPow(int x, long long N) {
  int res = 1;
  for (int i = 0; i <= 62; ++i) {
    if ((1ll << i) & N) res = (1ll * res * x) % MOD;
    x = (1ll * x * x) % MOD;
  }
  return res;
}
int main() {
  cin >> N >> K >> L >> MOD;
  if (L < 63 && (1ll << L) <= K) {
    cout << "0" << '\n';
    return 0;
  }
  if (L == 0) {
    if (K == 0) {
      cout << 1 % MOD << '\n';
      return 0;
    }
    cout << "0" << '\n';
    return 0;
  }
  to = fastPow(2, N);
  f[0] = f[1] = 1;
  p = F(N + 1);
  res = 1;
  for (i = 0; i < L; ++i)
    if ((K & (1ll << i)) == 0)
      res = (1ll * res * p) % MOD;
    else
      res = (1ll * res * (to - p)) % MOD;
  res = (res + MOD) % MOD;
  cout << res << '\n';
  return 0;
}
