#include <bits/stdc++.h>
using namespace std;
const int N = 101, infi = 1000000, mod = 1000000007;
long long n, m, k, l, sol = 1, sho, alt;
map<long long, long long> mem;
long long mul(long long fir, long long sec, long long MOD = m) {
  return ((fir % MOD) * (sec % MOD)) % MOD;
}
long long add(long long fir, long long sec, long long MOD = m) {
  return ((fir % MOD) + (sec % MOD) + 2ll * MOD) % MOD;
}
long long bow(long long fr, long long sc) {
  if (!sc) return 1;
  long long ret = bow(fr, sc / 2);
  ret = mul(ret, ret);
  if (sc % 2) ret = mul(ret, fr);
  return ret;
}
long long calc(long long L) {
  long long gt = mem[L];
  if (gt != 0) return gt == -1 ? 0 : gt;
  if (L == 0) return 1;
  if (L == 1) return 2;
  if (L < 0) return 1;
  if (L % 2) {
    long long ret1 = add(mul(calc(L / 2), calc(L / 2)),
                         mul(calc(L / 2 - 1), calc(L / 2 - 1)));
    if (ret1)
      mem[L] = ret1;
    else
      mem[L] = -1;
    return ret1;
  } else {
    long long ret = mul(calc(L / 2 - 1), calc(L / 2 - 1));
    ret = add(ret, mul(2ll * calc(L / 2 - 1), calc(L / 2 - 2)));
    if (ret)
      mem[L] = ret;
    else
      mem[L] = -1;
    return ret;
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k >> l >> m;
  for (int i = 63; i >= 0; i--) {
    if (k & (1ll << i)) {
      if (i >= l) return cout << 0, 0;
      if (i < l) sho++;
    } else if (i < l)
      alt++;
  }
  long long L1 = 1ll, L2 = 1ll;
  for (int i = 0; i < alt; i++) L1 = mul(L1, calc(n));
  for (int i = 0; i < sho; i++) L2 = mul(L2, add(bow(2, n), m - calc(n)));
  cout << mul(L1, L2);
  return 0;
}
