题目描述

样例

有一个 $2$ 行 $n$ 列的网格。部分格子已经驻扎了士兵，每名士兵的兵种是 $1$ 到 $m$ 中的一个整数。

你需要在每个空格中安排一名士兵，其兵种可以任意选择。已经驻扎的士兵及其兵种不能改变。

安排完成后，每两个共用一条边的格子上的士兵必须属于不同兵种。求合法安排的方案数，对 $10^9+9$ 取模。若无法完成合法安排，输出 $0$。

输入格式

第一行包含两个整数 $n,m$。

第二行包含 $n$ 个整数，依次描述第一行的格子。第三行包含 $n$ 个整数，依次描述第二行的格子。

每个整数为 $0$ 时，表示该格为空；否则表示该格已有士兵的兵种。

输出格式

输出一个整数，表示合法安排的方案数对 $10^9+9$ 取模后的值。

数据范围

所有数据满足 $1\le n\le10^5$、$5\le m\le10^5$；描述格子的每个整数均在 $0$ 到 $m$ 之间。

子任务

样例 1

3 5
1 0 1
0 0 0

172

样例 2

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

116370

样例 3

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

770175525