GlobeX Cup '18 S3 - Playing With Bits

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem types

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

Comments

There are no comments at the moment.