import java.util.Scanner;
public class Main {
private Scanner scanner;
private int mod;
private Main(Scanner scanner) {
this.scanner = scanner;
}
public static void main
(String[] args
) { Main main
= new Main
(new Scanner
(System.
in)); main.solve();
}
private void solve() {
long n = scanner.nextLong();
long k = scanner.nextLong();
int l = scanner.nextInt();
mod = scanner.nextInt();
if (mod == 1 || l < 63 && 1l << l <= k) {
return;
}
if (l == 0) {
if (k
== 0) System.
out.
println(1); else
return;
}
long pow2 = fastPower(2, n);
long fib = fibonacci(n + 1);
long res = 1;
for (int i = 0; i < l; i++)
if (((k >> i) & 1) == 0) res = res * fib % mod;
else
res = res * (pow2 - fib) % mod;
if (res < 0) res += mod;
}
private long fibonacci(long n) {
Matrix matrix = new Matrix(new long[][]{{1, 1}, {1, 0}});
matrix = fastPower(matrix, n);
return matrix.matrix[0][0];
}
private long fastPower(long base, long exponent) {
if (exponent == 0) return 1;
long x = fastPower(base, exponent >> 1);
x = x * x % mod;
if ((exponent & 1) != 0) x = x * base % mod;
return x;
}
private Matrix fastPower(Matrix base, long exponent) {
if (exponent == 1) return base;
Matrix x = fastPower(base, exponent >> 1);
x = multiplyMatrix(x, x);
if ((exponent & 1) != 0) x = multiplyMatrix(x, base);
return x;
}
private Matrix multiplyMatrix(Matrix a, Matrix b) {
Matrix matrix = new Matrix();
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
matrix.matrix[i][k] = (matrix.matrix[i][k] + a.matrix[i][j] * b.matrix[j][k]) % mod;
return matrix;
}
private class Matrix {
private long[][] matrix;
public Matrix() {
matrix = new long[2][2];
}
public Matrix(long[][] c) {
matrix = c.clone();
}
}
}