Description

Given a $2 \times n$ grid graph. Some vertices already have known colors, and the remaining vertices are not colored yet.

A valid coloring does not allow adjacent vertices to have the same color.

There are $c$ different colors in total, numbered from $1$ to $c$.

How many valid colorings are there for the uncolored vertices?

Input Format

The first line contains two integers $n$ and $c$, describing the size of the grid graph and the total number of colors.

Then there are two lines, each containing $n$ integers: if it is $0$, it means the corresponding vertex is uncolored; otherwise, it must be an integer from $1$ to $c$, meaning the vertex has already been colored with a certain color.

Output Format

Output one integer: the total number of valid colorings modulo $10^9+9$.

3 5
1 0 1
0 0 0

172

5 7
1 0 0 0 2
0 0 3 0 0

116370

10 13
0 2 0 0 1 0 2 0 0 3
0 1 0 1 0 0 0 0 4 0

770175525

Hint

Subtask $1$ ($44$ points): $1 \le n \le 10000$ and $5 \le c \le 10000$; there is no column with $2$ colored vertices; all colored vertices are in the first row; both the first column and the last column have a colored vertex.

Subtask $2$ ($32$ points): $1 \le n \le 10000$ and $5 \le c \le 10000$; there is no column with $2$ colored vertices; both the first column and the last column have a colored vertex.

Subtask $3$ ($12$ points): $1 \le n \le 10000$ and $5 \le c \le 10000$; both the first column and the last column have a colored vertex.

Subtask $4$ ($8$ points): $1 \le n \le 10000$ and $5 \le c \le 10000$.

Subtask $5$ ($4$ points): $1 \le n \le 100000$ and $5 \le c \le 100000$.

Translated by ChatGPT 5