Background

Now, even if I "melt" you, who was floating in the sky, into the air,
there is still a feeling that will not change.

Problem Description

You are given a positive integer $n$ and five sets $A, B, C, D, E$ consisting of integers in $[0, 2^n)$.

For two non-negative integers $x, i$, define $x_i = \lfloor x / 2^i \rfloor \bmod 2$, i.e., the $(i+1)$-th bit of $x$ in binary from low to high.

For a set $S$ consisting of non-negative integers, define a 5-tuple $(a, b, c, d, e)$ to be fair for $S$ if and only if:

• $a \in A$, $b \in B$, $c \in C$, $d \in D$, $e \in E$;
• For every $i \in S$, in $[a_i, b_i, c_i, d_i, e_i]$, the counts of $0$ and $1$ differ by at most $1$.

For all $S \subseteq \{0, 1, \cdots, n-1\}$, compute the number of 5-tuples that are fair for $S$. Output the answer modulo the given positive integer $P$.

Input Format

The first line contains two positive integers $n, P$, representing the value range of the numbers and the modulus for the answers.

The next five lines each describe a set using $2^n$ characters from 01. If the $i$-th character is 1, then $i - 1$ is in the set; otherwise, $i - 1$ is not in the set. The five sets described are $A, B, C, D, E$, respectively.

Output Format

Output $2^n$ lines, each containing one non-negative integer. Line $k$ gives the answer for the set $S = \{ i \mid (k - 1)_i = 1 \}$.

2 1000000000
1000
0010
0101
1000
0101

4
4
3
3

2 1000000000
1110
0110
1101
1111
0101

144
92
88
57

3 1000000000
11101101
01011010
11001101
01110101
01101101

3000
1770
1812
1071
1890
1084
1141
652

4 1000000000
1110110111111111
1111110101010101
0110111011101111
0011110111001101
1001111111101101

221760
139104
132236
82818
137312
86926
82048
51869
140280
88038
83500
52354
86869
55043
51747
32767

Hint

[Sample #1 Explanation]

For $S = \{0, 1\}$, the three 5-tuples that are fair for $S$ are: $(0, 2, 1, 0, 3)$, $(0, 2, 3, 0, 1)$, $(0, 2, 3, 0, 3)$.

[Constraints]

For all testdata, $1 \le n \le 15$, $10^8 \le P \le 10^9$.

This problem uses bundled testcases. There are $10$ subtasks, each worth $10$ points. Subtask $i$ satisfies $n = i + 5$.

Translated by ChatGPT 5