Cold Night

Nights in western Sweden can be quite cold, even in late April.

There are $M$ cabins at Chalmersbastun in Härryda. The $i$th cabin can house $c_i$ people, and has a temperature of $t_i$.

A total of $N$ bootcamp participants will stay in the cabins. The $i$th person has a favourite temperature $f_i$. All of these numbers are different. The number of participants is the maximum possible that can fit in the cabins. In other words, $c_1+c_2+\dots +c_M = N$.

If person $i$ sleeps in cabin $j$, then the angryness of person $i$ will be $|f_i-t_j|$. Of course, it would be ideal if the sum of angrynesses of all $N$ participants was minimized. But unfortunately, they just choose houses uniformly at random instead.

Your task is to calculate the probability that the sum of angrynesses is minimized when participants choose cabins uniformly at random. Find this number modulo $10^9+7$. In other words, if the probability is written as $P/Q$ where $P$ and $Q$ are coprime, then your task is to find $PQ^{-1}$ modulo $10^9+7$.

Input

The first line contains two integers $N$ and $M$ ($1 \leq M \leq N \leq 3 \cdot 10^5$).

The second line contains $M$ integers $c_i$ ($1 \leq c_i \leq N$, $c_1+c_2+\dots +c_M = N$). The third line contains $M$ integers $t_i$ ($-273 \leq t_i \leq 10^9$). The fourth line contains $N$ integers $f_i$ ($-273 \leq f_i \leq 10^9$).

Note that all of the numbers $f_i$ are different!

Output

Print one integer, the probability modulo $10^9+7$.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

8 2
4 4
-20 17
15 20 17 22 27 26 -31 0

71428572

4 4
1 1 1 1
1 2 3 4
1 2 3 4

41666667

2 2
1 1
1 2
3 4

1