#include <bits/stdc++.h>
using namespace std;
long long bs;
long long n, k, l, p, ans;
long long pw(long long a, long long b) {
  if (b == 0) return 1;
  if (b % 2) return a * pw(a, b - 1) % bs;
  return pw(a * a % bs, b / 2);
}
vector<vector<long long> > one() {
  vector<vector<long long> > res;
  res.resize(2);
  res[0].resize(2);
  res[1].resize(2);
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) res[i][j] = (i == j);
  return res;
}
vector<vector<long long> > mult(vector<vector<long long> > a,
                                vector<vector<long long> > b) {
  vector<vector<long long> > res = one();
  for (int i = 0; i < res.size(); i++)
    for (int j = 0; j < res[i].size(); j++) res[i][j] = 0;
  for (int k = 0; k < 2; k++)
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++)
        res[i][j] += (a[i][k] * b[k][j]), res[i][j] %= bs;
  return res;
}
vector<vector<long long> > fib;
vector<vector<long long> > pw(vector<vector<long long> > a, long long b) {
  if (b == 0) return one();
  if (b % 2) return mult(a, pw(a, b - 1));
  return pw(mult(a, a), b / 2);
}
void show(vector<vector<long long> > v) {
  for (int i = 0; i < v.size(); i++) {
    for (int j = 0; j < v[0].size(); j++) cout << v[i][j] << " ";
    cout << endl;
  }
}
long long get_fib(long long x) {
  vector<vector<long long> > v = pw(fib, x);
  return v[0][1];
}
long long solve1(long long x) { return get_fib(x + 2); }
long long solve2(long long x) { return (pw(2, x) - get_fib(x + 2) + bs) % bs; }
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> k >> l >> bs;
  fib = one();
  fib[1][0] = fib[0][1] = 1;
  fib[1][1] = 0;
  ans = 1;
  for (int i = 0; i < l; i++) {
    if (k & (1ll << i))
      ans *= solve2(n);
    else
      ans *= solve1(n);
    ans %= bs;
  }
  for (int i = l; i < 60; i++)
    if (k & (1ll << i)) ans = 0;
  cout << ans % bs << endl;
  return 0;
}
