#include <bits/stdc++.h>
using namespace std;
const long double PI = 2 * acos(0);
const long double eps = 1e-15;
const int inf = 1e9 + 7;
const long long Linf = (long long)1e18 + 7;
const int MOD = 1e9 + 7;
const int LMAX = 1e6 + 7;
const int MAX = 1e5 + 7;
const int BASE = 1e9 + 7;
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};
struct Matric {
  int r;
  int c;
  long long a[3][3];
} base;
long long N, K, L, M;
Matric multi(Matric A, Matric B) {
  Matric res;
  res.r = A.r;
  res.c = B.c;
  for (int i = (1); i <= (res.r); i++) {
    for (int j = (1); j <= (res.c); j++) {
      res.a[i][j] = 0;
      for (int k = (1); k <= (A.c); k++) {
        res.a[i][j] += A.a[i][k] * B.a[k][j];
        res.a[i][j] %= M;
      }
    }
  }
  return res;
}
Matric pow(Matric A, long long n) {
  if (n == 1) return A;
  Matric p = pow(A, n / 2);
  p = multi(p, p);
  if (n & 1) return multi(p, A);
  return p;
}
long long pow2(long long a) {
  if (a == 0) return 1;
  long long p = pow2(a / 2);
  p *= p;
  p %= M;
  if (a & 1) return p * 2 % M;
  return p;
}
long long fibo(long long n) {
  Matric base;
  base.r = 2;
  base.c = 2;
  base.a[1][1] = 0;
  base.a[1][2] = 1;
  base.a[2][1] = 1;
  base.a[2][2] = 1;
  base = pow(base, n);
  Matric A;
  A.r = 2;
  A.c = 1;
  A.a[1][1] = 1;
  A.a[2][1] = 2;
  A = multi(base, A);
  return A.a[1][1];
}
void solution(long long N, long long K, long long L, long long M) {
  if (M == 1) {
    cout << 0;
    return;
  }
  if (L == 0) {
    if (K == 1)
      cout << 0;
    else
      cout << 1;
    return;
  }
  long long fib = fibo(N);
  long long p = pow2(N);
  long long res = 1;
  for (int i = (1); i <= (L); i++) {
    if (K & 1) {
      res *= p - fib;
    } else {
      res *= fib;
    }
    res %= M;
    if (res < 0) res += M;
    K /= 2;
  }
  if (K > 0)
    cout << 0;
  else
    cout << res;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> N >> K >> L >> M;
  solution(N, K, L, M);
}
