Description:
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 2l meet the following condition: $$(a_{1}\ \mathrm{and}\ a_{2})\ \mathrm{or}\ (a_{2}\ \mathrm{and}\ a_{3})\ \mathrm{or}\ldots\ \mathrm{or}\ (a_{n-1}\ \mathrm{and}\ a_{n})=k$$? Here operation $$\text{and}$$ means bitwise AND (in Pascal it is equivalent to and, in C/C++/Java/Python it is equivalent to &), operation $$\sigma_{1}^{2}$$ means bitwise OR (in Pascal it is equivalent to $$\sigma_{1}^{2}$$, 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!
Input Format:
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).
Output Format:
In the single line print the number of arrays satisfying the condition above modulo m.
Note:
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}.