P14805 [CCPC 2024 哈尔滨站] 弹珠赛跑

弹珠赛跑是一种非常有趣的玩弹珠的方式，你今天也想尝试一下。 $x$ 轴负半轴有 $n$ 个起跑点位，第 $i$ 个点位的坐标为 $x_i$。总共有 $m$ 个弹珠，其中 $m$ 是奇数，第 $i$ 个弹珠的移动速度为 $v_i$。在一场比赛中，每一个弹珠都会等概率地随机选择一个起跑点位，不同的弹珠可以选到相同的点位。比赛开始时，所有弹珠同时出发，向 $x$ 正半轴方向一直移动。令 $c_i$ 为第 $i$ 个弹珠选择的起跑点位编号，不难得出在时间为 $t$ 时第 $i$ 个弹珠的坐标为 $x_{c_i} + v_i \cdot t$。 你是个独特的弹珠爱好者，并不在乎哪个弹珠最快。你只想知道这 $m$ 个弹珠的所有坐标的**中位数**恰好在原点（即 $x = 0$）的时间点。一个长度为奇数 $m$ 的序列的中位数是从小到大排序后下标为 $\frac{m+1}{2}$ 的数（下标从 $1$ 开始）。由于赛跑还没开始，弹珠的起跑点位还没有确定，所以你想知道这个答案的数学期望。为了避免实数误差，你只需要输出这个答案在 $10^9+7$ 模意义下的结果（详情见输出格式）。

第一行两个正整数 $n$ 和 $m$ ($1 \le n, m \le 500$，且 $m$ 为奇数)，表示起跑点位个数和弹珠的个数。 第二行 $n$ 个整数 $x_1, x_2, \ldots, x_n$ ($-10^9 \le x_i < 0$)，表示每个起跑点位的坐标。保证所有 $x_i$ 互不相同。 第三行 $m$ 个整数 $v_1, v_2, \ldots, v_m$ ($1 \le v_i \le 10^9$)，表示每个弹珠的移动速度。

输出一行一个整数，表示答案的数学期望对 $10^9+7$ 取模后的结果。 令 $M=10^9+7$。可以证明，答案能够表示为最简分数 $\frac p q$，其中 $p$ 和 $q$ 是正整数且 $q \not\equiv 0\pmod M$。则你需要输出 $p\cdot q^{-1}\pmod M$，$q^{-1}$ 表示 $q$ 在模 $M$ 意义下的乘法逆元。换句话说，输出满足 $0\le x < M$ 且 $x\cdot q\equiv p\pmod M$ 的整数 $x$。可以证明，符合条件的 $x$ 是唯一的。

对于第一个样例，三个弹珠的速度分别为 $1, 2, 3$，考虑三个弹珠分别的初始坐标： - $-4, -4, -4$：$t=2$ 的时候，三个弹珠的坐标分别为 $-2, 0, 2$，中位数恰好在原点。 - $-4, -4, -5$：$t=2$ 的时候，三个弹珠的坐标分别为 $-2, 0, 1$，中位数恰好在原点。 - $-4, -5, -4$：$t=2.5$ 的时候，三个弹珠的坐标分别为 $-1.5, 0, 3.5$，中位数恰好在原点。 - $(-4, -5, -5)$, $(-5, -4, -4)$, $(-5, -4, -5)$, $(-5, -5, -4)$, $(-5, -5, -5)$ 的时候同理，中位数恰好在原点的时间分别为 $t=2.5$, $t=2$, $t=2$, $t=2.5$, $t=2.5$。 综上，期望时间为 $\frac{2 + 2 + 2.5 + 2.5 + 2 + 2 + 2.5 + 2.5}{8} = \frac{9}{4}$，因此你需要输出 $9 \cdot 4^{-1} \bmod (10^9+7) = 250000004$。