#include <bits/stdc++.h>
using namespace std;
const long long N = 2e5 + 30, Mod = 1e9 + 7;
const long long SQ = 330;
long long n, k, m, l;
map<long long, long long> Fib;
long long POW(long long x, long long y) {
  long long res = 1;
  while (y) {
    if (y & 1) res = (res * x) % m;
    x = (x * x) % m;
    y >>= 1;
  }
  return res;
}
long long f(long long x) {
  if (Fib.count(x)) return Fib[x];
  long long s = x / 2;
  long long s2 = (x + 1) / 2;
  long long res = f(s);
  res *= f(s2);
  long long res2 = f(s - 1) * f(s2 - 1);
  res %= m;
  res2 %= m;
  res = (res + res2) % m;
  return Fib[x] = res;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> k >> l >> m;
  long long P = POW(2, n);
  Fib[0] = Fib[1] = 1;
  long long ans = 1 % m;
  long long G = f(n + 1);
  if (l < 61 && k >= (1ll << l)) return cout << 0, 0;
  for (int i = 0; i < l; i++) {
    if (k & (1ll << i))
      ans *= (P - G + m) % m;
    else
      ans *= G;
    ans %= m;
  }
  cout << ans;
  return (0);
}
