#include <bits/stdc++.h>
using namespace std;
map<long long, long long> Fib;
long long n, k, l, m, res = 1;
long long f(long long x) {
  if (Fib.count(x)) return Fib[x];
  return Fib[x] =
             (f((x + 1) / 2) * f(x / 2) + f((x - 1) / 2) * f((x - 2) / 2)) % m;
}
long long pow_mod(long long a, long long b, long long M) {
  long long res = 1;
  a %= M;
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % M;
    a = a * a % M;
  }
  return res;
}
int main() {
  cin >> n >> k >> l >> m;
  Fib[0] = Fib[1] = 1;
  for (long long i = 0; i < l; i++) {
    if (k & (1LL << i))
      res = res * (pow_mod(2, n, m) - f(n + 1) + m) % m;
    else
      res = res * f(n + 1) % m;
    while (res < 0) res += m;
  }
  for (long long i = l; i < 60; i++)
    if (k & (1LL << i)) res = 0, i = 61;
  cout << res % m;
}
