Coloring the 2×n Grid

Given a grid graph of dimensions $2 \times n$. Some nodes have a pre-assigned color while others are uncolored. There are $c$ colors available, numbered from $1$ to $c$. A valid coloring must ensure that any two adjacent nodes (i.e. nodes sharing an edge) have different colors. In the grid, vertices in the same column are adjacent (the top and bottom are connected), and vertices in neighboring columns in the same row are also adjacent.

You are given the current coloring of the grid: a 2×n matrix where each cell is either $0$ (indicating that the node is uncolored) or an integer between $1$ and $c$ (indicating a pre-assigned color). It is guaranteed that the pre-colored nodes do not violate the adjacent coloring condition.

Determine the number of valid coloring schemes for the uncolored nodes.

inputFormat

The first line contains two integers $n$ and $c$. The next two lines each contain $n$ integers. The $i$-th integer in each line denotes the color of the corresponding node in that row. A value of $0$ indicates the node is uncolored, while a value between $1$ and $c$ indicates that the node is pre-colored.

outputFormat

Output a single integer representing the number of valid coloring schemes for the uncolored nodes.

sample

1 3
0
0

6