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).
d = {0: 1, 1: 1}

def fib(x, m):
    if x in d:
        return d[x]
    elif x % 2==0:
        x1 = x//2
        x2 = x//2-1
        answer = fib(x1, m)**2+fib(x2, m)**2
        d[x] = answer % m
        return answer % m
    else:
        x1 = x//2+1
        x2 = x//2-1
        answer = fib(x1, m)**2-fib(x2, m)**2
        d[x] = answer % m
        return answer % m
    
    
def process(n, k, l, m):
    b = bin(k)[2:].zfill(l)
    fib1 = fib(n+1, m)
    fib2 = pow(2, n, m)-fib1
    answer = 1
    for i in range(l):
        if b[i]=='0':
            answer = (answer*fib1) % m
        else:
            answer = (answer*fib2) % m
    print(answer)
    
n, k, l, m = [int(x) for x in input().split()]
process(n, k, l, m)
        