GukiZ and Binary Operations

1000ms

262144K

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 2^l meet the following condition: $\text{[math]}$ ? Here operation $\text{[math]}$ means bitwise AND (in Pascal it is equivalent to and, in C/C++/Java/Python it is equivalent to &), operation $\text{[math]}$ means bitwise OR (in Pascal it is equivalent to $\text{[math]}$ , 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:

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

Output:

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

Sample Input:

2 1 2 10

Sample Output:

Sample Input:

2 1 1 3

Sample Output:

Sample Input:

3 3 2 10

Sample Output:

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}.

Informação

Provedor Codeforces

Código CF551D