← 返回题目列表

Codeforces · 2131/G

G. 哇啊!

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

为了帮助提高她的数学能力,Kudryavka 获得了一组 $$$S$$$,其中包含 $$$n$$$ 不同的正整数。

最初,她 分数 是 $$$1$$$。如果集合不为空,她可以对集合执行任意数量的以下操作:

  1. 设 $$$S$$$ 的最小值为 $$$m$$$。
  2. 乘以她 分数 作者:$$$m$$$。
  3. 从$$$S$$$ 中删除$$$m$$$。
  4. 对于每个满足 $$$1 \le i \lt m$$$ 的整数 $$$i$$$,将 $$$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$$$ 的元素。在执行每一次$$$k$$$操作之前,保证集合$$$S$$$不为空。

保证所有测试用例的 $$$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$$$。