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).
# -*- coding: utf-8 -*-
from collections import deque

def calc(n, m):
    if n == 0:
        return [[0, 0], [0, 0]]
    if n == 1:
        return [[1, 0], [0, 1]]
    a = calc(n // 2, m)
    if n % 2 == 0:
        res00 = (a[0][0] * a[0][0]) % m
        res00 = (res00 + a[0][0] * a[1][0]) % m
        res00 = (res00 + a[0][1] * a[0][0]) % m
        res01 = (a[0][0] * a[0][1]) % m
        res01 = (res01 + a[0][0] * a[1][1]) % m
        res01 = (res01 + a[0][1] * a[0][1]) % m
        res10 = (a[1][0] * a[0][0]) % m
        res10 = (res10 + a[1][0] * a[1][0]) % m
        res10 = (res10 + a[1][1] * a[0][0]) % m
        res11 = (a[1][0] * a[0][1]) % m
        res11 = (res11 + a[1][0] * a[1][1]) % m
        res11 = (res11 + a[1][1] * a[0][1]) % m
        return [[res00, res01], [res10, res11]]
    else:
        res00 = (a[0][0] * a[0][0] * 2) % m
        res00 = (res00 + a[0][0] * a[1][0]) % m
        res00 = (res00 + a[0][1] * a[0][0]) % m
        res00 = (res00 + a[0][1] * a[1][0]) % m
        res01 = (a[0][0] * a[0][1] * 2) % m
        res01 = (res01 + a[0][0] * a[1][1]) % m
        res01 = (res01 + a[0][1] * a[0][1]) % m
        res01 = (res01 + a[0][1] * a[1][1]) % m
        res10 = (a[1][0] * a[0][0] * 2) % m
        res10 = (res10 + a[1][0] * a[1][0]) % m
        res10 = (res10 + a[1][1] * a[0][0]) % m
        res10 = (res10 + a[1][1] * a[1][0]) % m
        res11 = (a[1][0] * a[0][1] * 2) % m
        res11 = (res11 + a[1][0] * a[1][1]) % m
        res11 = (res11 + a[1][1] * a[0][1]) % m
        res11 = (res11 + a[1][1] * a[1][1]) % m
        return [[res00, res01], [res10, res11]]

def binpow(a, p, m):
    if p == 0:
        return 1 % m
    if p == 1:
        return a % m
    ans = binpow(a, p // 2, m)
    ans = (ans * ans) % m
    if p % 2 == 1:
        ans = (ans * a) % m
    return ans

n, k, l, m = map(int, input().split())
ans = [0, 0]
x = calc(n, m)
ans[0] = (x[0][0] + x[0][1] + x[1][0] + x[1][1]) % m
ans[1] = ((binpow(2, n, m) - ans[0]) % m + m) % m
res = 1

for i in range(l):
    res = (res * ans[k & 1]) % m
    k >>= 1  

print(res)
