CF551D.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!

我们都知道 GukiZ 经常玩数组。

现在他正在思考这样一个问题：有多少个长度为 $n$ 的数组 $a$，其每个元素均为非负整数且严格小于 $2^l$，满足如下条件：
？
其中运算符 表示按位与（在 Pascal 中等价于 and，在 C/C++/Java/Python 中等价于 &），运算符 表示按位或（在 Pascal 中等价于 ，在 C/C++/Java/Python 中等价于 |）。

由于答案可能非常大，请对 $m$ 取模。这一次 GukiZ 没能想出解法，需要你来帮助他！

First and the only line of input contains four integers n, k, l, m (2 ≤ n ≤ 1018, 0 ≤ k ≤ 1018, 0 ≤ l ≤ 64, 1 ≤ m ≤ 109 + 7).

输入仅有一行，包含四个整数 $n$、$k$、$l$、$m$（满足 $2 \leq n \leq 10^{18}$，$0 \leq k \leq 10^{18}$，$0 \leq l \leq 64$，$1 \leq m \leq 10^9 + 7$）。

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

在单行中输出满足上述条件的数组个数对 $m$ 取模的结果。

In the first sample, satisfying arrays are {1, 1}, {3, 1}, {1, 3}.

In the second sample, only satisfying array is {1, 1}.

In the third sample, satisfying arrays are {0, 3, 3}, {1, 3, 2}, {1, 3, 3}, {2, 3, 1}, {2, 3, 3}, {3, 3, 0}, {3, 3, 1}, {3, 3, 2}, {3, 3, 3}.

在第一个样例中，满足条件的数组为 $\{1,\,1\}$、$\{3,\,1\}$、$\{1,\,3\}$。

在第二个样例中，唯一满足条件的数组是 $\{1,\,1\}$。

在第三个样例中，满足条件的数组为 $\{0,\,3,\,3\}$、$\{1,\,3,\,2\}$、$\{1,\,3,\,3\}$、$\{2,\,3,\,1\}$、$\{2,\,3,\,3\}$、$\{3,\,3,\,0\}$、$\{3,\,3,\,1\}$、$\{3,\,3,\,2\}$、$\{3,\,3,\,3\}$。