August is doing his binary math homework. While doing it, he came up with a problem, and thought it would be a good problem to put on the GlobeX Canada Cup.

August gives you 3 questions. Given the integers $N$, $M$, $K$, and $V$, how many ways are there to make an integer array $a$ of length $N$ where $0\le a_i<2^K$ such that:

1. $a_1\oplus a_2\oplus a_3\oplus \dots \oplus a_N=V$?
2. $a_1\parallel a_2\parallel a_3\parallel \dots \parallel a_N=V$?
3. $a_1\mathrm{\&}{a}_2\mathrm{\&}{a}_3\mathrm{\&}\dots \mathrm{\&}{a}_N=V$?

Note that:

• $\oplus$ denotes the bitwise xor operation (^ in most languages).
• $\parallel$ denotes the bitwise or operation (| in most languages).
• $\mathrm{\&}$ denotes the bitwise and operation (& in most languages).

Since August has meganumerophobia, he wants the answer to each question modulo $M$.

Input Specification

The first line and only line will contain $4$ space-separated integers $N,M,K,V$ $(1\le N\le {10}^9,1\le M\le 2\times {10}^9,0\le K\le 63,0\le V<2^K)$.

Output Specification

On the first line, output the answer to question 1, modulo $M$.
On the second line, output the answer to question 2, modulo $M$.
On the last line, output the answer to question 3, modulo $M$.

Subtasks

Subtask 1 [5%]

$N\le 8,K\le 3$

Subtask 2 [15%]

$N\le {10}^3,M={10}^9+7$

Subtask 3 [60%]

$N\le {10}^5$

Subtask 4 [20%]

No additional constraints.

Sample Input 1

2 1000000007 3 5

Sample Output 1

8
9
3

Sample Input 2

8 1000000007 1 0

Sample Output 2

128
1
255