题目描述

弹珠比赛是一种有趣的弹珠玩法，今天你想试试吗？

在 $x$ 轴的负半轴上有 $n$ 个起点，其中 $i$ 个点位于 $x_i$ 。一共有 $m$ 个弹珠，其中 $m$ 是奇数， $i$ 个弹珠的速度为 $v_i$ 。在比赛中，每颗弹珠以相等的概率随机选择一个起点，不同的弹珠可以选择相同的起点。然后，所有弹珠同时开始向 $x$ 轴的正方向移动。假设 $c_i$ 是 $i$-th弹珠选择的起点。在 $t$ 时刻， $i$-th弹珠的坐标为 $x_{c_i} + v_i \cdot t$ 。

你是一个独特的弹珠竞赛爱好者，并不关心哪颗弹珠最快。相反，你想知道所有 $m$ 个弹珠坐标的中位数到达原点(即 $x = 0$ )的确切时间。长度为 $m$ (其中 $m$ 为奇数)的序列的中位数定义为按升序排序时位于 $\frac{m+1}{2}$ 位置的元素(索引从 $1$ 开始)。由于比赛尚未开始，起点也未确定，因此您感兴趣的是这一时间的预期值。为避免浮点错误，只需输出结果取模 $10^9+7$ (详见输出格式)。

输入格式

输入

第一行包含两个正整数 $n$ 和 $m$ ( $1 \leq n, m \le 500$ 和 $m$ 为奇数)，分别代表起始点数和弹珠数。

第二行包含 $n$ 个整数 $x_1, x_2, \ldots, x_n$ ( $-10^9 \leq x_i \leq 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$ modulo $M$ 的模乘逆。换句话说，输出这样一个整数 $x$ 即 $0 \leq x_M$ 和 $x\cdot q\equiv p\pmod M$ 。可以证明正好有一个 $x$ 符合条件。

2 3
-4 -5
1 2 3

250000004

3 3
-4 -5 -6
1 2 3

500000006

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

434986672

解释 #1

注

在第一个例子中，三个弹珠的速度分别为 $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$ 。