Description

To improve his IQ, ZJY traveled to a new world. However, after traveling, ZJY unfortunately found that to open the door back to his original world, he must solve the puzzle drawn on the door. The puzzle is as follows:

There is an $n$-row by $m$-column board on which many special pieces can be placed. Each piece has an attack range of 3 rows and $p$ columns. The input provides a template of the attack range as a $3\times p$ matrix. A piece is assumed to be at row $1$, column $k$ of the template; positions it can attack are marked with $1$, and positions it cannot attack are marked with $0$. The input guarantees that the entry at row $1$, column $k$ is $1$. The password to open the door is the number of ways to place pieces on the board so that the pieces do not attack each other. Note that placing no pieces at all also counts as a valid arrangement. Since the number of arrangements may be large, and the password is a 32-bit binary number, ZJY only needs the number of arrangements modulo $2^{32}$.

Note: indices start from $0$, i.e., row $1$ refers to the middle row.

Input Format

The first line contains two integers $n$ and $m$, representing the size of the board.

The second line contains two integers $p$ and $k$, representing the size of the upcoming attack-range template and the piece’s position within the template.

The next three lines each contain $p$ numbers, describing the attack-range template. There is a space after each number.

Output Format

Output a single line with one integer, the number of valid arrangements modulo $2^{32}$.

5 5
3 1
0 1 0
1 1 1
0 1 0

55447

Hint

Constraints

For 10% of the testdata, $1 \leq n \leq 5$, $1 \leq m \leq 5$.

For 50% of the testdata, $1 \leq n \leq 1000$, $1 \leq m \leq 6$.

For 100% of the testdata, $1 \leq n \leq 10^{6}$, $1 \leq m \leq 6$.

Translated by ChatGPT 5