#include <bits/stdc++.h>
long long n, k, l, m, ans;
struct mat {
  long long a[3][3];
} A, B;
inline mat operator*(mat x, mat y) {
  mat c;
  memset(c.a, 0, sizeof c.a);
  for (int k = (0), __ = (2); k < __; ++k)
    for (int i = (0), __ = (2); i < __; ++i)
      for (int j = (0), __ = (2); j < __; ++j)
        (c.a[i][j] += (x.a[i][k] * y.a[k][j]) % m) %= m;
  return c;
}
inline mat operator^(mat a, long long y) {
  mat c;
  for (int i = (0), __ = (2); i < __; ++i)
    for (int j = (0), __ = (2); j < __; ++j) c.a[i][j] = (i == j);
  while (y) {
    if (y & 1) c = c * a;
    a = a * a;
    y >>= 1;
  }
  return c;
}
long long Pow(long long x) {
  long long s = 1, c = 2;
  while (x) {
    if (x & 1) s = (s * c) % m;
    c = c * c % m;
    x >>= 1;
  }
  return s;
}
int main() {
  mat p, x;
  p.a[0][0] = 0;
  p.a[0][1] = 1;
  p.a[1][0] = 1;
  p.a[1][1] = 1;
  x.a[0][0] = 1;
  x.a[0][1] = 2;
  x.a[1][0] = 0;
  x.a[1][1] = 0;
  std::cin >> n >> k >> l >> m;
  ans = 0;
  if (l == 64 || (1ull << l) > k) {
    ++ans;
    p = p ^ n;
    x = x * p;
    long long t1 = x.a[0][0];
    long long t2 = (m + Pow(n) - t1) % m;
    for (int i = (0), __ = (l); i < __; ++i) {
      if (k & (1ull << i))
        ans = ans * t2 % m;
      else
        ans = ans * t1 % m;
    }
  }
  std::cout << ans % m << std::endl;
  return 0;
}
