#include <bits/stdc++.h>
using namespace std;
unsigned long long int n, k, l, m, ans, cur_pow, cur_fib, border;
int bit[70], cnt;
void multiply(unsigned long long int F[2][2], unsigned long long int M[2][2]) {
  unsigned long long int x = (F[0][0] * M[0][0] + F[0][1] * M[1][0]) % m;
  unsigned long long int y = (F[0][0] * M[0][1] + F[0][1] * M[1][1]) % m;
  unsigned long long int z = (F[1][0] * M[0][0] + F[1][1] * M[1][0]) % m;
  unsigned long long int w = (F[1][0] * M[0][1] + F[1][1] * M[1][1]) % m;
  F[0][0] = x;
  F[0][1] = y;
  F[1][0] = z;
  F[1][1] = w;
}
void power(unsigned long long int F[2][2], unsigned long long int n) {
  if (n == 0 || n == 1) return;
  unsigned long long int M[2][2] = {{1, 1}, {1, 0}};
  power(F, n / 2);
  multiply(F, F);
  if (n % 2 != 0) multiply(F, M);
}
unsigned long long int fibo_matrix(unsigned long long int n) {
  unsigned long long int F[2][2] = {{1, 1}, {1, 0}};
  if (n == 0) return 0;
  power(F, n - 1);
  return F[0][0];
}
unsigned long long int build_pow_mod(unsigned long long int base,
                                     unsigned long long int exp) {
  if (exp == 0)
    return 1;
  else if (exp == 1)
    return base;
  else if (exp % 2 == 0) {
    unsigned long long int tmp = build_pow_mod(base, exp / 2);
    return tmp * tmp % m;
  } else if (exp % 2 == 1) {
    return 2 * build_pow_mod(base, exp - 1) % m;
  }
}
unsigned long long int build_pow(unsigned long long int base,
                                 unsigned long long int exp) {
  if (exp == 0)
    return 1;
  else if (exp == 1)
    return base;
  else if (exp % 2 == 0) {
    unsigned long long int tmp = build_pow(base, exp / 2);
    return tmp * tmp;
  } else if (exp % 2 == 1) {
    return 2 * build_pow(base, exp - 1);
  }
}
int main(void) {
  while (4 == scanf("%llu %llu %llu %llu", &n, &k, &l, &m)) {
    memset(bit, 0, sizeof(bit));
    cur_pow = build_pow_mod(2, n);
    cur_fib = fibo_matrix(n + 2);
    cnt = 0;
    ans = 1;
    unsigned long long int tmp = k;
    while (tmp > 0) {
      bit[cnt++] = tmp % 2;
      tmp /= 2;
    }
    border = build_pow(2, l) - 1;
    if (border >= k && m != 1 || l == 64) {
      for (int i = 0; i < l; i++) {
        if (bit[i] == 0) {
          ans = (ans * cur_fib) % m;
        } else {
          ans = (ans * (cur_pow - cur_fib + m)) % m;
        }
      }
      printf("%llu\n", ans);
    } else {
      printf("0\n");
    }
  }
  return 0;
}
