#include <bits/stdc++.h>
using namespace std;
long long N, K, L, M;
struct Matrix {
  long long arr[2][2];
  Matrix() { memset(arr, 0, sizeof(arr)); }
  Matrix(int x) {
    arr[0][0] = arr[1][1] = x;
    arr[0][1] = arr[1][0] = 0;
  }
  Matrix operator*(const Matrix &m) const {
    Matrix ans;
    memset(ans.arr, 0, sizeof(ans.arr));
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++)
        for (int k = 0; k < 2; k++) ans.arr[i][j] += arr[i][k] * m.arr[k][j];
    return ans;
  }
  Matrix operator%(const int m) const {
    Matrix ans = *this;
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++) ans.arr[i][j] %= m;
    return ans;
  }
};
template <typename T>
T qpow(T x, long long p) {
  T ans = T(1);
  while (p) {
    if (p & 1) ans = (ans * x) % M;
    x = (x * x) % M;
    p >>= 1;
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> N >> K >> L >> M;
  if (L <= log(K) / log(2)) {
    cout << 0 << endl;
    return 0;
  }
  Matrix fib_mat;
  fib_mat.arr[0][0] = 0;
  fib_mat.arr[0][1] = 1;
  fib_mat.arr[1][0] = 1;
  fib_mat.arr[1][1] = 1;
  long long pow2n = qpow(2ll, N);
  Matrix fib_res = qpow(fib_mat, N);
  long long eq0 = (fib_res.arr[0][1] + fib_res.arr[1][1]) % M;
  long long eq1 = (pow2n + M - eq0) % M;
  int ones = 0;
  while (K) {
    ones += K & 1;
    K >>= 1;
  }
  long long ans = (qpow(eq1, ones) * qpow(eq0, L - ones)) % M;
  cout << ans << endl;
  return 0;
}
