#include <bits/stdc++.h>
using namespace std;
const int maxn = 200;
int mod;
void product(unsigned long long a[][6], unsigned long long b[][6]);
void quick_p_matrix(unsigned long long a[][6], unsigned long long b, int n);
void exgcd(unsigned long long a, unsigned long long b, unsigned long long& d,
           unsigned long long& x, unsigned long long& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    d = a;
  } else {
    exgcd(b, a % b, d, y, x);
    y -= (a / b) * x;
  }
}
unsigned long long Niyuan(unsigned long long number, unsigned long long moder) {
  unsigned long long x, y, d;
  exgcd(number, moder, d, x, y);
  x = (x + moder) % moder;
  return x;
}
unsigned long long Y[maxn][2], N[maxn][2];
unsigned long long ans[maxn];
unsigned long long aa[6][6];
unsigned long long bb[6][6];
unsigned long long tt[] = {
    1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0,
};
void get10(unsigned long long x, int& nn0, int& nn1) {
  nn0 = nn1 = 0;
  while (x) {
    if (x & 1)
      nn1++;
    else
      nn0++;
    x >>= 1;
  }
}
unsigned long long quickP(unsigned long long a, unsigned long long b) {
  unsigned long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return ans;
}
int main() {
  int i, l, j;
  unsigned long long n, k, m;
  cin >> n >> k >> l >> m;
  mod = m;
  int NN0;
  int NN1;
  get10(k, NN0, NN1);
  if (NN0 + NN1 > l) {
    puts("0");
    return 0;
  }
  int cnt = 0;
  for (i = 0; i < 4; i++) {
    for (j = 0; j < 4; j++) aa[i][j] = tt[cnt++];
  }
  quick_p_matrix(aa, n - 2, 4);
  unsigned long long xxx = (aa[0][1] + aa[1][1] + aa[0][3] + aa[1][3] +
                            aa[0][2] * 2 + aa[1][2] * 2) %
                           mod;
  unsigned long long yyy = (quickP(2, n) - xxx + mod) % mod;
  NN0 = l - NN1;
  cout << quickP(xxx, NN1) * quickP(yyy, NN0) % mod << endl;
  return 0;
}
void product(unsigned long long a[][6], unsigned long long b[][6], int n) {
  int i, j, k;
  unsigned long long c[6][6];
  memset(c, 0, sizeof(c));
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      for (k = 0; k < n; k++)
        c[i][j] = (c[i][j] % mod + (a[i][k] % mod) * (b[k][j] % mod)) % mod;
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) a[i][j] = c[i][j];
}
void quick_p_matrix(unsigned long long a[][6], unsigned long long b, int n) {
  int i, k, j;
  unsigned long long res[6][6] = {0};
  for (i = 0; i < n; i++) res[i][i] = 1;
  while (b) {
    if (b & 1) product(res, a, n);
    product(a, a, n);
    b >>= 1;
  }
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) a[i][j] = res[i][j];
}
