G. Wafu!
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

To help improve her math, Kudryavka is given a set $$$S$$$ that consists of $$$n$$$ distinct positive integers.

Initially, her score is $$$1$$$. She can perform an arbitrary number of the following operations on the set if it is not empty:

  1. Let the minimum value of $$$S$$$ be $$$m$$$.
  2. Multiply her score by $$$m$$$.
  3. Remove $$$m$$$ from $$$S$$$.
  4. For every integer $$$i$$$ such that $$$1 \le i \lt m$$$, add $$$i$$$ to the set $$$S$$$. It can be shown that no duplicates are added during this step.

She is addicted to performing operations, but after $$$k$$$ operations, she realizes she forgot her score. Please help her determine her score, modulo $$$10^9+7$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$).

The second line of each test case contains $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ ($$$1 \le s_i \le 10^9$$$, $$$s_i \neq s_j$$$) — the elements of the initial set $$$S$$$. It is guaranteed that the set $$$S$$$ is not empty before each of the $$$k$$$ operations is performed.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output an integer indicating the answer modulo $$$10^9+7$$$.

Example
Input
4
2 3
1 3
3 6
5 1 4
2 100
2 100
5 15
1 2 3 4 5
Output
3
24
118143737
576
Note

Let us simulate the process in the first test case:

$$$$$$ \{1,3\} \xrightarrow{\text{remove}\ 1} \{3\} \xrightarrow[\text{add}\ 1,2]{\text{remove}\ 3} \{1,2\} \xrightarrow{\text{remove}\ 1} \{2\} $$$$$$

The removed values are $$$1$$$, $$$3$$$ and $$$1$$$ respectively, so her score is $$$1\times 3\times 1 = 3$$$.

In the second test case, the answer is $$$1 \times 4 \times 1 \times 2 \times 1 \times 3 = 24$$$.