#include <bits/stdc++.h>
const char en = '\n';
using namespace std;
unsigned long long prv;
vector<vector<unsigned long long> > mul(vector<vector<unsigned long long> > V,
                                        vector<vector<unsigned long long> > M,
                                        int n) {
  vector<vector<unsigned long long> > R(n, vector<unsigned long long>(n, 0));
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      for (int k = 0; k < n; k++) {
        R[i][j] += V[i][k] * M[k][j];
        R[i][j] %= prv;
      }
  return R;
}
int main() {
  ios::sync_with_stdio(false);
  unsigned long long n, k, l, m;
  cin >> n >> k >> l >> prv;
  unsigned long long l2 = 1;
  l2 = l2 << (min(l, (unsigned long long)63));
  if (k >= l2) {
    cout << "0" << en;
    return 0;
  }
  unsigned long long pocet11 = 0;
  unsigned long long pocetx1 = 0;
  vector<vector<unsigned long long> > X(3, vector<unsigned long long>(3, 0));
  X[0][0] = 1;
  X[0][1] = 1;
  X[1][0] = 1;
  X[2][1] = 1;
  X[2][2] = 2;
  vector<vector<unsigned long long> > M(3, vector<unsigned long long>(3, 0));
  M[0][0] = 1;
  M[1][1] = 1;
  M[2][2] = 1;
  unsigned long long x = n;
  while (x) {
    if (x % 2) {
      M = mul(M, X, 3);
    }
    X = mul(X, X, 3);
    x /= 2;
  }
  pocet11 = M[2][0] % prv;
  pocetx1 = (M[0][0] + M[1][0]) % prv;
  unsigned long long suc = 1;
  for (unsigned long long i = 0; i < l; i++) {
    if ((k & (1LL << i)) != 0)
      suc *= pocet11;
    else
      suc *= pocetx1;
    suc %= prv;
  }
  cout << suc % prv << en;
}
