#include <bits/stdc++.h>
long long mod;
long long exp(long long a, long long b) {
  long long res = 1;
  long long a_generated = a;
  for (long long i = 1; i <= b; i *= 2) {
    if (i & b) {
      res *= a_generated;
      res %= mod;
    }
    a_generated *= a_generated;
    a_generated %= mod;
  }
  return res;
}
long long fib(long long n) {
  std::vector<std::vector<long long>> res = {{1, 1}, {1, 0}};
  std::vector<std::vector<long long>> temp = {{1, 1}, {1, 0}};
  for (long long i = 1; i <= n; i *= 2) {
    if (i & n) {
      auto new_v = res;
      for (int j = 0; j < 2; j++) {
        for (int k = 0; k < 2; k++) {
          new_v[j][k] = 0;
          for (int l = 0; l < 2; l++) {
            new_v[j][k] += res[j][l] * temp[l][k];
            new_v[j][k] %= mod;
          }
        }
      }
      res = new_v;
    }
    auto new_v = res;
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 2; k++) {
        new_v[j][k] = 0;
        for (int l = 0; l < 2; l++) {
          new_v[j][k] += temp[j][l] * temp[l][k];
          new_v[j][k] %= mod;
        }
      }
    }
    temp = new_v;
  }
  return res[1][1];
}
int main() {
  long long n, k, l;
  std::cin >> n >> k >> l >> mod;
  long long max = 1;
  long long ones = 0;
  long long zeroes = 0;
  for (int i = 0; i < l; i++) {
    if (max & k) {
      ones++;
    } else {
      zeroes++;
    }
    if (max > k) {
      zeroes += l - i - 1;
      break;
    }
    max *= 2;
  }
  if (max <= k or mod == 1) {
    std::cout << 0 << std::endl;
    return 0;
  }
  long long res = 1;
  long long zero_fib = fib(n + 2);
  for (int i = 0; i < zeroes; i++) {
    res *= zero_fib;
    res %= mod;
  }
  long long one_fib = exp(2, n) - zero_fib;
  if (one_fib < 0) {
    one_fib += mod;
  }
  for (int i = 0; i < ones; i++) {
    res *= one_fib;
    res %= mod;
  }
  std::cout << res << std::endl;
}
