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).
from math import comb

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


sus = bin(k)[2:]
bits = sus.count("1")

import sys

sys.setrecursionlimit(1000000000)
d = dict()

def fib(x):
    if x in d: return d[x]
    if x==0: return 0
    if x==1: return 1
    if x==2: return 1

    if x%2==0:
        d[x] = (fib(x//2-1) + fib(x//2+1))*fib(x//2) % m
        return d[x]
    else:
        d[x] = fib(x//2)**2 + fib(x//2+1)**2 % m
        return d[x]


ans = 1
ans *= pow(fib(n+2), l-bits, m)
ans *= pow(2**n-fib(n+2), bits, m)
print(ans%m)
