A9911 | GukiZ and Binary Operations

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^{l}$ meet the following condition: ? Here operation  means bitwise AND (in Pascal it is equivalent to and, in C/C++/Java/Python it is equivalent to &), operation  means bitwise OR (in Pascal it is equivalent to , 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^{18}$ , $0<=k<=10^{18}$ , $0<=l<=64$ , $1<=m<=10^{9}+7$ ).

In the single line print the number of arrays satisfying the condition above modulo $m$ .