#include <bits/stdc++.h>
using namespace std;
unsigned long long power(unsigned long long a, long long b, long long mod) {
  unsigned long long res = 1;
  while (b > 0) {
    if (b & 1) res = (res * a % mod) % mod;
    a = ((a % mod) * (a % mod)) % mod;
    b /= 2;
  }
  return res;
}
vector<vector<unsigned long long> > mul(vector<vector<unsigned long long> > a,
                                        vector<vector<unsigned long long> > b,
                                        long long mod) {
  int l = a[0].size();
  int n = b[0].size();
  int m = a.size();
  vector<vector<unsigned long long> > ans = {{0, 0}, {0, 0}};
  for (int k = 0; k < l; ++k) {
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        ans[i][j] = (ans[i][j] + a[i][k] % mod * b[k][j] % mod) % mod;
      }
    }
  }
  return ans;
}
unsigned long long getFib(long long n, unsigned long long mod) {
  vector<vector<unsigned long long> > res = {{1, 0}, {0, 1}};
  vector<vector<unsigned long long> > a = {{1, 1}, {1, 0}};
  while (n > 0) {
    if (n & 1) res = mul(res, a, mod);
    n /= 2;
    a = mul(a, a, mod);
  }
  return res[0][1];
}
int main() {
  long long n, m, k, l;
  cin >> n >> k >> l >> m;
  if (l < 63 && (1LL << l) <= k) {
    cout << 0LL << endl;
    return (0);
  }
  long long res = 1;
  for (long long i = 0; i < l; ++i) {
    long long r = getFib(n + 2, m);
    if ((k & (1LL << i)) != 0) {
      long long q = (power(2, n, m) % m - r + m) % m;
      res = (res * q) % m;
    } else {
      res = (res * r) % m;
    }
  }
  cout << res % m << endl;
  return (0);
}
