Marble Race
弹珠赛跑是一种有趣的玩弹珠的方式。
x 轴的负半轴上有 n 个起跑点,第 i 个点的坐标为 xi。共有 m 个弹珠,m 是奇数,第 j 个弹珠的速度为 vj。
在一场赛跑中,每个弹珠独立地、等概率地选择一个起跑点。不同的弹珠可以选择相同的起跑点。随后所有弹珠同时出发,沿 x 轴正方向匀速移动。如果第 j 个弹珠选择的起跑点编号为 cj,则它在时刻 t 的坐标为
xcj+vjt.
你不关心哪个弹珠最快,而是想知道:这 m 个弹珠的坐标的中位数恰好为 0 的时刻,其数学期望是多少?
长度为奇数 m 的序列的中位数,是将序列从小到大排序后第 (m+1)/2 个元素,下标从 1 开始。
由于弹珠尚未选择起跑点,你需要对所有独立选择计算期望,并将答案对 109+7 取模。
输入格式
第一行两个整数 n,m,满足 1≤n,m≤500,且 m 为奇数。
第二行 n 个整数 x1,…,xn,满足 −109≤xi<0,所有 xi 两两不同。
第三行 m 个整数 v1,…,vm,满足 1≤vj≤109。速度可以重复。
本题只有一组输入。
输出格式
输出一个整数,表示期望对 P=109+7 取模后的结果。
形式化地,期望可以表示为最简分数 p/q,且 q≡0(modP)。输出唯一的整数 y,满足 0≤y<P 且 yq≡p(modP),即 y=pq−1modP。
样例 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,3。三个弹珠的初始坐标有 8 种等概率情况:
| 初始坐标,按弹珠编号排列 |
中位数到达原点的时刻 |
| (−4,−4,−4) |
2 |
| (−4,−4,−5) |
| (−4,−5,−4) |
2.5 |
| (−4,−5,−5) |
| (−5,−4,−4) |
2 |
| (−5,−4,−5) |
| (−5,−5,−4) |
2.5 |
| (−5,−5,−5) |
例如第一种情况在 t=2 时坐标为 (−2,0,2);第二种情况在 t=2 时为 (−2,0,1);第三种情况在 t=2.5 时为 (−1.5,0,3.5),其中位数均为 0。
因此期望为
82+2+2.5+2.5+2+2+2.5+2.5=49,
输出 9⋅4−1mod(109+7)=250000004。