#include <bits/stdc++.h>
using namespace std;
std::vector<size_t> RepresentInBaseTwo(unsigned long long num) {
  std::vector<size_t> ans;
  size_t cur = 0;
  while (num) {
    if (num & 1) {
      ans.push_back(cur);
    }
    num >>= 1;
    ++cur;
  }
  return ans;
}
unsigned long long BinPow(unsigned long long base, unsigned long long exponent,
                          unsigned long long modulo) {
  unsigned long long res = 1;
  while (exponent) {
    if (exponent & 1) {
      res = (res * base) % modulo;
    }
    base = (base * base) % modulo;
    exponent >>= 1;
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(7);
  unsigned long long n, k, m;
  size_t l;
  std::cin >> n >> k >> l >> m;
  vector<unsigned long long> a(100, 0);
  vector<unsigned long long> b(100, 0);
  vector<unsigned long long> c(100, 0);
  a[0] = c[0] = a[1] = b[1] = 1 % m;
  for (size_t i = 2; i < 100; ++i) {
    a[i] = a[i - 1] * a[i - 1] + a[i - 1] * b[i - 1] * 2;
    b[i] = a[i - 1] * b[i - 1] + a[i - 1] * c[i - 1] + b[i - 1] * b[i - 1];
    c[i] = b[i - 1] * b[i - 1] + b[i - 1] * c[i - 1] * 2;
    a[i] %= m;
    b[i] %= m;
    c[i] %= m;
  }
  if (k > 0 && log2(k) >= l) {
    std::cout << 0;
    return 0;
  }
  auto degrees = RepresentInBaseTwo(n);
  auto zero = (a[degrees[0]] + b[degrees[0]]) % m,
       one = (b[degrees[0]] + c[degrees[0]]) % m;
  for (size_t i = 1; i < degrees.size(); i++) {
    auto oldzero = zero, oldone = one;
    zero = ((oldzero * a[degrees[i]] % m + oldzero * b[degrees[i]] % m) % m +
            oldone * a[degrees[i]] % m) %
           m;
    one = ((oldzero * b[degrees[i]] % m + oldzero * c[degrees[i]] % m) % m +
           oldone * b[degrees[i]] % m) %
          m;
  }
  auto ans_zero = (one + zero) % m;
  auto ans_one = (BinPow(2, n, m) + m - ans_zero) % m;
  auto num_of_ones = RepresentInBaseTwo(k).size();
  auto num_of_zeros = l - num_of_ones;
  std::cout << BinPow(ans_zero, num_of_zeros, m) *
                   BinPow(ans_one, num_of_ones, m) % m
            << std::endl;
  return 0;
}
