#include <bits/stdc++.h>
using namespace std;
long long n, k, l, mod;
struct mat {
  long long n, m;
  long long M[3][3];
  long long* operator[](long long x) { return M[x]; }
  mat() { memset(M, 0, sizeof M); }
};
mat test, A, B, iden;
mat zar(mat a, mat b) {
  mat ans;
  ans.n = a.n, ans.m = b.m;
  for (long long i = 0; i < ans.n; i++)
    for (long long k = 0; k < a.m; k++)
      for (long long j = 0; j < ans.m; j++)
        ans[i][j] = (1ll * ans[i][j] + 1ll * a[i][k] * b[k][j]) % mod;
  return ans;
}
mat pw(mat a, long long b) {
  if (!b) return iden;
  if (b == 1) return a;
  mat ans = pw(a, b >> 1);
  ans = zar(ans, ans);
  if (b & 1) ans = zar(ans, a);
  return ans;
}
long long my_pw(long long x) {
  if (x == 0) return 1;
  long long ans = my_pw(x >> 1);
  ans = (1ll * ans * ans) % mod;
  if (x & 1) ans = (1ll * ans * 2) % mod;
  return ans;
}
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> k >> l >> mod;
  if (l <= 60 && (1ll << min((long long)60, l)) <= k) return cout << "0\n", 0;
  B.n = 2, B.m = 1, B[0][0] = 1, B[1][0] = 0;
  A.n = 2, A.m = 2, A[0][0] = 1, A[0][1] = 1, A[1][0] = 1, A[1][1] = 0;
  iden.n = 2, iden.m = 2, iden[0][0] = 1, iden[1][1] = 1;
  test = zar(pw(A, n + 1), B);
  long long num1 = test[0][0], num2 = (my_pw(n) - num1 + 2 * mod) % mod,
            ans = 1;
  for (long long i = 0; i < l; i++) {
    if (k & 1ll << i)
      ans = (1ll * ans * num2) % mod;
    else
      ans = (1ll * ans * num1) % mod;
  }
  cout << ans % mod << '\n';
  return 0;
}
