#include <bits/stdc++.h>
using namespace std;
long long n, k, l, m;
struct node {
  int A[2][2];
  int n, m;
  void build(int N, int M) {
    n = N;
    m = M;
    A[0][0] = 1;
    A[0][1] = 1;
    A[1][0] = 1;
    A[1][1] = 0;
  }
};
node operator*(const node& a, const node& b) {
  node c;
  c.build(a.n, b.m);
  for (int i = 0; i < a.n; i++) {
    for (int j = 0; j < b.m; j++) {
      long long res = 0;
      for (int k = 0; k < a.m; k++) res += (long long)a.A[i][k] * b.A[k][j] % m;
      c.A[i][j] = res % m;
    }
  }
  return c;
}
int po(int x, long long n) {
  int ans = 1;
  int t = x;
  while (n) {
    if (n & 1) ans = (long long)ans * t % m;
    t = (long long)t * t % m;
    n >>= 1;
  }
  return ans;
}
int main() {
  cin >> n >> k >> l >> m;
  node a, b;
  a.build(2, 2);
  b.build(2, 2);
  b.A[0][0] = 1;
  b.A[0][1] = 0;
  b.A[1][0] = 0;
  b.A[1][1] = 1;
  long long N = n;
  n--;
  while (n) {
    if (n & 1) b = b * a;
    a = a * a;
    n >>= 1;
  }
  long long res = 0;
  res = ((long long)b.A[0][0] + b.A[0][1] + b.A[1][0] + b.A[1][1]) % m;
  long long res2 = po(2, N);
  res2 = res2 - res;
  if (res2 < 0) res2 += m;
  for (int i = l; i <= 62; i++) {
    if ((1LL << i) & k) {
      printf("0\n");
      return 0;
    }
  }
  int ans = 1;
  for (int i = 0; i < l; i++) {
    if ((1LL << i) & k) {
      ans = (long long)ans * res2 % m;
    } else
      ans = (long long)ans * res % m;
  }
  printf("%d\n", ans % m);
  return 0;
}
