#include <bits/stdc++.h>
using namespace std;
const int maxN = 2e2 + 5;
const long long INF = 1e18;
long long MOD = 1e9 + 7;
long long gcd(long long a, long long b) { return !b ? a : gcd(b, a % b); }
long long sq(long long x) { return (x * x) % MOD; }
long long modP(long long a, long long b) {
  return (!b ? 1 : (sq(modP(a, b / 2)) * (b % 2 ? a : 1)) % MOD);
}
struct Matrix {
  int M[maxN][maxN];
  int n, m;
  Matrix(int a, int b) {
    n = a;
    m = b;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++) M[i][j] = 0;
  }
  int* operator[](int i) { return M[i]; }
  Matrix operator*(const Matrix& A) {
    Matrix R(n, A.m);
    for (int i = 0; i < n; i++) {
      for (int k = 0; k < m; k++) {
        for (int j = 0; j < A.m; j++) {
          R[i][j] = (R[i][j] + (1ll * M[i][k] * A.M[k][j]) % MOD) % MOD;
        }
      }
    }
    return R;
  }
  Matrix operator^(const long long tmp) {
    Matrix R(n, m);
    Matrix T = *this;
    long long pw = tmp;
    for (int i = 0; i < n; i++) R[i][i] = 1;
    for (; pw; pw >>= 1, T = T * T)
      if (pw & 1) R = R * T;
    return R;
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  Matrix F(2, 2);
  F[0][0] = F[0][1] = F[1][0] = 1;
  long long n, k, l;
  cin >> n >> k >> l >> MOD;
  long long len = (k ? 64 - __builtin_clzll(k) : 0);
  long long cnt = (k ? __builtin_popcountll(k) : 0);
  if (len > l) return cout << 0 << endl, 0;
  long long P = modP(2, n);
  n++;
  F = F ^ n;
  long long res = modP(F[0][0], l - cnt);
  res = (res * modP((P - F[0][0] + MOD) % MOD, cnt)) % MOD;
  cout << res << endl;
  return 0;
}
