#include <bits/stdc++.h>
using namespace std;
long long n, k, l, m;
struct matrix {
  long long a[3][3];
  void clear() { memset(a, 0, sizeof(a)); }
  void zero() {
    a[1][1] = 0;
    a[1][2] = a[2][1] = a[2][2] = 1;
  }
  void yuan() { a[1][1] = a[2][2] = 1; }
};
matrix time(matrix &a, matrix &b) {
  matrix c, d;
  c.clear();
  for (int i = 1; i <= 2; i++)
    for (int j = 1; j <= 2; j++)
      for (int k = 1; k <= 2; k++)
        c.a[i][j] = (c.a[i][j] + (a.a[i][k] * b.a[k][j]) % m) % m;
  return c;
}
matrix matrixquickpow(matrix &a, long long p) {
  matrix ans;
  ans.clear();
  ans.yuan();
  while (p) {
    if (p & 1) ans = time(ans, a);
    a = time(a, a);
    p = p >> 1;
  }
  return ans;
}
long long quickpow(long long p) {
  long long ans = 1, q = 2;
  while (p) {
    if (p & 1) ans = ans * q % m;
    p = p >> 1;
    q = q * q % m;
  }
  return ans;
}
long long answer() {
  if (l == 0 && k == 1) return 0;
  if (l <= log(k) / log(2)) {
    return 0;
  }
  long long ans = 1, t = quickpow(n);
  matrix a;
  a.zero();
  matrix b;
  b = matrixquickpow(a, n + 3);
  while (l) {
    if (k & 1)
      ans = ans * (t % m + m - b.a[1][1] % m) % m;
    else
      ans = ans * b.a[1][1] % m;
    k = k >> 1;
    l--;
  }
  return ans % m;
}
int main() {
  cin >> n >> k >> l >> m;
  cout << answer() << endl;
  return 0;
}
