#include <bits/stdc++.h>
using namespace std;
struct matrix {
  long long mat[3][3];
};
int l, a[100];
long long f, fk, mod, ians = 1, n, k, t, p = 2, total = 1;
matrix ans, c;
matrix operator*(matrix a, matrix b) {
  matrix c;
  c.mat[0][0] = c.mat[0][1] = c.mat[1][0] = c.mat[1][1] = 0;
  for (int i = 0; i <= 1; i++)
    for (int j = 0; j <= 1; j++)
      for (int k = 0; k <= 1; k++)
        c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % mod;
  return c;
}
matrix operator^(matrix a, long long b) {
  matrix c;
  c.mat[0][0] = c.mat[1][1] = 1;
  c.mat[0][1] = c.mat[1][0] = 0;
  while (b) {
    if (b & 1) c = c * a;
    b >>= 1;
    a = a * a;
  }
  return c;
}
int main() {
  scanf("%lld%lld%d%lld", &n, &k, &l, &mod);
  t = k;
  while (t) {
    a[++a[0]] = int(t & 1);
    t >>= 1;
  }
  if (l == 0) {
    if (!k && mod != 1)
      printf("1\n");
    else
      printf("0\n");
    return 0;
  }
  if (a[0] > l) {
    printf("0\n");
    return 0;
  }
  t = l;
  ans.mat[0][0] = 1;
  ans.mat[0][1] = 1;
  c.mat[0][0] = c.mat[0][1] = c.mat[1][0] = 1;
  c = c ^ n;
  ans = ans * c;
  f = ans.mat[0][0];
  total = 1;
  p = 2;
  while (n) {
    if (n & 1) total = total * p % mod;
    n >>= 1;
    p = p * p % mod;
  }
  fk = (mod + total - f) % mod;
  for (int i = 1; i <= t; i++)
    if (a[i])
      ians = ians * fk % mod;
    else
      ians = ians * f % mod;
  printf("%lld\n", ians);
  return 0;
}
