#include <bits/stdc++.h>
using namespace std;
long long binpow(long long a, long long n, long long m) {
  long long res = 1;
  while (n) {
    if (n & 1) {
      res *= a;
      res %= m;
    }
    a *= a;
    a %= m;
    n >>= 1;
  }
  return res;
}
long long binpow(long long a, long long n) {
  long long res = 1;
  while (n) {
    if (n & 1) {
      res *= a;
    }
    a *= a;
    n >>= 1;
  }
  return res;
}
vector<vector<long long> > binpowmat(vector<vector<long long> > a, long long n,
                                     long long m) {
  vector<vector<long long> > res(2, vector<long long>(2));
  res[0][0] = res[1][1] = 1;
  while (n) {
    if (n & 1) {
      vector<vector<long long> > tmp = res;
      res[0][0] = (tmp[0][0] * a[0][0] % m + tmp[0][1] * a[1][0] % m) % m;
      res[1][0] = (tmp[1][0] * a[0][0] % m + tmp[1][1] * a[1][0] % m) % m;
      res[0][1] = (tmp[0][0] * a[0][1] % m + tmp[0][1] * a[1][1] % m) % m;
      res[1][1] = (tmp[1][0] * a[0][1] % m + tmp[1][1] * a[1][1] % m) % m;
    }
    vector<vector<long long> > tmp = a;
    a[0][0] = (tmp[0][0] * tmp[0][0] % m + tmp[0][1] * tmp[1][0] % m) % m;
    a[1][0] = (tmp[1][0] * tmp[0][0] % m + tmp[1][1] * tmp[1][0] % m) % m;
    a[0][1] = (tmp[0][0] * tmp[0][1] % m + tmp[0][1] * tmp[1][1] % m) % m;
    a[1][1] = (tmp[1][0] * tmp[0][1] % m + tmp[1][1] * tmp[1][1] % m) % m;
    n >>= 1;
  }
  return res;
}
int main(int argc, const char* argv[]) {
  long long n, k, l, m;
  cin >> n >> k >> l >> m;
  int logk = 0;
  long long tmp = k;
  while (tmp) {
    tmp /= 2;
    ++logk;
  }
  if (logk > l) {
    cout << 0 << endl;
    return 0;
  }
  long long ans = 1;
  vector<vector<long long> > a(2, vector<long long>(2));
  a[1][0] = a[0][1] = a[1][1] = 1;
  long long fb = binpowmat(a, n + 2, m)[1][0];
  long long dfb = binpow(2, n, m) - fb;
  dfb %= m;
  while (dfb < 0) {
    dfb += m;
  }
  while (k) {
    int r = k % 2;
    if (!r) {
      ans *= fb;
      ans %= m;
    } else {
      ans *= dfb;
      ans %= m;
    }
    k /= 2;
  }
  for (int i = 0; i < l - logk; ++i) {
    ans *= fb;
    ans %= m;
  }
  ans %= m;
  cout << ans << endl;
  return 0;
}
