#include <bits/stdc++.h>
struct mat {
  long long m[2][2];
  mat(int a, int b, int c, int d) {
    m[0][0] = a;
    m[0][1] = b;
    m[1][0] = c;
    m[1][1] = d;
  }
  mat() {}
} I(1, 0, 0, 1), fgen(1, 1, 1, 0), temp;
long long N, K, L, M;
void print(mat A) {
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) printf("%lld ", A.m[i][j]);
  printf("\n");
}
mat operator*(mat A, mat B) {
  mat C(0, 0, 0, 0);
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++)
      for (int k = 0; k < 2; k++)
        C.m[i][j] = (C.m[i][j] + A.m[i][k] * B.m[k][j]) % M;
  return C;
}
mat pow(mat A, long long p) {
  if (p == 0) return I;
  mat Ap = pow(A, p / 2);
  Ap = Ap * Ap;
  if (p % 2) Ap = Ap * A;
  return Ap;
}
long long pow(long long A, long long p) {
  if (p == 0) return 1;
  long long Ap = pow(A, p / 2);
  Ap = (Ap * Ap) % M;
  if (p % 2) Ap = (Ap * A) % M;
  return Ap;
}
int main() {
  scanf("%lld %lld %lld %lld", &N, &K, &L, &M);
  long long R = 1, Fp, F, P2;
  temp = pow(fgen, N + 1);
  F = temp.m[0][0];
  P2 = pow(2, N);
  Fp = (M + P2 - F) % M;
  if (L < 1) {
    if (K > 0) R = 0;
    printf("%lld\n", R % M);
    return 0;
  }
  for (long long i = 0; i < L; i++) {
    if (K % 2)
      R = (R * Fp) % M;
    else
      R = (R * F) % M;
    K /= 2;
  }
  if (K) R = 0;
  printf("%lld\n", R);
  return 0;
}
