#include <bits/stdc++.h>
using namespace std;
unordered_map<long long int, long long int> fib;
inline void getFib(long long int n, long long int mod) {
  auto iter = fib.find(n);
  if (iter == fib.end()) {
    vector<long long int> path;
    long long int last = n - 3;
    while (last > 0) {
      path.push_back(last);
      last /= 2;
    }
    long long int base[2][2] = {{1, 1}, {1, 0}};
    long long int t[2][2] = {{1, 1}, {1, 0}};
    for (int i = (int)path.size() - 2; i >= 0; --i) {
      long long int a00 = (t[0][0] * t[0][0] + t[0][1] * t[1][0]) % mod;
      long long int a01 = (t[0][0] * t[0][1] + t[0][1] * t[1][1]) % mod;
      long long int a10 = (t[1][0] * t[0][0] + t[1][1] * t[1][0]) % mod;
      long long int a11 = (t[1][0] * t[0][1] + t[1][1] * t[1][1]) % mod;
      t[0][0] = a00;
      t[0][1] = a01;
      t[1][0] = a10;
      t[1][1] = a11;
      if (path[i] % 2 == 1) {
        a00 = (t[0][0] * base[0][0] + t[0][1] * base[1][0]) % mod;
        a01 = (t[0][0] * base[0][1] + t[0][1] * base[1][1]) % mod;
        a10 = (t[1][0] * base[0][0] + t[1][1] * base[1][0]) % mod;
        a11 = (t[1][0] * base[0][1] + t[1][1] * base[1][1]) % mod;
        t[0][0] = a00;
        t[0][1] = a01;
        t[1][0] = a10;
        t[1][1] = a11;
      }
    }
    fib[n] = (t[0][0] * 5 + t[0][1] * 3) % mod;
  }
}
int main() {
  fib[0] = 0;
  fib[1] = 1;
  fib[2] = 3;
  fib[3] = 5;
  long long int n, k, l, mod;
  cin >> n >> k >> l >> mod;
  unsigned long long int maxV = 1;
  maxV = maxV << l;
  if ((k >= maxV && l < 64) || (l == 0 && k != 0)) {
    cout << 0 << endl;
    return 0;
  }
  if (l == 0 && k == 0) {
    cout << (1 % mod) << endl;
    return 0;
  }
  getFib(n, mod);
  long long int zeroFactor = fib[n];
  long long int oneFactor = 2;
  vector<long long int> path;
  long long int m = n;
  while (m > 0) {
    path.push_back(m);
    m /= 2;
  }
  for (int i = (int)path.size() - 2; i >= 0; --i) {
    oneFactor = oneFactor * oneFactor;
    oneFactor %= mod;
    if (path[i] % 2 == 1) {
      oneFactor *= 2;
      oneFactor %= mod;
    }
  }
  oneFactor -= zeroFactor;
  while (oneFactor < 0) oneFactor += mod;
  vector<int> bitk;
  while (k > 0) {
    bitk.push_back(k % 2);
    k /= 2;
  }
  while (bitk.size() != l) {
    bitk.push_back(0);
  }
  long long int ans = 1;
  for (int i = 0; i < bitk.size(); ++i) {
    if (bitk[i] == 0) {
      ans *= zeroFactor;
      ans %= mod;
    } else {
      ans *= oneFactor;
      ans %= mod;
    }
  }
  cout << ans << endl;
  return 0;
}
