#include <bits/stdc++.h>
using namespace std;
long long int n, k, l, md;
long long int bpow(long long int x, long long int n) {
  long long int ans = 1;
  while (n > 0) {
    if (n & 1) ans *= x;
    x *= x;
    ans %= md;
    x %= md;
    n /= 2;
  }
  return ans;
}
struct matrix {
  long long int m[3][3];
  matrix() {
    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) m[i][j] = 0;
    }
  }
} mat;
matrix mul(matrix a, matrix b) {
  matrix c;
  for (int i = 1; i <= 2; ++i) {
    for (int j = 1; j <= 2; ++j) {
      c.m[i][j] = 0;
      for (int p = 1; p <= 2; ++p) {
        c.m[i][j] = (c.m[i][j] + a.m[i][p] * b.m[p][j]) % md;
      }
    }
  }
  return c;
}
matrix pow(matrix base, long long int exponent) {
  matrix result;
  for (int i = 1; i <= 2; i++) {
    for (int j = 1; j <= 2; j++) result.m[i][j] = 0;
  }
  for (int i = 1; i <= 2; ++i) result.m[i][i] = 1;
  while (exponent > 0) {
    if (exponent % 2 == 1) result = mul(result, base);
    exponent = exponent >> 1;
    base = mul(base, base);
  }
  return result;
}
int main() {
  ios::sync_with_stdio(false);
  ;
  cin.tie(0);
  ;
  cin >> n >> k >> l >> md;
  long long int i, j, ans, res = 0;
  if (n == 1)
    ans = 2;
  else if (n == 2)
    ans = 3;
  else {
    mat.m[1][1] = 0;
    mat.m[1][2] = 1;
    mat.m[2][1] = 1;
    mat.m[2][2] = 1;
    mat = pow(mat, n - 2);
    ans = (2 * mat.m[2][1] + 3 * mat.m[2][2]) % md;
  }
  res = 1;
  for (i = 0; i < l; i++) {
    if (k & (1LL << i))
      res *= (bpow(2, n) - ans + md) % md;
    else
      res *= ans;
    res %= md;
    if (res < 0) res += md;
  }
  for (i = l; i <= 63; i++) {
    if (k & (1LL << i)) {
      cout << "0";
      return 0;
    }
  }
  res = res % md;
  cout << res;
  return 0;
}
