/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
Paken島には 2 つの小学校、anmichi校とsanada校があり、島の人々はどちらかの学校に通って日々競プロの精進をしています。
これらの人々は、毎週行われるPatCoder社のコンテストに出ており、各人には能力を表すレーティングという値がついています。
anmichi校に通う N 人の生徒のうち i 番目の人のレーティングは A_i、sanada校に通う M 人の生徒のうち j 番目の人のレーティングは B_j です。
ある日、この 2 校で今年も伝統の対抗戦が行われることとなりました。
対抗戦では各校から 2 名ずつ選抜し、チーム戦を行うこととなっています。
この対抗戦の主催者であるdefineは 2 校で選ばれる人たちの実力差をなるべくなくすため、次の条件を満たすように 2 人を選ぶことを各校に伝えました。
- anmichi校から選んだ 2 名のレーティングを低い方から順に P,Q、sanada校から選んだ 2 名のレーティングを低い方から順に R,S としたとき、R < P < Q < S となる。
define君は条件を満たす選び方が何通りあるのか気になっています。
define君のためにこの条件を満たすような 4 人の選び方の通り数を 10^9+7 で割った余りを求めてください。
なお、4 人のレーティングの通り数を求めるわけではないことに注意してください。
制約
- 入力は全て整数である。
- 2 \leq N,M \leq 2\times 10^5
- 1 \leq A_i,B_j \leq 10^9 (1 \leq i \leq N, 1 \leq j \leq M)
- A_i は全て異なる。
- B_j は全て異なる。
入力
入力は以下の形式で標準入力から与えられます。
N M
A_1 A_2 \ldots A_{N-1} A_N
B_1 B_2 \ldots B_{M-1} B_M
出力
4 人の選び方の通り数を 10^9+7 で割った余りを 1 行に出力してください。
入力例1
4 4 40 60 20 10 25 30 80 50
出力例1
2
anmichi校からはレーティングが 40 と 60 の人しか選べず、sanada校からはレーティングが 25 と 80 の人、レーティングが 30 と 80 の人の 2 通りの選び方があります。
よって、1 \times 2 を 10^9+7 で割った余りである 2 を出力してください。
入力例2
5 3 112 76 50 35 22 15 60 50
出力例2
4
anmichi校とsanada校にレーティングが同じ人がいる場合もあります。ただし 1 つの学校内には同じレーティングの人はいません。
入力例3
2 2 8 69 1 20
出力例3
0
大会が開けません。悲しいですね。まずは学校の生徒数を増やしましょう。
writer: sanadayukimura73