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).
def main():
    def multiply(A, B):
        C = [[0] * len(B[0]) for i in range(len(A))]
        for i in range(len(A)):
            for j in range(len(B[0])):
                C[i][j] = sum(A[i][k] * B[k][j] for k in range(len(B))) % MOD
        return C
    
    def mat_power(A, p):
        if p == 1:
            return A
        if p % 2 == 1:
            return multiply(mat_power(A, p - 1), A)
        return mat_power(multiply(A, A), p / 2)
    
    def power(x, p):
        if p == 0:
            return 1
        if p % 2 == 1:
            return x * power(x, p - 1) % MOD
        return power(x * x % MOD, p / 2) % MOD
    
    n, k, l, MOD = [int(i) for i in input().split()]
    
    d0 = multiply(mat_power([[1, 1], [1, 0]], n), [[1], [1]])[0][0]
    d1 = ((power(2, n) - d0) % MOD + MOD) % MOD
    
    ones = 0
    for i in range(l):
        ones += k & 1
        k >>= 1
    
    print(power(d1, ones) * power(d0, l - ones) % MOD)
    
    
main()
