#include <bits/stdc++.h>
using namespace std;
long long mpow(long long base, long long exponent, long long mod) {
  long long res = 1;
  while (exponent) {
    if (exponent % 2 == 1) {
      res = (res * base) % mod;
    }
    base = (base * base) % mod;
    exponent = exponent >> 1;
  }
  return res;
}
long long fib(long long n, long long m) {
  long long mat[2][2] = {{0, 1}, {1, 1}};
  long long res[2][2] = {{1, 0}, {0, 1}};
  long long tmp[2][2];
  while (n) {
    if (n % 2 == 1) {
      tmp[0][0] = (res[0][0] * mat[0][0] + res[0][1] * mat[1][0]) % m;
      tmp[0][1] = (res[0][0] * mat[0][1] + res[0][1] * mat[1][1]) % m;
      tmp[1][0] = (res[1][0] * mat[0][0] + res[1][1] * mat[1][0]) % m;
      tmp[1][1] = (res[1][0] * mat[0][1] + res[1][1] * mat[1][1]) % m;
      memcpy(res, tmp, sizeof(tmp));
    }
    tmp[0][0] = (mat[0][0] * mat[0][0] + mat[0][1] * mat[1][0]) % m;
    tmp[0][1] = (mat[0][0] * mat[0][1] + mat[0][1] * mat[1][1]) % m;
    tmp[1][0] = (mat[1][0] * mat[0][0] + mat[1][1] * mat[1][0]) % m;
    tmp[1][1] = (mat[1][0] * mat[0][1] + mat[1][1] * mat[1][1]) % m;
    memcpy(mat, tmp, sizeof(tmp));
    n = n >> 1;
  }
  return (res[0][0] + res[0][1]) % m;
}
int main() {
  ios_base::sync_with_stdio(false);
  long long n, k, l, m;
  cin >> n >> k >> l >> m;
  if ((m == 1) or (l < 63 and ((1LL << l) <= k))) {
    cout << "0\n";
    return 0;
  }
  if (l == 0) {
    if (k == 0) {
      cout << "1\n";
      return 0;
    } else {
      cout << "0\n";
      return 0;
    }
  }
  long long f = fib(n + 1, m);
  long long tp = mpow(2, n, m);
  long long res = 1;
  for (int i = 0; i < l; i++) {
    if (((k >> i) & 1) == 0) {
      res = (f * res) % m;
    } else {
      res = (res * (tp - f)) % m;
    }
  }
  if (res < 0) res += m;
  cout << res << "\n";
  return 0;
}
