#include <bits/stdc++.h>
using namespace std;
long long k, l, n, m;
long long binpow(long long a, long long n) {
  if (n == 0) return 1;
  if (n % 2 == 1)
    return (binpow(a, n - 1) * a) % m;
  else {
    long long b = binpow(a, n / 2);
    return (b * b) % m;
  }
}
vector<vector<long long> > gg(vector<vector<long long> > a,
                              vector<vector<long long> > b) {
  vector<vector<long long> > c;
  c.resize(3);
  c[1].resize(3);
  c[2].resize(3);
  for (int k = 1; k <= 2; ++k)
    for (int i = 1; i <= 2; ++i)
      for (int j = 1; j <= 2; ++j) c[k][i] = (c[k][i] + a[k][j] * b[j][i]) % m;
  return c;
}
vector<vector<long long> > first(vector<vector<long long> > a, long long n) {
  if (n == 1) return a;
  vector<vector<long long> > rr = first(a, n / 2);
  rr = gg(rr, rr);
  if (n % 2) {
    return gg(rr, a);
  } else {
    return rr;
  }
}
int main() {
  cin >> n >> k >> l >> m;
  int a0 = 0, a1 = 0;
  while (k > 0) {
    if (k % 2)
      ++a1;
    else
      ++a0;
    k /= 2;
  }
  if (a1 + a0 > l) {
    cout << 0;
    return 0;
  }
  vector<vector<long long> > tt;
  tt.resize(3);
  tt[1].resize(3);
  tt[2].resize(3);
  tt[1][1] = 1;
  tt[1][2] = 1;
  tt[2][1] = 1;
  tt[2][2] = 0;
  vector<vector<long long> > gl = first(tt, n + 1);
  long long ans1 = (gl[1][2] + gl[2][2]) % m;
  long long ans2 = binpow(2, n);
  long long OD = (ans2 - ans1 + m) % m;
  OD = binpow(OD, a1);
  a0 += l - a1 - a0;
  long long LC = binpow(ans1, a0);
  cout << (OD * LC) % m;
  return 0;
}
