E. Marble Race
time limit per test
5 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

Marble race is a fun way to play with marbles, and today you want to give it a try.

There are $$$n$$$ starting points on the negative half of the $$$x$$$-axis, with the $$$i$$$-th point located at $$$x_i$$$. There are $$$m$$$ marbles in total, where $$$m$$$ is an odd number, and the $$$i$$$-th marble has a speed of $$$v_i$$$. In a race, each marble randomly chooses a starting point with equal probability, and different marbles can choose the same starting point. Then, all the marbles start moving simultaneously towards the positive direction of the $$$x$$$-axis. Let $$$c_i$$$ be the starting point chosen by the $$$i$$$-th marble. At time $$$t$$$, the coordinate of the $$$i$$$-th marble is given by $$$x_{c_i} + v_i \cdot t$$$.

You are a unique marble race enthusiast and do not care which marble is the fastest. Instead, you want to find out the exact time when the median of all the $$$m$$$ marble coordinates reaches the origin (i.e., $$$x = 0$$$). The median of a sequence of length $$$m$$$ (where $$$m$$$ is odd) is defined as the element at the position $$$\frac{m+1}{2}$$$ when sorted in ascending order (indexing starts from $$$1$$$). Since the race has not yet started and the starting points are not yet determined, you are interested in the expected value of this time. To avoid floating-point errors, you only need to output the result modulo $$$10^9+7$$$ (see the output format for details).

Input

The first line contains two positive integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 500$$$, and $$$m$$$ is odd), representing the number of starting points and the number of marbles.

The second line contains $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ ($$$-10^9 \le x_i \lt 0$$$), representing the coordinates of each starting point. It is guaranteed that all $$$x_i$$$ are distinct.

The third line contains $$$m$$$ integers $$$v_1, v_2, \ldots, v_m$$$ ($$$1 \le v_i \le 10^9$$$), representing the speed of each marble.

Output

Output a single integer, representing the expected time modulo $$$10^9+7$$$.

Formally, let $$$M=10^9+7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac p q$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not\equiv 0\pmod M$$$. Output the integer equal to $$$p\cdot q^{-1}\pmod M$$$, where $$$q^{-1}$$$ denotes the modular multiplicative inverse of $$$q$$$ modulo $$$M$$$. In other words, output such an integer $$$x$$$ that $$$0\le x \lt M$$$ and $$$x\cdot q\equiv p\pmod M$$$. It can be proved that there is exactly one $$$x$$$ which meets the condition.

Examples
Input
2 3
-4 -5
1 2 3
Output
250000004
Input
3 3
-4 -5 -6
1 2 3
Output
500000006
Input
5 5
-4 -5 -6 -10 -2
1 2 3 2 4
Output
434986672
Note

For the first example, the speeds of the three marbles are $$$1, 2, 3$$$, respectively. Consider the initial positions of the three marbles:

  • $$$-4, -4, -4$$$: At $$$t=2$$$, the coordinates of the three marbles are $$$-2, 0, 2$$$, and the median is at the origin.
  • $$$-4, -4, -5$$$: At $$$t=2$$$, the coordinates are $$$-2, 0, 1$$$, and the median is at the origin.
  • $$$-4, -5, -4$$$: At $$$t=2.5$$$, the coordinates are $$$-1.5, 0, 3.5$$$, and the median is at the origin.
  • For $$$(-4, -5, -5)$$$, $$$(-5, -4, -4)$$$, $$$(-5, -4, -5)$$$, $$$(-5, -5, -4)$$$, $$$(-5, -5, -5)$$$, the median is at the origin at times $$$t=2.5$$$, $$$t=2$$$, $$$t=2$$$, $$$t=2.5$$$, $$$t=2.5$$$, respectively.
In summary, the expected time is $$$\frac{2 + 2 + 2.5 + 2.5 + 2 + 2 + 2.5 + 2.5}{8} = \frac{9}{4}$$$, so you need to output $$$9 \cdot 4^{-1} \bmod (10^9+7) = 250000004$$$.