#include <bits/stdc++.h>
using namespace std;
long long n, k;
int l, m;
vector<vector<long long> > mult(vector<vector<long long> >& a,
                                vector<vector<long long> >& b) {
  int n = a.size();
  vector<vector<long long> > c(n, vector<long long>(n, 0));
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      for (int k = 0; k < n; ++k) c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % m;
  return c;
}
vector<vector<long long> > power(vector<vector<long long> >& a, long long p) {
  if (p == 1) return a;
  vector<vector<long long> > c = power(a, p / 2);
  c = mult(c, c);
  if (p & 1) c = mult(c, a);
  return c;
}
long long power2(long long a, long long p) {
  if (p == 0) return 1;
  if (p == 1) return a;
  long long c = power2(a, p / 2);
  c = c * c % m;
  if (p & 1) c = c * a % m;
  return c;
}
int main() {
  scanf("%lld%lld%d%d", &n, &k, &l, &m);
  if (l != 64 && k >> l) {
    printf("0");
    return 0;
  }
  int ones = __builtin_popcount(k);
  ones += __builtin_popcount(k >> 32);
  int zeros = l - ones;
  vector<vector<long long> > x(2, vector<long long>(2, 1));
  x[1][1] = 0;
  long long ans = power(x, n + 3)[1][1];
  long long ans2 = ((power2(2, n) - ans) % m + m) % m;
  printf("%d", power2(ans, zeros) * power2(ans2, ones) % m);
  return 0;
}
