#include <bits/stdc++.h>
using namespace std;
unsigned long long MOD;
unsigned long long sq(unsigned long long a) { return a * a; }
unsigned long long pot(unsigned long long a, unsigned long long b) {
  return b ? ((sq(pot(a, b >> 1)) % MOD) * (b & 1 ? a : 1)) % MOD : 1;
}
unsigned long long fib(unsigned long long n) {
  if (n == 0) return 0;
  unsigned long long f1[2][2], f[2][2] = {{0, 1}, {1, 1}};
  int ln;
  for (ln = 0; (n >> ln); ln++)
    ;
  for (int i = ln - 2; i >= 0; i--) {
    f1[0][0] = (f[0][0] * f[0][0] + f[0][1] * f[1][0]) % MOD;
    f1[0][1] = (f[0][0] * f[0][1] + f[0][1] * f[1][1]) % MOD;
    f1[1][0] = (f[1][0] * f[0][0] + f[1][1] * f[1][0]) % MOD;
    f1[1][1] = (f[1][0] * f[0][1] + f[1][1] * f[1][1]) % MOD;
    if ((n >> i) % 2) {
      f[0][0] = f1[0][1];
      f[0][1] = (f1[0][0] + f1[0][1]) % MOD;
      f[1][0] = f1[1][1];
      f[1][1] = (f1[1][0] + f1[1][1]) % MOD;
    } else {
      f[0][0] = f1[0][0];
      f[0][1] = f1[0][1];
      f[1][0] = f1[1][0];
      f[1][1] = f1[1][1];
    }
  }
  return f[1][1];
}
int main() {
  unsigned long long n, k, res = 1;
  int l;
  cin >> n >> k >> l >> MOD;
  if ((k >= ((unsigned long long)1 << l) && k > 0 && l < 64) || MOD == 1) {
    cout << '0' << endl;
    return 0;
  }
  if (n == 1) {
    cout << '1' << endl;
    return 0;
  }
  for (int i = 0; i < l; i++) {
    if ((k >> i) % 2)
      res = (res * ((MOD + pot(2, n) - fib(n + 1)) % MOD)) % MOD;
    else
      res = (res * fib(n + 1)) % MOD;
  }
  cout << res << endl;
}
