#include <bits/stdc++.h>
using namespace std;
long long int modi(long long int x, long long int y, long long int p) {
  x = x % p;
  long long int c = 1;
  if (x == 1 || y == 0) {
    return 1;
  }
  while (y != 1) {
    if (y % 2 == 0) {
      x = x * x;
      x = x % p;
    } else {
      c = c * x;
      c = c % p;
      x = x * x;
      x = x % p;
    }
    y = y / 2;
  }
  return (c * x) % p;
}
long long int count(long long int n) {
  if (n == 0) {
    return 1;
  }
  long long int c = 0;
  while (n != 0) {
    n = n / 2;
    ++c;
  }
  return c;
}
void multiply(long long int a[2][2], long long int b[2][2], long long int p) {
  long long int c[2][2];
  long long int sum = 0;
  for (long long int i = 0; i <= 1; i++) {
    for (long long int k = 0; k <= 1; k++) {
      for (long long int j = 0; j <= 1; j++) {
        sum = sum + ((a[i][j] % p) * (b[j][k] % p)) % p;
        sum = sum % p;
      }
      c[i][k] = sum;
      sum = 0;
    }
  }
  for (long long int i = 0; i <= 1; i++) {
    for (long long int j = 0; j <= 1; j++) {
      a[i][j] = c[i][j];
    }
  }
}
void power(long long int f[2][2], long long int m[2][2], long long int n,
           long long int p) {
  if (n == 0 || n == 1) {
    return;
  }
  power(f, m, n / 2, p);
  multiply(f, f, p);
  if (n % 2 != 0) {
    multiply(f, m, p);
  }
}
long long int calci(long long int n, long long int p) {
  long long int t1[2][2] = {{1, 1}, {1, 0}};
  long long int t2[2][2] = {{1, 1}, {1, 0}};
  if (n == 0) {
    return 1;
  } else if (n == 1) {
    return 1;
  } else if (n == 2) {
    return 2;
  } else {
    power(t1, t2, n - 2, p);
    return (2 * t1[0][0] + t1[0][1]) % p;
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long int n, k, l, p, jp;
  cin >> n >> k >> l >> p;
  jp = count(k);
  if (k == 0 && l == 0) {
    cout << 1 % p;
  } else if (jp <= l) {
    long long int ans = 1;
    for (long long int i = 1; i <= l; i++) {
      long long int x = (k / (long long int)pow(2, i - 1)) % 2;
      long long int ans1 = 0;
      if (x == 0) {
        if (n == 2) {
          ans1 = 3;
        } else {
          long long int f1 = calci(n - 1, p);
          long long int f2 = calci(n - 2, p);
          ans1 = 2 * f1 + f2;
          ans1 = ans1 % p;
        }
      } else {
        if (n == 2) {
          ans1 = 1;
        } else {
          long long int f1 = calci(n - 1, p);
          long long int f2 = calci(n - 2, p);
          ans1 = 2 * f1 + f2;
          ans1 = ans1 % p;
          ans1 = modi(2, n, p) - ans1;
          if (ans1 >= 0) {
            ans1 = ans1 % p;
          } else {
            ans1 = (p - (abs(ans1) % p));
          }
        }
      }
      ans = ans * ans1;
      ans = ans % p;
    }
    cout << ans;
  } else {
    cout << 0;
  }
}
