#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
long long const inf = 3e18, linf = 2e9, inf2 = 1e12;
int const mxn = 5e5 + 10;
long long poww(long long a, long long b, long long md) {
  return (!b ? 1
             : (b & 1 ? a * poww(a * a % md, b / 2, md) % md
                      : poww(a * a % md, b / 2, md) % md));
}
long long mod;
struct MAT {
  long long n, m, A[200][200];
  MAT(const long long &n2, const long long &m2) {
    n = n2, m = m2;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++) A[i][j] = 0;
  }
  MAT operator*(const MAT &B) {
    MAT C = MAT(n, m);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        for (int k = 0; k < m; k++) {
          C.A[i][j] = (C.A[i][j] + 1ll * ((A[i][k] % mod + mod) % mod *
                                          (B.A[k][j] % mod + mod) % mod)) %
                      mod;
          if (C.A[i][j] < 0) cout << C.A[i][j] << endl;
        }
      }
    }
    return (C);
  }
  MAT operator+(const MAT &B) {
    MAT C = MAT(n, m);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) C.A[i][j] = (A[i][j] + B.A[i][j]) % mod;
    }
    return (C);
  }
  void printmat() {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) cout << A[i][j] << " ";
      cout << "\n";
    }
  }
  MAT operator^(long long x) {
    MAT R = MAT(n, m);
    for (int i = 0; i < n; i++) R.A[i][i] = 1;
    MAT T = MAT(n, m);
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++) T.A[i][j] = A[i][j];
    while (x > 0) {
      if (x % 2) R = R * T;
      T = T * T;
      x /= 2;
    }
    return R;
  }
};
int main() {
  long long n, k, l;
  cin >> n >> k >> l >> mod;
  if (l < 61 and k >= (((long long)1) << l)) {
    cout << 0;
    return 0;
  }
  MAT M = MAT(2, 2);
  M.A[0][0] = M.A[0][1] = M.A[1][0] = 1;
  M = M ^ (n + 1);
  long long a = M.A[0][0] % mod;
  long long ans = 1;
  long long pw = poww(2, n, mod);
  for (int mask = 0; mask < l; mask++) {
    if (mask <= 61 and k & (((long long)1) << mask))
      ans = (ans * (pw - a) % mod) % mod;
    else
      ans = (ans * (a) % mod) % mod;
  }
  cout << (ans + mod) % mod;
}
