#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 333;
const long long linf = 1e18 + 333;
long long mod;
map<long long, long long> fib;
long long f(long long n) {
  if (n < 2) return 1;
  if (fib.find(n) != fib.end()) return fib[n];
  return fib[n] =
             (f((n + 1) / 2) * f(n / 2) + f((n - 1) / 2) * f((n - 2) / 2)) %
             mod;
}
long long pw(long long x, long long k) {
  if (!k) return 1;
  long long t = pw(x, k / 2);
  if (k & 1) return t * t % mod * x % mod;
  return t * t % mod;
}
int main() {
  ios ::sync_with_stdio(0);
  long long n, k, l;
  cin >> n >> k >> l >> mod;
  if (l < 63 and (1LL << l) <= k) {
    cout << 0 << endl;
    return 0;
  }
  long long aLL = pw(2, n), fib = f(n + 1), ans = 1;
  for (int i = 0; i < l; i++) {
    if (i < 63 and (k & 1LL << i)) {
      long long res = aLL - fib;
      if (res < 0) res += mod;
      ans = ans * res % mod;
    } else
      ans = ans * fib % mod;
  }
  ans %= mod;
  cout << ans << endl;
  return 0;
}
