#include <bits/stdc++.h>
using namespace std;
const int MN = 100 * 100 * 100 * 10;
long long n, k, l, m, bit[2];
long long logg(long long t) {
  if (t == 1 || t == 0) return 1;
  return logg(t / 2) + 1;
}
long long pow(long long t) {
  if (t == 0) return 0;
  if (t == 1) return 2;
  long long ret = pow(t / 2);
  ret = ret * ret;
  if (t % 2) ret = ret * 2;
  ret = (long long)ret % m;
  return ret;
}
pair<pair<long long, long long>, pair<long long, long long> > rec(long long t) {
  if (t == 1)
    return make_pair(pair<long long, long long>(1, 0),
                     pair<long long, long long>(0, 1));
  pair<pair<long long, long long>, pair<long long, long long> > tmp1 =
                                                                    rec(t / 2),
                                                                tmp2 = tmp1,
                                                                ret;
  if (t % 2) {
    tmp2.first.first = tmp1.first.first + tmp1.first.second;
    tmp2.first.second = tmp1.first.first;
    tmp2.second.first = tmp1.second.first + tmp1.second.second;
    tmp2.second.second = tmp1.second.first;
  }
  ret.first.first =
      (long long)(tmp1.first.first * (tmp2.first.first + tmp2.second.first) +
                  tmp1.first.second * tmp2.first.first) %
      m;
  ret.first.second =
      (long long)(tmp1.first.first * (tmp2.first.second + tmp2.second.second) +
                  tmp1.first.second * tmp2.first.second) %
      m;
  ret.second.first =
      (long long)(tmp1.second.first * (tmp2.first.first + tmp2.second.first) +
                  tmp1.second.second * tmp2.first.first) %
      m;
  ret.second.second =
      (long long)(tmp1.second.first * (tmp2.first.second + tmp2.second.second) +
                  tmp1.second.second * tmp2.first.second) %
      m;
  return ret;
}
int main() {
  cin >> n >> k >> l >> m;
  pair<pair<long long, long long>, pair<long long, long long> > tmp = rec(n);
  bit[0] = (long long)(tmp.first.first + tmp.first.second + tmp.second.first +
                       tmp.second.second) %
           m;
  bit[1] = (long long)(m + pow(n) - bit[0]) % m;
  if (k == 0 && l == 0) {
    cout << 1 % m;
    return 0;
  }
  if (logg(k) > l) {
    cout << 0;
    return 0;
  }
  long long ans = 1;
  for (long long i = 0; i < l; k /= 2, i++) {
    long long bb = k % 2;
    ans = ans * bit[bb];
    ans = (long long)ans % m;
  }
  cout << ans;
  return 0;
}
