P14805 [CCPC 2024 Harbin Site] Marble Race

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 \textbf{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).

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 < 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 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 < M$ and $x\cdot q\equiv p\pmod M$. It can be proved that there is exactly one $x$ which meets the condition.

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$.