#include <bits/stdc++.h>
using namespace std;
int m;
long long pow(long long base, long long exp) {
  if (exp == 0)
    return 1ll;
  else if (exp == 1)
    return base;
  else {
    long long half = pow(base, exp / 2);
    long long x = (half * half) % m;
    if (exp % 2 == 1)
      return (x * base) % m;
    else
      return x;
  }
}
struct Matrix {
  long long data[2][2];
};
Matrix multiply(Matrix a, Matrix b) {
  Matrix c;
  c.data[0][0] = c.data[1][1] = c.data[0][1] = c.data[1][0] = 0;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++)
      for (int k = 0; k < 2; k++)
        c.data[i][k] = (c.data[i][k] + a.data[i][j] * b.data[j][k]) % m;
  return c;
}
Matrix power(Matrix base, long long exp) {
  if (exp == 1) {
    return base;
  } else {
    Matrix m = power(base, exp / 2);
    Matrix m2 = multiply(m, m);
    if (exp % 2 == 1)
      return multiply(m2, base);
    else
      return m2;
  }
}
int main() {
  long long n, k, l;
  cin >> n >> k >> l >> m;
  if (m == 1 || ((1ll << l) <= k && l < 63)) {
    cout << 0;
    return 0;
  }
  if (l == 0) {
    if (k == 0)
      cout << 1;
    else
      cout << 0;
    return 0;
  }
  Matrix base;
  base.data[0][0] = base.data[0][1] = base.data[1][0] = 1;
  base.data[1][1] = 0;
  Matrix f = power(base, n + 1);
  long long fib = f.data[0][0];
  long long lim = pow(2ll, n);
  long long rs = 1;
  for (int i = 0; i < l; i++) {
    if (((k >> i) & 1) == 0)
      rs = rs * fib % m;
    else
      rs = rs * (lim - fib) % m;
  }
  if (rs < 0) rs += m;
  cout << rs;
  return 0;
}
