#include <bits/stdc++.h>
using namespace std;
unsigned long long n, k, m;
int l;
vector<vector<unsigned long long> > mul(
    vector<vector<unsigned long long> > &a,
    vector<vector<unsigned long long> > &b) {
  vector<vector<unsigned long long> > c(
      a.size(), vector<unsigned long long>(b[0].size()));
  for (int i = 0; i < a.size(); i++)
    for (int k = 0; k < b.size(); k++)
      if (a[i][k] != 0)
        for (int j = 0; j < b[0].size(); j++) {
          c[i][j] += a[i][k] * b[k][j];
          c[i][j] = c[i][j] % m;
        }
  return c;
}
vector<vector<unsigned long long> > pow(vector<vector<unsigned long long> > &a,
                                        unsigned long long tim) {
  vector<vector<unsigned long long> > ans(
      a.size(), vector<unsigned long long>(a[0].size()));
  for (int i = 0; i < a.size(); i++) ans[i][i] = 1;
  while (tim) {
    if (tim & 1) ans = mul(ans, a);
    a = mul(a, a);
    tim = tim >> 1;
  }
  return ans;
}
unsigned long long quickpower(unsigned long long base, unsigned long long tim) {
  unsigned long long ret = 1;
  while (tim) {
    if (tim & 1) ret = (ret * base) % m;
    base = (base * base) % m;
    tim = tim >> 1;
  }
  return ret;
}
int main() {
  cin >> n >> k >> l >> m;
  unsigned long long temp = 1;
  if (l < 60 && k >= (temp << l)) {
    cout << 0 << endl;
    return 0;
  }
  if (m == 1) {
    cout << 0 << endl;
    return 0;
  }
  vector<vector<unsigned long long> > start(1, vector<unsigned long long>(2));
  start[0][0] = 1;
  start[0][1] = 0;
  vector<vector<unsigned long long> > mult(2, vector<unsigned long long>(2));
  mult[0][0] = 1;
  mult[0][1] = 1;
  mult[1][0] = 1;
  mult[1][1] = 0;
  vector<vector<unsigned long long> > nmult = pow(mult, n);
  vector<vector<unsigned long long> > final = mul(start, nmult);
  unsigned long long case0 = (final[0][0] + final[0][1]) % m;
  unsigned long long totcase = quickpower(2, n);
  unsigned long long case1 = (totcase - case0 + m) % m;
  unsigned long long ans = 1;
  for (int i = 0; i < l; i++) {
    unsigned long long type;
    if (i >= 60)
      type = 0;
    else
      type = k & (temp << i);
    if (type)
      ans = (ans * case1) % m;
    else
      ans = (ans * case0) % m;
  }
  cout << ans << endl;
  return 0;
}
