G. Клацанье шарами
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Rammstein - Ausländer
ඞ

По кругу расставлены $$$m$$$ корзин, пронумерованных от $$$1$$$ до $$$m$$$ по часовой стрелке (корзина $$$m$$$ находится рядом с корзиной $$$1$$$). Кроме того, имеется $$$n$$$ шаров, причем шар $$$i$$$ первоначально помещен в корзину $$$a_i$$$, и ни одна корзина не содержит более одного шара.

Алисе разрешено выполнять следующую операцию, которая всегда занимает ровно одну секунду, независимо от того, перемещаете/выбрасываете вы шар или нет:

  • Алиса выбирает целое число $$$i$$$ между $$$1$$$ и $$$n$$$ равномерно случайным образом.
  • Если шар $$$i$$$ был выброшен ранее, ничего не делать.
  • В противном случае, шар $$$i$$$ перемещается из корзины, в которой он находится в данный момент, в следующую корзину (по часовой стрелке). Если в корзине, в которую перемещается шар, сейчас находится другой шар $$$j$$$, выбросить шар $$$j$$$.

Она повторяет эту операцию до тех пор, пока не останется ровно один шар. Вычислите математическое ожидание времени (в секундах), необходимого Алисе для завершения процесса.

Можно доказать, что ответ можно представить в виде рационального числа $$$\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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число: математическое ожидание времени (в секундах), необходимое Алисе для завершения процесса, по модулю $$$10^9 + 7$$$.

Пример
Входные данные
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
Выходные данные
600000042
14
35
333333409
0
Примечание

В первом наборе входных данных Алиса могла бы действовать следующим образом (мы определяем $$$a_i = -1$$$, если шар $$$i$$$ был выброшен):

  • Изначально $$$a = [5, 1, 4]$$$.
  • Алиса выбирает $$$i = 2$$$ с вероятностью $$$\frac{1}{3}$$$, и шар $$$2$$$ перемещается в корзину $$$2$$$. После этого $$$a = [5, 2, 4]$$$.
  • Алиса выбирает $$$i = 2$$$ с вероятностью $$$\frac{1}{3}$$$, и шар $$$2$$$ перемещается в корзину $$$3$$$. После этого $$$a = [5, 3, 4]$$$.
  • Алиса выбирает $$$i = 2$$$ с вероятностью $$$\frac{1}{3}$$$, и шар $$$2$$$ перемещается в корзину $$$4$$$. Поскольку в корзине $$$4$$$ ранее находился шар $$$3$$$, этот шар выбрасывается. После этого $$$a = [5, 4, -1]$$$.
  • Алиса выбирает $$$i = 3$$$ с вероятностью $$$\frac{1}{3}$$$. Шар $$$3$$$ уже был выброшен, поэтому ничего не происходит. После этого $$$a = [5, 4, -1]$$$.
  • Алиса выбирает $$$i = 2$$$ с вероятностью $$$\frac{1}{3}$$$, и шар $$$2$$$ перемещается в корзину $$$5$$$, из которой выбрасывается шар $$$1$$$. После этого $$$a = [-1, 5, -1]$$$, и процесс завершается.
Ответ для этого набора входных данных равен $$$\frac{189}{5}$$$.

Ответ для второго набора входных данных равен $$$14$$$ (обратите внимание, что эти два шара находятся рядом друг с другом).

Ответ для третьего набора входных данных равен $$$35$$$.

Ответ для четвертого набора входных данных равен $$$\frac{220}{3}$$$.

В пятом наборе входных данных, поскольку изначально имеется только один шар, ответ равен $$$0$$$.