CF2131G Wafu!

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 < 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$$$.

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$$$.

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

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$$$.