#include <bits/stdc++.h>
using namespace std;
long long n, k, l, M, res = 1;
inline void fix(long long &t) { t = (t + M) % M; }
pair<long long, long long> f(long long n) {
  if (n == 0) return {1, 1};
  if (n & 1) {
    pair<long long, long long> p = f(n - 1);
    p.first += p.second;
    swap(p.first, p.second);
    return p;
  }
  pair<long long, long long> p = f(n / 2 - 1);
  long long x = (((p.first * p.first) % M) + ((p.second * p.second) % M)) % M;
  long long y = (p.second * ((2 * p.first + p.second) % M)) % M;
  return {x, y};
}
long long POW(long long x, long long y) {
  long long r = 1;
  while (y) {
    if (y & 1) r *= x;
    x *= x;
    fix(x), fix(r);
    y /= 2;
  }
  return r;
}
int main() {
  cin >> n >> k >> l >> M;
  if (l <= 60 && (1LL << l) <= k) return cout << 0, 0;
  long long x = f(n + 1).first, y = POW(2, n);
  y -= x;
  fix(y);
  for (int i = 0; i < l; i++)
    if ((1LL << i) & k)
      res *= y, fix(res);
    else
      res *= x, fix(res);
  fix(res);
  cout << res;
  return 0;
}
