問題文

正整数 $N,M$ が与えられます。 この時長さが $N,M$ の整数列 $A_1,A_2,\ldots ,A_N$ と $B=B_1,B_2,\ldots ,B_M$ が与えられます。 数列 $B$ の最大値を $C$ とすると $C$ 人の子供がいます。 これらの子供には $1,2,\ldots ,C $ の番号がついています。 数列 $A,B$ からそれぞれ要素を選ぶ方法は $NM$ 通りありますが、その全てに対して以下の操作を行います。

選ばれた要素を $A_i,B_j$ とし、 $1$ から $B_j$ の番号がついている子供全員に対して $k$ の番号がついている子供には $2×\lfloor \frac{A_i×k}{B_j}\rfloor $ 個のお菓子をあげます。

この操作を全てする時にお菓子は最低で何個必要か出力してください。 ただし答えは非常に大きくなる可能性があるので $1000000007$ で割った余りを出力してください。

入力

$N$
$M$
$A_1\ A_2\ \dots\ A_N$
$B_1\ B_2\ \dots\ B_M$

• 入力は全て整数である。
• $1 \le N,M \le 2000=2×10^3$
• $0 \le A_i\le 100000000=10^8$
• $1 \le B_j\le 100000000=10^8$

出力

必要なお菓子の個数の最低値を $1000000007$ で割った余りを出力して最後に改行してください。

サンプル

1
1
3
4

12

6
9
234523 35645 223 3563 234 346
346 467568 234141 457 235235 4656 3452 457 2

792159237