#include <bits/stdc++.h>
using namespace std;
long long n, k, m;
int l;
long long ksm(long long x, long long y) {
  long long ans = 1;
  while (y) {
    if (y & 1) ans = ans * x % m;
    x = x * x % m;
    y >>= 1;
  }
  return ans;
}
struct mat {
  long long a[2][2];
};
mat mat1 = {1, 1, 0, 0};
mat mat2 = {0, 1, 1, 1};
mat multi(mat a, mat b) {
  mat c;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) c.a[i][j] = 0;
  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.a[i][k] * b.a[k][j]) % m;
  return c;
}
mat pow(mat a, long long y) {
  mat ans;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) ans.a[i][j] = 0;
  for (int i = 0; i < 2; i++) ans.a[i][i] = 1;
  while (y) {
    if (y & 1) ans = multi(ans, a);
    a = multi(a, a);
    y >>= 1;
  }
  return ans;
}
long long mul_mod(long long a, long long b) {
  long long ret = 0;
  while (b) {
    if (b & 1) ret = (ret + a) % m;
    a = a * 2 % m;
    b >>= 1;
  }
  return ret;
}
int main() {
  cin >> n >> k >> l >> m;
  long long ans = 1;
  mat2 = pow(mat2, n);
  mat1 = multi(mat1, mat2);
  long long ans0 = mat1.a[0][1];
  long long ans1 = (ksm(2, n) - ans0 + m) % m;
  int flag = 0;
  if ((((long long)1 << l) - 1) < k && l <= 62) {
    cout << "0" << endl;
  } else {
    for (int i = 0; i < l; i++) {
      if ((((long long)1 << i) & k))
        ans = mul_mod(ans, ans1);
      else
        ans = mul_mod(ans, ans0);
    }
    if (l == 0 && k == 0)
      cout << 1 % m << endl;
    else if (l == 0 && k != 0)
      cout << 0 % m << endl;
    else
      cout << ans % m << endl;
  }
  return 0;
}
