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 mul_matr(matr1, matr2):
    return [[sum(x * y for (x, y) in zip(row, col)) for col in zip(*matr2)] for row in matr1]
        
def pow_matr_mod(matr, pw, mod):
    res = [[1, 0], [0, 1]]
    for c in map(int, "{:b}".format(pw)):
        res = mul_matr(res, res)
        if c:
            res = mul_matr(res, matr)
        for row in res:
            for i in range(len(row)):
                row[i] %= mod
    return res

def get_zero_count(n, mod):
    return sum(map(sum, pow_matr_mod([[1, 1], [1, 0]], n - 1, mod)))  % mod


def get_one_count(n, mod):
    return (pow(2, n, mod) - get_zero_count(n, mod)) % mod


def calc_result(n, k, l, m):
    if k >= 2 ** l:
        return 0

    zero = get_zero_count(n, m)
    one = get_one_count(n, m)
    res = 1
    for c in map(int, "{{:0{}b}}".format(l).format(k)):
        if c:
            res *= one
        else:
            res *= zero
        res %= m

    return res
    
print(calc_result(*map(int, input().split())))
