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 multiply(x, y):
    global m
    a = (x[0][0] * y[0][0] + x[0][1] * y[1][0]) % m
    b = (x[0][0] * y[0][1] + x[0][1] * y[1][1]) % m
    c = (x[1][0] * y[0][0] + x[1][1] * y[1][0]) % m
    d = (x[1][0] * y[0][1] + x[1][1] * y[1][1]) % m
    return [[a, b], [c, d]]

def seqs(n):
    f = [[1, 1], [1, 0]]
    result = [[1, 0], [0, 1]]
    while n > 0:
        if n % 2 == 1:
            result = multiply(result, f)
            n -= 1
        f = multiply(f, f)
        n //= 2
    return result[0][1]

def power(n):
    global m
    result = 1
    base = 2
    while n > 0:
        if n % 2 == 1:
            result *= base
            n -= 1
        base *= base
        base %= m
        result %= m
        n //= 2
    return result

n, k, l, m = tuple(map(int, input().split()))

if k > 2 ** l:
    print(0)
else:
    answer = 1
    s = seqs(n + 2)
    total = power(n)
    while l > 0:
        if k % 2 == 0:
            answer *= s
        else:
            answer *= total - s
        answer %= m
        k //= 2
        l -= 1

    print(answer)
