#3111. 「SDOI2019」染色

内存限制:256 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

给定 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