#include <bits/stdc++.h>
using namespace std;
long long mod;
long long modExp(long long a, long long b, long long md) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = (ans * a) % md;
    a = (a * a) % md;
    b /= 2;
  }
  return ans;
}
int bit[65];
void copymatrix(long long a[2][2], long long b[2][2], int row, int col) {
  int i, j;
  for (i = 0; i < row; ++i)
    for (j = 0; j < col; ++j) a[i][j] = b[i][j];
}
void multiply(long long a[2][2], long long b[2][2], int row, int col) {
  long long c[2][2];
  int i, j, k;
  for (i = 0; i < row; i++)
    for (j = 0; j < col; ++j) c[i][j] = 0;
  for (i = 0; i < row; i++) {
    for (j = 0; j < col; j++) {
      c[i][j] = 0;
      for (k = 0; k < col; k++) {
        c[i][j] = (c[i][j] + a[i][k] * 1LL * b[k][j] % mod) % mod;
      }
    }
  }
  copymatrix(a, c, row, col);
}
void matpow(long long a[2][2], long long b, int row, int col) {
  long long c[2][2];
  int i, j;
  for (i = 0; i < row; i++)
    for (j = 0; j < col; ++j) c[i][j] = 0;
  for (i = 0; i < col; i++) c[i][i] = 1;
  while (b) {
    if (b & 1) multiply(c, a, row, col);
    multiply(a, a, row, col);
    b /= 2;
  }
  copymatrix(a, c, row, col);
}
long long fib(long long n) {
  long long mat[2][2];
  mat[0][0] = mat[1][0] = mat[0][1] = 1;
  mat[1][1] = 0;
  matpow(mat, n - 1, 2, 2);
  return (mat[0][0] + mat[1][0]) % mod;
}
int main() {
  long long n, k, l, m, i;
  cin >> n >> k >> l >> m;
  mod = m;
  for (i = 0; i <= l - 1; ++i) {
    if (k & (1LL << i)) bit[i] = 1;
  }
  long long ans = 1 % m;
  long long val = 1LL << l;
  if (l < 63 && k >= val) {
    cout << "0\n";
  } else {
    for (i = 0; i <= l - 1; ++i) {
      if (bit[i] == 0) {
        ans = ans * fib(n + 1);
        ans %= m;
      } else {
        ans = ans * (modExp(2LL, n, m) - fib(n + 1));
        ans = (ans % mod + 2 * mod) % mod;
      }
    }
    cout << ans << endl;
  }
}
