#include <bits/stdc++.h>
using namespace std;
long long mod;
pair<long long, long long> fib(long long n) {
  if (n == 0) {
    return make_pair(0 % mod, 1 % mod);
  } else {
    pair<long long, long long> p = fib(n / 2);
    long long x = p.first, y = p.second;
    long long x1 = (1ll * x * (2 * y - x)) % mod,
              y1 = ((1ll * x * x) % mod + (1ll * y * y) % mod) % mod;
    if (n & 1)
      return make_pair(y1, (y1 + x1) % mod);
    else
      return make_pair(x1, y1);
  }
}
long long pow(long long n) {
  if (n == 0) return 1;
  long long ans = pow(n / 2);
  ans = (1ll * ans * ans) % mod;
  if (n & 1)
    return (ans * 2) % mod;
  else
    return ans;
}
int32_t main() {
  long long n, k, l;
  cin >> n >> k >> l >> mod;
  if (l < 62 && k >= (1ll << l)) return cout << 0, 0;
  long long ans1 = fib(n + 2).first;
  long long ans2 = (pow(n) - ans1 + mod) % mod;
  long long ans = 1;
  for (long long i = 0; i < min(l, 63ll); i++) {
    if (k & (1ll << i)) {
      ans = (1ll * ans * ans2) % mod;
    } else {
      ans = (1ll * ans * ans1) % mod;
    }
  }
  if (l == 64) ans = (1ll * ans * ans1) % mod;
  cout << (ans + mod) % mod;
}
