#include <bits/stdc++.h>
using namespace std;
const long long inf = 1000000000000000000LL;
const double EPS = 1e-9;
const long long mod = 1000000007ll;
const int maxn = 300500;
long long m;
long long pow_mod(long long base, long long power) {
  long long res = 1;
  while (power) {
    if (power & 1) res = res * base % m;
    base = base * base % m;
    power >>= 1;
  }
  return res;
}
struct matrix {
  long long a[2][2];
  matrix() { memset(a, 0, sizeof(a)); }
  matrix operator*(const matrix &p) {
    matrix c;
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++)
        for (int k = 0; k < 2; k++)
          c.a[i][j] = (c.a[i][j] + a[i][k] * p.a[k][j]) % m;
    return c;
  }
};
matrix pow(long long n, matrix t) {
  if (n == 1) return t;
  if (n & 1LL) return pow(n / 2, t * t) * t;
  return pow(n / 2, t * t);
}
int main() {
  long long n, k, l;
  scanf("%lld%lld%lld%lld", &n, &k, &l, &m);
  if ((l < 63 && k >= (1LL << l)) || m == 1) {
    puts("0");
    return 0;
  }
  matrix a;
  a.a[0][1] = a.a[1][0] = a.a[1][1] = 1;
  a = pow(n + 2, a);
  long long ret = 1;
  for (int i = 0; i < (int)(l); ++i) {
    long long cur = 1;
    if (k & (1LL << i))
      cur = pow_mod(2, n) - a.a[0][1];
    else
      cur = a.a[0][1];
    cur += m;
    cur %= m;
    ret = (ret * cur) % m;
  }
  printf("%lld", ret);
}
