配点 : $500$ 点

問題文

dwango社員のニワンゴくんはゲームが大好きです。ニワンゴくんは「なんとかトゥーン」というゲームを遊んでいます。

このゲームはチーム戦で、$N$ 人のプレイヤーからなるAチームと、$M$ 人のプレイヤーからなるBチームに分かれて戦闘を行います。各プレイヤーは戦闘の間、相手チームのプレイヤーに対して「攻撃」を行うことができます。あるプレイヤーからあるプレイヤーに対する攻撃が成立すると、攻撃したプレイヤーの「キル数」が $1$ 加算され、同時に攻撃されたプレイヤーの「デス数」が $1$ 加算されます。どちらのプレイヤーも攻撃の後も戦闘を継続でき、攻撃したりされたりすることが可能です。あるプレイヤーが同じプレイヤーを複数回攻撃することもありえます。しかし、同じチームのプレイヤーを攻撃することはできません。戦闘の開始時点で、すべてのプレイヤーのキル数とデス数は $0$ に設定されています。

ニワンゴくんは、戦闘が終わるとその結果を記録しています。ニワンゴくんの記録は以下の様なものです。まず、Aチームのプレイヤーをキル数の多い順（同じ場合デス数の少ない順）に並べ、それらのキル数を killA = \[killA_1, killA_2, ..., killA_N\] 、デス数を deathA = \[deathA_1, deathA_2, ..., deathA_N\] とします。同様にしてBチームのプレイヤーからも数列 killB = \[killB_1, killB_2, ..., killB_M\] および deathB = \[deathB_1, deathB_2, ..., deathB_M\] を定義します。ニワンゴくんは $killA$ と $killB$ のみを記録します。

ニワンゴくんは、 $killA$ と $killB$ から必ずしも一意に $deathA$ と $deathB$ を復元できないことに気が付きました。与えられた $killA$ と $killB$ に矛盾しない $deathA$ と $deathB$ の組み合わせは何通りあるでしょうか？答えは非常に大きくなりうるので、 $1,000,000,007 (10^9 + 7)$ で割った余りを出力してください。

制約

• $1 \\leq N, M \\leq 100$
• $0 \\leq killA_i, killB_i$
• $killA_1 + killA_2 + ... + killA_N \\leq 1,000$
• $killB_1 + killB_2 + ... + killB_M \\leq 1,000$
• $killA_{i} \\geq killA_{i+1} (1 \\leq i \\leq N - 1)$
• $killB_{i} \\geq killB_{i+1} (1 \\leq i \\leq M - 1)$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $killA_1$ $killA_2$ $...$ $killA_N$ $killB_1$ $killB_2$ $...$ $killB_M$

出力

答えを出力せよ。

入力例1

4 1
0 0 0 0
5```

### 出力例1

```plain
6```

$deathA$ としてありえるのは、 $\[0, 0, 0, 5\]$, $\[0, 0, 1, 4\]$, $\[0, 0, 2, 3\]$, $\[0, 1, 1, 3\]$, $\[0, 1, 2, 2\]$, $\[1, 1, 1, 2\]$ の $6$ 通り、$deathB$ としてありえるのは、 $\[0\]$ の $1$ 通りなので、答えは $6$ となる。

### 入力例2

```plain
4 1
3 2 1 0
5```

### 出力例2

```plain
56```

入力例1ではAチームの全員のキル数が同じなため、デス数は昇順である必要があったが、入力例2ではキル数が異なるため、デス数は昇順である必要はない。

### 入力例3

```plain
4 4
2 1 1 1
1 1 1 1```

### 出力例3

```plain
66```

$deathA$ としてありえるのは $11$ 通り、$deathB$ としてありえるのは $6$ 通りなので、答えは $66$ となる。

### 入力例4

```plain
4 4
5 5 4 3
5 4 4 3```

### 出力例4

```plain
322875```

### 入力例5

```plain
5 5
100 100 100 100 100
50 50 50 50 50```

### 出力例5

```plain
331829279```

* * *