← 返回题目列表

Codeforces · 1228/B

B. 填充网格

中文机器翻译题面 查看原题

假设有一个由空单元格或满单元格组成的 $$$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)$$$。