Problem Statement

You are given positive integers $N,M$. You are then given integer sequences $A_1,A_2,\ldots ,A_N$ and $B=B_1,B_2,\ldots ,B_M$ of lengths $N,M$. Let $C$ be the maximum value of the sequence $B$; there are $C$ children. These children are numbered $1,2,\ldots ,C $. There are $NM$ ways to choose one element from each of the sequences $A,B$, and the following operation is performed for all of them.

Let the chosen elements be $A_i,B_j$. For all children numbered from $1$ to $B_j$, the child numbered $k$ is given $2×\lfloor \frac{A_i×k}{B_j}\rfloor $ candies.

Output the minimum number of candies needed to perform all of these operations. Since the answer can be very large, output it modulo $1000000007$.

Input

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

• All inputs are integers.
• $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$

Output

Output the minimum number of candies needed, modulo $1000000007$, followed by a newline.

Sample

1
1
3
4

12

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

792159237