#include <bits/stdc++.h>
using namespace std;
long long n, m, i, k, ans, x, y, a[3][3], c[3][3], d[3][3], l;
void Prepare() {
  long long h, w;
  int i, j, k;
  a[1][1] = 3;
  a[2][1] = 5;
  c[1][1] = 0;
  c[1][2] = 1;
  c[2][1] = 1;
  c[2][2] = 1;
  if (n == 2)
    x = 3;
  else if (n == 3)
    x = 5;
  else {
    h = n - 3;
    while (h) {
      if (h % 2) {
        memset(d, 0, sizeof(d));
        for (i = 1; i <= 2; i++)
          for (j = 1; j <= 2; j++)
            for (k = 1; k <= 2; k++)
              d[i][j] = (d[i][j] + ((c[i][k] * a[k][j]) % m)) % m;
        a[1][1] = d[1][1];
        a[2][1] = d[2][1];
      }
      h >>= 1;
      memset(d, 0, sizeof(d));
      for (i = 1; i <= 2; i++)
        for (j = 1; j <= 2; j++)
          for (k = 1; k <= 2; k++)
            d[i][j] = (d[i][j] + ((c[i][k] * c[k][j]) % m)) % m;
      for (i = 1; i <= 2; i++)
        for (j = 1; j <= 2; j++) c[i][j] = d[i][j];
    }
    x = a[2][1];
  }
  h = n;
  y = 1;
  w = 2;
  while (h) {
    if (h % 2) {
      y = (y * w) % m;
    }
    h >>= 1;
    w = (w * w) % m;
  }
  y = (y + m - x) % m;
}
int main() {
  scanf("%I64d%I64d%I64d%I64d", &n, &k, &l, &m);
  Prepare();
  ans = 0;
  if (l == 64 || ((unsigned long long)1 << l) > k) {
    ans++;
    for (i = 0; i < l; i++)
      if (k & (unsigned long long)1 << i)
        ans = (ans * y) % m;
      else
        ans = (ans * x) % m;
  }
  printf("%I64d\n", ans % m);
  return 0;
}
