#include <bits/stdc++.h>
using namespace std;
unsigned long long A[4][4];
unsigned long long res[4][4];
unsigned long long M;
void pre() {
  for (int val = 0; val < 2; val++) {
    for (int prev = 0; prev < 2; prev++) {
      for (int curr = 0; curr < 2; curr++) {
        int new_val = val | (prev & curr);
        int new_prev = curr;
        A[val * 2 + prev][new_val * 2 + new_prev]++;
      }
    }
  }
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) res[i][j] = (i == j);
  }
  return;
}
void mul(unsigned long long A1[][4], unsigned long long A2[][4]) {
  unsigned long long C[4][4];
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      C[i][j] = 0;
      for (int k = 0; k < 4; k++) {
        C[i][j] = C[i][j] + (A1[i][k] * A2[k][j]) % M;
        if (C[i][j] >= M) C[i][j] -= M;
      }
    }
  }
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) A1[i][j] = C[i][j];
  }
  return;
}
void expo(unsigned long long x) {
  while (x > 0) {
    if (x & 1) mul(res, A);
    mul(A, A);
    x >>= 1;
  }
  return;
}
unsigned long long fast_pow(unsigned long long a, unsigned long long b) {
  unsigned long long res = 1;
  while (b > 0) {
    if (b & 1) res = (res * a) % M;
    a = (a * a) % M;
    b >>= 1;
  }
  return res;
}
int main() {
  unsigned long long n, k, l, ones, zeros, ans_zeros = 0, ans_ones = 0;
  cin >> n >> k >> l >> M;
  unsigned long long val = 1;
  for (unsigned long long i = 1; i <= l; i++) val = val * 2ULL;
  val--;
  if (val < k) {
    puts("0");
    return 0;
  }
  ones = 0;
  while (k > 0) {
    ones += (k % 2 == 1);
    k /= 2;
  }
  zeros = l - ones;
  pre();
  expo(n - 1);
  for (int prev = 0; prev < 2; prev++) {
    ans_zeros = (ans_zeros + res[0 * 2 + prev][0 * 2 + 1] +
                 res[0 * 2 + prev][0 * 2 + 0]) %
                M;
    ans_ones = (ans_ones + res[0 * 2 + prev][1 * 2 + 1] +
                res[0 * 2 + prev][1 * 2 + 0]) %
               M;
  }
  unsigned long long fin_ans = fast_pow(ans_zeros, zeros);
  fin_ans = (fin_ans * fast_pow(ans_ones, ones)) % M;
  cout << fin_ans << endl;
  return 0;
}
