P5359 [SDOI2019] Coloring

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?

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 one integer: the total number of valid colorings modulo $10^9+9$.

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