#include <bits/stdc++.h>
using namespace std;
long long m;
class matrix {
 public:
  long long a[2][2];
  matrix() {
    a[0][0] = a[1][1] = 1;
    a[1][0] = a[0][1] = 0;
  }
  ~matrix(){};
  matrix operator*(matrix &t) {
    matrix tmp;
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        tmp.a[i][j] = (a[i][0] * t.a[0][j]) % m + (a[i][1] * t.a[1][j]) % m;
        tmp.a[i][j] %= m;
      }
    }
    return tmp;
  }
};
matrix m_qpow(matrix &a, long long n) {
  matrix ret, tmp;
  tmp = a;
  while (n) {
    if (n & 1) ret = ret * tmp;
    tmp = tmp * tmp;
    n >>= 1;
  }
  return ret;
}
long long qpow(long long a, long long n) {
  long long ret = 1, tmp = a;
  while (n) {
    if (n & 1) ret = (ret * tmp) % m;
    tmp = (tmp * tmp) % m;
    n >>= 1;
  }
  return ret;
}
int main() {
  long long n, k, l, ans;
  cin >> n >> k >> l >> m;
  ans = 1;
  matrix a;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) a.a[i][j] = 1;
  a.a[1][1] = 0;
  a = m_qpow(a, n + 1);
  long long t1, t2;
  t1 = a.a[0][0];
  t2 = (qpow(2, n) - t1 + m) % m;
  for (int i = 0; i < l; i++) {
    if (k & 1) {
      ans *= t2;
      ans %= m;
    } else {
      ans *= t1;
      ans %= m;
    }
    k >>= 1;
  }
  ans %= m;
  if (k) ans = 0;
  cout << ans << endl;
  return 0;
}
