#include <bits/stdc++.h>
using namespace std;
unsigned long long n, k, l, m;
void matrixMult(unsigned long long A[2][2], unsigned long long B[2][2]) {
  unsigned long long res[2][2];
  res[0][0] = ((A[0][0] * B[0][0]) % m + (A[0][1] * B[1][0]) % m) % m;
  res[0][1] = ((A[0][0] * B[1][0]) % m + (A[0][1] * B[1][1]) % m) % m;
  res[1][0] = ((A[1][0] * B[0][0]) % m + (A[1][1] * B[1][0]) % m) % m;
  res[1][1] = ((A[1][0] * B[1][0]) % m + (A[1][1] * B[1][1]) % m) % m;
  A[0][0] = res[0][0];
  A[1][0] = res[1][0];
  A[0][1] = res[0][1];
  A[1][1] = res[1][1];
}
void matrixExp(unsigned long long M[2][2], unsigned long long exp) {
  unsigned long long res[2][2] = {{1, 0}, {0, 1}};
  while (exp) {
    if (exp % 2) {
      matrixMult(res, M);
    }
    exp = exp >> 1;
    matrixMult(M, M);
  }
  M[0][0] = res[0][0];
  M[1][0] = res[1][0];
  M[0][1] = res[0][1];
  M[1][1] = res[1][1];
}
unsigned long long fibo(unsigned long long x) {
  if (x < 3) return x + 1;
  unsigned long long A[2] = {1, 2};
  unsigned long long M[2][2] = {{0, 1}, {1, 1}};
  matrixExp(M, x - 1);
  return ((M[1][0] * A[0]) % m + (M[1][1] * A[1]) % m) % m;
}
unsigned long long fastExp(unsigned long long a, unsigned long long exp) {
  unsigned long long res = 1;
  unsigned long long weighted = a;
  while (exp) {
    if (exp % 2) {
      res = (res * weighted) % m;
    }
    exp = (exp >> 1);
    weighted = (weighted * weighted) % m;
  }
  return res;
}
int main() {
  cin >> n >> k >> l >> m;
  unsigned long long maxVal = (1LL << l) - 1;
  if (l < 64 && maxVal < k || (k > 0 && l == 0)) {
    cout << 0 << endl;
    return 0;
  }
  unsigned long long twoToTheN = fastExp(2, n);
  unsigned long long fiboOfN = fibo(n);
  unsigned long long count = 1;
  while (l--) {
    if (k % 2) {
      count = (count * (twoToTheN + m - fiboOfN)) % m;
    } else {
      count = (count * fiboOfN) % m;
    }
    k = k >> 1;
  }
  cout << count % m << endl;
  return 0;
}
