#include <bits/stdc++.h>
using namespace std;
int mod;
long long n, k;
int l;
struct mar {
  long long d[2][2];
  mar(int _a = 0, int _b = 0, int _c = 0, int _d = 0) {
    d[0][0] = _a;
    d[0][1] = _b;
    d[1][0] = _c;
    d[1][1] = _d;
  }
};
mar operator*(mar a, mar b) {
  mar c;
  for (int i = (0); i < (2); ++i)
    for (int j = (0); j < (2); ++j)
      for (int k = (0); k < (2); ++k) {
        c.d[i][j] += a.d[i][k] * b.d[k][j];
        c.d[i][j] %= mod;
      }
  return c;
}
mar kpow(mar a, long long b) {
  mar ans(1, 0, 0, 1);
  while (b) {
    if (b & 1) ans = ans * a;
    a = a * a;
    b >>= 1;
  }
  return ans;
}
long long kpow(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return ans;
}
int main() {
  cin >> n >> k >> l >> mod;
  if (l <= 60 && (k >> l) > 0) {
    cout << 0 << "\n";
    return 0;
  }
  mar fib(1, 1, 1, 0), res(3, 0, 2, 0);
  fib = kpow(fib, n - 2);
  res = fib * res;
  long long cas = res.d[0][0] % mod;
  long long ans = 1 % mod;
  for (int i = (0); i < (l); ++i) {
    if ((k >> i) & 1)
      ans = ((kpow(2, n) - cas) % mod + mod) % mod * ans % mod;
    else
      ans = ans * cas % mod;
  }
  cout << ans << "\n";
  return 0;
}
