沿着圆圈放置 $$$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$$$。