Comet OJ

C0706 [SDOI2019]染色

内存限制：256 MB 时间限制：3000 ms

题目描述

给定 $2 \times n$ 的格点图。其中一些结点有着已知的颜色，其余的结点还没有被染色。一个合法的染色方案不允许相邻结点有相同的染色。

现在一共有 $c$ 种不同的颜色，依次记为 $1$ 到 $c$。请问有多少对未染色结点的合法染色方案？

输入格式

第一行有两个整数 $n$ 和 $c$，分别描述了格点图的大小和总的颜色个数。

之后两行，每行有 $n$ 个整数：如果是 $0$ 则表示对应结点未被染色，否则一定是一个 $1$ 到 $c$ 的整数表示对应结点已经染了某一种颜色。

输出

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

样例

样例输入 1

3 5
1 0 1
0 0 0

样例输出 1

172

样例输入 2

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

样例输出 2

116370

样例输入 3

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

样例输出 3

770175525

提示

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

子任务 $2$（$32$分）：$1 ≤ n ≤ 10000$ 且 $5 ≤ c ≤ 10000$；不存在一列有$2$个已染色结点；第一列和最后一列均有结点已被染色。

子任务 $3$（$12$分）：$1 ≤ n ≤ 10000$ 且 $5 ≤ c ≤ 10000$；第一列和最后一列均有结点已被染色。

子任务 $4$（$8$分）：$1 ≤ n ≤ 10000$ 且 $5 ≤ c ≤ 10000$。

子任务 $5$（$4$分）：$1 ≤ n ≤ 100000$ 且 $5 ≤ c ≤ 100000$。