#include <bits/stdc++.h>
using namespace std;
struct matrix {
  long long mat[2][2];
};
long long mod;
matrix multiply(matrix a, matrix b) {
  matrix c;
  memset(c.mat, 0, sizeof(c.mat));
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      if (a.mat[i][j] == 0) continue;
      for (int k = 0; k < 2; k++) {
        if (b.mat[j][k] == 0) continue;
        c.mat[i][k] += a.mat[i][j] * b.mat[j][k] % mod;
        if (c.mat[i][k] > mod)
          c.mat[i][k] -= mod;
        else if (c.mat[i][k] < 0)
          c.mat[i][k] += mod;
      }
    }
  }
  return c;
}
matrix quicklymod(matrix a, long long n) {
  matrix res;
  memset(res.mat, 0, sizeof(res.mat));
  for (int i = 0; i < 2; i++) res.mat[i][i] = 1;
  while (n) {
    if (n & 1) res = multiply(a, res);
    a = multiply(a, a);
    n >>= 1;
  }
  return res;
}
long long ppow(long long a, long long b) {
  long long c = 1;
  while (b) {
    if (b & 1) c = c * a % mod;
    b >>= 1;
    a = a * a % mod;
  }
  return c;
}
int main() {
  long long n, k, l, m;
  scanf("%I64d%I64d%I64d%I64d", &n, &k, &l, &mod);
  if (l != 64 && k >= (unsigned long long)(1ULL << l)) {
    printf("0\n");
    return 0;
  }
  matrix ans;
  ans.mat[0][0] = 1;
  ans.mat[0][1] = 1;
  ans.mat[1][0] = 1;
  ans.mat[1][1] = 0;
  ans = quicklymod(ans, n);
  long long x = (ans.mat[0][0] + ans.mat[0][1]) % mod;
  long long y = ((ppow(2, n) - x) % mod + mod) % mod;
  long long sum = 1;
  for (long long i = 0; i < l; i++) {
    if (k & (1LL << i))
      sum = (sum * y) % mod;
    else
      sum = sum * x % mod;
  }
  printf("%I64d\n", sum % mod);
  return 0;
}
