#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:36777216")
const int Nmax = 500100;
const int Direction[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
long long n, k;
int l, m;
long long two = 1;
long long need_fib = 0;
map<long long, long long> F;
long long getFibonnace(long long n) {
  if (n < 2) return 1;
  if (F.find(n) != F.end()) return F[n];
  F[n] = (getFibonnace((n + 1) / 2) * getFibonnace(n / 2)) % m;
  F[n] =
      (F[n] + (getFibonnace((n - 1) / 2) * getFibonnace((n - 2) / 2)) % m) % m;
  return F[n];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> k >> l >> m;
  long long current = 2;
  for (long long deg = n; deg > 0; deg /= 2) {
    if (deg & 1) two = (two * current) % m;
    current = (current * current) % m;
  }
  need_fib = getFibonnace(n + 1);
  two -= need_fib;
  if (two < 0) two += m;
  long long result = 1;
  for (int i = 0; i < 64; i++) {
    if (((k >> i) & 1)) {
      if (i >= l)
        result = 0;
      else
        result = (result * two) % m;
    } else {
      if (i < l) result = (result * need_fib) % m;
    }
  }
  cout << result % m << endl;
  return 0;
}
