G. Wafu！

每次测试的时间限制：$3$ 秒
每次测试的内存限制：$256$ 兆字节

为了帮助提高数学成绩，Kudryavka 得到了一个包含 $n$ 个互不相同的正整数的集合 $S$。

最初，她的分数为 $1$。在集合非空的情况下，她可以执行任意次以下操作：

• 设 $S$ 中的最小值为 $m$。
• 将她的分数乘以 $m$。
• 从 $S$ 中移除 $m$。
• 对每个满足 $1 \le i < 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 \ne s_j$）——初始集合 $S$ 中的元素。保证在每次操作执行前集合 $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\}$

• 移除 $1$，加入 $1$ 以下的数（无），集合变为 $\{3\}$，分数乘 $1$ → $1$
• 移除 $3$，加入 $1,2$，集合变为 $\{1,2\}$，分数乘 $3$ → $3$
• 移除 $1$，加入 $1$ 以下的数（无），集合变为 $\{2\}$，分数乘 $1$ → $3$

被移除的数依次为 $1,3,1$，所以分数为 $1 \times 3 \times 1 = 3$。

第二个测试用例：分数为 $1 \times 4 \times 1 \times 2 \times 1 \times 3 = 24$。