← 返回题目列表

Codeforces · 1951/G

G. 嘎嘎作响的球

中文机器翻译题面 查看原题

沿着圆圈放置 $$$m$$$ 个篮子,按顺时针顺序编号从 $$$1$$$ 到 $$$m$$$(篮子 $$$m$$$ 紧挨着篮子 $$$1$$$)。此外,还有$$$n$$$个球,其中球$$$i$$$最初放置在篮子$$$a_i$$$中,并且没有篮子包含多个球。

Alice 可以执行以下操作,无论您是否移动/扔球,该操作始终只需要一秒钟:

- Alice 统一随机选择 $$$1$$$ 和 $$$n$$$ 之间的整数 $$$i$$$。
- 如果球 $$$i$$$ 之前被扔掉,则不执行任何操作。
- 否则,球 $$$i$$$ 将从当前包含它的篮子移动到下一个篮子(按顺时针顺序)。如果目标篮子当前包含另一个球 $$$j$$$,则将球 $$$j$$$ 扔掉。

她重复这一操作,直到只剩下一个球。计算 Alice 结束进程所需的预计时间(以秒为单位)。

可以证明答案可以表示为有理数 $$$\frac{p}{q}$$$ 与互质 $$$p$$$ 和 $$$q$$$。您需要输出 $$$p \cdot q^{-1} \bmod 10^9 + 7$$$。可以证明 $$$10^9 + 7 \nmid q$$$。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5, n \le m \le 10^9$$$) – 球的数量和篮子的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$, $$$a_i$$$ 成对不同) - 每个球的初始位置。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数:Alice 结束进程所需的预期时间(以秒为单位),以 $$$10^9 + 7$$$ 为模。

示例

输入 #1

5
3 10
5 1 4
2 15
15 1
6 6
1 2 3 4 5 6
6 9
6 5 4 3 2 1
1 100
69

输出 #1

600000042
14
35
333333409
0

注意

在第一个测试用例中,Alice 可以按如下方式进行(如果球 $$$i$$$ 被扔出,我们定义 $$$a_i = -1$$$):

- 最初,$$$a = [5, 1, 4]$$$。
- Alice 以 $$$\frac{1}{3}$$$ 的概率选择 $$$i = 2$$$,并且球 $$$2$$$ 被移至篮子 $$$2$$$ 中。之后,$$$a = [5, 2, 4]$$$。
- Alice 选择 $$$i = 2$$$,概率为 $$$\frac{1}{3}$$$,并且球 $$$2$$$ 被移动到篮子 $$$3$$$ 中。之后,$$$a = [5, 3, 4]$$$。
- Alice 选择 $$$i = 2$$$,概率为 $$$\frac{1}{3}$$$,并且球 $$$2$$$ 被移动到篮子 $$$4$$$ 中。由于篮子 $$$4$$$ 先前包含球 $$$3$$$,因此该球被扔出。之后,$$$a = [5, 4, -1]$$$。
- Alice 选择 $$$i = 3$$$,概率为 $$$\frac{1}{3}$$$。球 $$$3$$$ 已经被扔出去了,所以什么也没有发生。之后,$$$a = [5, 4, -1]$$$。
- Alice 选择 $$$i = 2$$$,概率为 $$$\frac{1}{3}$$$,并且球 $$$2$$$ 被移至篮子 $$$5$$$,从而抛出球 $$$1$$$。之后$$$a = [-1, 5, -1]$$$,流程结束。

第二个测试用例的答案是 $$$14$$$ (请注意,这两个球彼此相邻)。

第三个测试用例的答案是 $$$35$$$。

第四个测试用例的答案是 $$$\frac{220}{3}$$$。

在第五个测试用例中,由于最初只有一个球,所以答案是 $$$0$$$。