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 \ldots \oplus a_N = V~?
2. ~a_1 \parallel a_2 \parallel a_3 \parallel \ldots \parallel a_N = V~?
3. ~a_1 \mathbin{\&} a_2 \mathbin{\&} a_3 \mathbin{\&} \ldots \mathbin{\&} a_N = V~?

Note that:

• ~\oplus~ denotes the bitwise xor operation (^ in most languages).
• ~\parallel~ denotes the bitwise or operation (| in most languages).
• ~\&~ 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