G. Wafu!
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Чтобы улучшить свои навыки в математике, Кудрявка получает набор $$$S$$$, который состоит из $$$n$$$ различных положительных целых чисел.

Изначально её счёт равен $$$1$$$. Она может выполнять произвольное количество следующих операций над набором, если он не пуст:

  1. Пусть минимальное значение в $$$S$$$ равно $$$m$$$.
  2. Умножить свой счёт на $$$m$$$.
  3. Удалить $$$m$$$ из $$$S$$$.
  4. Для каждого целого числа $$$i$$$, такого что $$$1 \le i \lt m$$$, добавить $$$i$$$ в набор $$$S$$$. Можно показать, что на этом шаге дубликаты не добавляются.

Ей очень понравилось выполнять операции, но после $$$k$$$ операций она понимает, что забыла свой счёт. Пожалуйста, помогите ей определить свой счёт, по модулю $$$10^9+7$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$).

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$s_1, s_2, \dots, s_n$$$ ($$$1 \le s_i \le 10^9$$$, $$$s_i \neq s_j$$$) — элементы начального набора $$$S$$$. Гарантируется, что набор $$$S$$$ не пуст перед выполнением каждой из $$$k$$$ операций.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
4
2 3
1 3
3 6
5 1 4
2 100
2 100
5 15
1 2 3 4 5
Выходные данные
3
24
118143737
576
Примечание

Давайте смоделируем процесс в первом примере:

$$$$$$ \{1,3\} \xrightarrow{\text{удалить}\ 1} \{3\} \xrightarrow[\text{добавить}\ 1,2]{\text{удалить}\ 3} \{1,2\} \xrightarrow{\text{удалить}\ 1} \{2\} $$$$$$

Удаленные значения: $$$1$$$, $$$3$$$ и $$$1$$$ соответственно, так что её счёт равен $$$1\times 3\times 1 = 3$$$.

Во втором примере ответ равен $$$1 \times 4 \times 1 \times 2 \times 1 \times 3 = 24$$$.