配点 : 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

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

4 1
3 2 1 0
5

出力例2

56

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

入力例3

4 4
2 1 1 1
1 1 1 1

出力例3

66

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

入力例4

4 4
5 5 4 3
5 4 4 3

出力例4

322875

入力例5

5 5
100 100 100 100 100
50 50 50 50 50

出力例5

331829279