#P18206. Marble Race

Marble Race

Marble Race

弹珠赛跑是一种有趣的玩弹珠的方式。

xx 轴的负半轴上有 nn 个起跑点,第 ii 个点的坐标为 xix_i。共有 mm 个弹珠,mm 是奇数,第 jj 个弹珠的速度为 vjv_j。

在一场赛跑中,每个弹珠独立地、等概率地选择一个起跑点。不同的弹珠可以选择相同的起跑点。随后所有弹珠同时出发,沿 xx 轴正方向匀速移动。如果第 jj 个弹珠选择的起跑点编号为 cjc_j,则它在时刻 tt 的坐标为

xcj+vjt.x_{c_j}+v_jt.

你不关心哪个弹珠最快,而是想知道:这 mm 个弹珠的坐标的中位数恰好为 00 的时刻,其数学期望是多少?

长度为奇数 mm 的序列的中位数,是将序列从小到大排序后第 (m+1)/2(m+1)/2 个元素,下标从 11 开始。

由于弹珠尚未选择起跑点,你需要对所有独立选择计算期望,并将答案对 109+710^9+7 取模。

输入格式

第一行两个整数 n,mn,m,满足 1≤n,m≤5001\le n,m\le500,且 mm 为奇数。

第二行 nn 个整数 x1,…,xnx_1,\ldots,x_n,满足 −109≤xi<0-10^9\le x_i<0,所有 xix_i 两两不同。

第三行 mm 个整数 v1,…,vmv_1,\ldots,v_m,满足 1≤vj≤1091\le v_j\le10^9。速度可以重复。

本题只有一组输入。

输出格式

输出一个整数,表示期望对 P=109+7P=10^9+7 取模后的结果。

形式化地,期望可以表示为最简分数 p/qp/q,且 q≢0(modP)q\not\equiv0\pmod P。输出唯一的整数 yy,满足 0≤y<P0\le y<P 且 yq≡p(modP)yq\equiv p\pmod P,即 y=pq−1 mod Py=pq^{-1}\bmod P。

样例 1

输入:

2 3
-4 -5
1 2 3

输出:

250000004

样例 2

输入:

3 3
-4 -5 -6
1 2 3

输出:

500000006

样例 3

输入:

5 5
-4 -5 -6 -10 -2
1 2 3 2 4

输出:

434986672

样例说明

第一组样例中,三个弹珠的速度分别为 1,2,31,2,3。三个弹珠的初始坐标有 88 种等概率情况:

初始坐标,按弹珠编号排列 中位数到达原点的时刻
(−4,−4,−4)(-4,-4,-4) 22
(−4,−4,−5)(-4,-4,-5)
(−4,−5,−4)(-4,-5,-4) 2.52.5
(−4,−5,−5)(-4,-5,-5)
(−5,−4,−4)(-5,-4,-4) 22
(−5,−4,−5)(-5,-4,-5)
(−5,−5,−4)(-5,-5,-4) 2.52.5
(−5,−5,−5)(-5,-5,-5)

例如第一种情况在 t=2t=2 时坐标为 (−2,0,2)(-2,0,2);第二种情况在 t=2t=2 时为 (−2,0,1)(-2,0,1);第三种情况在 t=2.5t=2.5 时为 (−1.5,0,3.5)(-1.5,0,3.5),其中位数均为 00。

因此期望为

2+2+2.5+2.5+2+2+2.5+2.58=94,\frac{2+2+2.5+2.5+2+2+2.5+2.5}{8}=\frac94,

输出 9⋅4−1 mod (109+7)=2500000049\cdot4^{-1}\bmod(10^9+7)=250000004。