描述

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

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

格式

输入格式

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

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

输出格式

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

样例1

样例输入1

3 5
1 0 1
0 0 0

样例输出1

172

样例2

样例输入2

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

样例输出2

116370

样例3

样例输入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\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\)。

时限

3s

内存限制

默认