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 CC++JavaPython it is equivalent to &), operation means bitwise OR (in Pascal it is equivalent to , in CC++JavaPython 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 ≤ 1018, 0 ≤ k ≤ 1018, 0 ≤ l ≤ 64, 1 ≤ m ≤ 109 + 7).

输出描述:

In the single line print the number of arrays satisfying the condition above modulo 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}.