P5359 [SDOI2019] 染色

给定 $2 \times n$ 的格点图。其中一些结点有着已知的颜色，其余的结点还没有被染色。 一个合法的染色方案不允许相邻结点有相同的染色。 现在一共有 $c$ 种不同的颜色，依次记为 $1$ 到 $c$。 请问有多少对未染色结点的合法染色方案？

第一行有两个整数$n$和$c$，分别描述了格点图的大小和总的颜色个数。 之后两行，每行有$n$个整数：如果是 $0$ 则表示对应结点未被染色，否则一定是一个$1$到$c$的整数表示对应结点已经染了某一种颜色。

输出一个整数，为总的染色方案数对$10^9+9$取模后的值。

子任务$1$：（$44$分）$1\le n\le 10000$ 且 $5\le c\le 10000$；不存在一列有$2$个已染色结点；被染色结点全部位于第一行；第一列和最后一列均有结点已被染色。 子任务$2$：（$32$分）$1\le n\le 10000$ 且 $5\le c\le 10000$；不存在一列有$2$个已染色结点；第一列和最后一列均有结点已被染色。 子任务$3$：（$12$分）$1\le n\le 10000$ 且 $5\le c\le 10000$；第一列和最后一列均有结点已被染色。 子任务$4$：（$8$分）$1\le n\le 10000$ 且 $5\le c\le 10000$。 子任务$5$：（$4$分）$1\le n\le 100000$ 且 $5\le c\le 100000$。