We all know that GukiZ often plays with arrays. 

Now he is thinking about this problem: how many arrays *a*, of length *n*, with non-negative elements strictly less then 2<sup class="upper-index">*l*</sup> meet the following condition: <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/02bd933699313baffa5788fedb6b21a78354f37e.png" style="max-width: 100.0%;max-height: 100.0%;"/>? Here operation <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/625ed07379e4df241affcda9308db4df81849a5f.png" style="max-width: 100.0%;max-height: 100.0%;"/> means bitwise AND (in Pascal it is equivalent to and, in C/C++/Java/Python it is equivalent to &amp;), operation <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/d8e629dfc5d72ed17b4f7da6266cd97331093ddf.png" style="max-width: 100.0%;max-height: 100.0%;"/> means bitwise OR (in Pascal it is equivalent to <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/d8e629dfc5d72ed17b4f7da6266cd97331093ddf.png" style="max-width: 100.0%;max-height: 100.0%;"/>, in C/C++/Java/Python it is equivalent to |). 

Because the answer can be quite large, calculate it modulo *m*. This time GukiZ hasn't come up with solution, and needs you to help him!
First and the only line of input contains four integers *n*, *k*, *l*, *m* (2 ≤ *n* ≤ 10<sup class="upper-index">18</sup>, 0 ≤ *k* ≤ 10<sup class="upper-index">18</sup>, 0 ≤ *l* ≤ 64, 1 ≤ *m* ≤ 10<sup class="upper-index">9</sup> + 7).
'''
    Python3(PyPy3) Template for Programming-Contest.
'''

import sys
import numpy as np


def input():
    return sys.stdin.readline().rstrip()


DXY = [(0, -1), (1, 0), (0, 1), (-1, 0)]  # LDRU
inf = 1 << 64


mat = np.array([[1, 1], [1, 0]], dtype=np.int64)


def matpow(n: int, mod: int):
    if n == 0:
        return np.eye(2, dtype=np.int64)
    elif n == 1:
        return mat
    else:
        tmp = matpow(n // 2, mod)
        tmp1 = np.dot(tmp, tmp) % mod
        if n & 1:
            tmp1 = np.dot(tmp1, matpow(1, mod)) % mod
        return tmp1 % mod


def slv():
    n, K, L, mod = map(int, input().split())
    powmat = matpow(n - 1, mod)
    tot = pow(2, n, mod)
    zero = int(powmat[0][0] + powmat[0][1] + powmat[1][0] + powmat[1][1])
    if pow(2, L) - 1 < K:
        print(0)
        return 0
    ans = 1
    for bit in range(L):
        if (K >> bit) & 1:
            ans *= (tot - zero)
        else:
            ans *= zero
    print(ans % mod)
    return


def main():
    testcase = 1
    #testcase = int(input())
    for _ in range(testcase):
        slv()
    return 0


if __name__ == "__main__":
    main()
