假设有一个由空单元格或满单元格组成的 $$$h \times w$$$ 网格。让我们做一些定义:
- $$$r_{i}$$$ 是连接到第 $$$i$$$ 行左侧的连续完整单元格的数量 ($$$1 \le i \le h$$$)。特别是,如果第 $$$i$$$ 行的最左侧单元格为空,则 $$$r_i=0$$$。
- $$$c_{j}$$$ 是连接到第 $$$j$$$ 列顶端的连续完整单元格的数量 ($$$1 \le j \le w$$$)。特别是,如果第 $$$j$$$ 列的最顶层单元格为空,则 $$$c_j=0$$$。
换句话说,第 $$$i$$$ 行完全以 $$$r_i$$$ 完整单元格开始。同样,第 $$$j$$$ 列完全以 $$$c_j$$$ 完整单元格开始。
这些是一些 $$$3 \times 4$$$ 网格的 $$$r$$$ 和 $$$c$$$ 值。黑色单元格已满,白色单元格为空。
您的值为 $$$r$$$ 和 $$$c$$$。最初,所有单元格都是空的。求出填充网格单元以满足 $$$r$$$ 和 $$$c$$$ 值的方法数。由于答案可能非常大,因此对 $$$1000000007\,(10^{9} + 7)$$$ 求模答案。换句话说,求答案除以 $$$1000000007\,(10^{9} + 7)$$$ 后的余数。
输入
第一行包含两个整数 $$$h$$$ 和 $$$w$$$ ($$$1 \le h, w \le 10^{3}$$$) — 网格的高度和宽度。
第二行包含 $$$h$$$ 整数 $$$r_{1}, r_{2}, \ldots, r_{h}$$$ ($$$0 \le r_{i} \le w$$$) — $$$r$$$ 的值。
第三行包含 $$$w$$$ 整数 $$$c_{1}, c_{2}, \ldots, c_{w}$$$ ($$$0 \le c_{j} \le h$$$) — $$$c$$$ 的值。
输出
打印答案模 $$$1000000007\,(10^{9} + 7)$$$。
示例
输入 #1
3 4 0 3 1 0 2 3 0
输出 #1
2
输入 #2
1 1 0 1
输出 #2
0
输入 #3
19 16 16 16 16 16 15 15 0 5 0 4 9 9 1 4 4 0 8 16 12 6 12 19 15 8 6 19 19 14 6 9 16 10 11 15 4
输出 #3
797922655
注意
在第一个示例中,这是另一种可能的情况。
在第二个示例中,不可能制作一个网格来满足这样的 $$$r$$$、$$$c$$$ 值。
在第三个示例中,请确保打印答案模 $$$(10^9 + 7)$$$。