#include <bits/stdc++.h>
using namespace std;
int MOD = 1000000000 + 7;
long long sq(long long a) { return a * a; }
long long pot(long long a, long long b) {
  return b ? ((sq(pot(a, b >> 1)) % MOD) * (b & 1 ? a : 1)) % MOD : 1;
}
struct mat {
  long long a, b, c, d;
  mat operator*(const mat& m) const {
    mat res;
    res.a = ((a * m.a) % MOD + (b * m.c) % MOD) % MOD;
    res.b = ((a * m.b) % MOD + (b * m.d) % MOD) % MOD;
    res.c = res.b;
    res.d = ((c * m.b) % MOD + (d * m.d) % MOD) % MOD;
    return res;
  }
};
mat matPot(mat b, long long e) {
  if (e == 1)
    return b;
  else if (e == 2)
    return b * b;
  else if (e % 2 == 0)
    return matPot(matPot(b, e / 2), 2);
  else
    return matPot(matPot(b, e / 2), 2) * b;
}
long long fib(long long f) {
  if (f == 0)
    return 0;
  else if (f == 2 || f == 1)
    return 1;
  else {
    mat a;
    a.a = a.b = a.c = 1;
    a.d = 0;
    return matPot(a, f - 1).a;
  }
}
int main() {
  long long n, k, l;
  cin >> n >> k >> l >> MOD;
  if (l == 0) {
    if (k == 0)
      cout << 1 % MOD << endl;
    else
      cout << 0 % MOD << endl;
    return 0;
  }
  long long F = fib(n + 2);
  long long p2 = pot(2, n);
  long long ak = k;
  int al = 0;
  bool pot2 = true;
  while (ak != 0) {
    if (ak % 2 != 0) pot2 = false;
    al++;
    ak = ak >> 1;
  }
  if (al > l && !pot2) {
    cout << 0 << endl;
    return 0;
  }
  long long p = (p2 - F + MOD) % MOD;
  long long sol = 1;
  while (l--) {
    if (!(1 & k))
      sol = (sol * F) % MOD;
    else
      sol = (sol * p) % MOD;
    k = k >> 1;
  }
  cout << sol << endl;
}
