

Time Limit: 2.525 sec / Memory Limit: 246 MB
配点 : 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