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).
n,k,l,MOD = map(int, input().split())

class Matrix:
    def __init__(self, a,b,c,d):
        self.a, self.b, self.c, self.d = a,b,c,d
    def __mul__(self, other):
        return Matrix(
                      (self.a * other.a + self.b * other.c) % MOD, 
                      (self.a * other.b + self.b * other.d) % MOD,
                      (self.c * other.a + self.d * other.c) % MOD,
                      (self.c * other.b + self.d * other.d) % MOD
                     ) 


def bin_pow(base, deg):
    if deg == 0:
        return Matrix(1,0,0,1)
    tmp = bin_pow(base, deg // 2)
    tmp =  tmp * tmp
    if deg % 2 == 1:
        tmp *= base
    return tmp

def Fib(n):
    return bin_pow(Matrix(1,1,1,0), n).b

without_set = Fib(n+2)
with_set = (pow(2, n, MOD) + MOD - without_set) % MOD

if k >= 2**l: 
    print(0)
    exit(0)
ans = 1

for i in range(l):
    x = k % 2;
    k //= 2
    if x:
        ans *= with_set
    else:
        ans *= without_set
    ans %= MOD
    
print(ans)
