33796번 - Another Expected Value Problem 다국어

문제

You are given an array $a$ of $n$ integers. You then perform the following process $k$ times.

• Choose an integer $i$ where 1ドル \le i \le n,ドル uniformly at random.
• For each 1ドル \le j \le n,ドル move $a_j$ one unit closer to $a_i$. Formally, for each $j,ドル
  • If $a_j < a_i,ドル increment $a_j$ by 1ドル$
  • If $a_j > a_i,ドル decrement $a_j$ by 1ドル$
  • If $a_j = a_i,ドル do not modify the value of $a_j$.

After performing this process $k$ times, you select an integer $i$ where 1ドル \le i \le n$ uniformly at random. What is the expected value of $a_i$?

It can be shown that this value can be represented as $\frac{P}{Q}$ where $P$ and $Q$ are coprime integers and $Q \not\equiv 0 \mod 10^9+7$. Print the value of $P\cdot Q^{-1}$ modulo 10ドル^9+7$.

입력

The first line of the input contains a single integer $t$ (1ドル\le t\le 10^4$) --- the number of test cases.

The first line of each test case contains two integers $n$ and $k$ (1ドル\le n,k \le 2\cdot 10^5$) --- the length of the array and the number of operations you will perform.

The second line of each test case will contain $n$ integers $a_1, a_2, \cdots a_n$ (1ドル \le a_i \le 10^9$) --- the initial array $a$.

It is guaranteed that the sum of $n$ over all test cases, and the sum of $k$ over all test cases, do not exceed 2ドル\cdot 10^5$.

출력

For each test case, output a single line containing the expected value of $a_i$ at the end of this process, modulo 10ドル^9+7$ as described above.

제한

노트

In the first sample case, since all elements of $a$ are initially equal, none of them will change after any of the $k=5$ operations. Therefore, the final array will be $[8, 8, 8],ドル so the expected value of a random element of the final array is 8ドル$.

In the second sample case, there is a 50ドル\%$ chance of choosing $i = 1$ in the operation, and a 50ドル\%$ chance of choosing $i = 2$.

1. If $i = 1$ is chosen, all elements of the array will move closer to $a_1 = 10,ドル so $a$ will go from $[10, 11]$ to $[10, 10]$. The expected value of a random element of this array is 10ドル$.
2. If $i = 2$ is chosen, all elements of the array will move closer to $a_2 = 11,ドル so $a$ will go from $[10, 11]$ to $[11, 11]$. The expected value of a random element of this array is 11ドル$.

So there is a 50ドル\%$ chance of the expected value being 10ドル,ドル and a 50ドル\%$ chance of it being 11ドル$. Therefore, the final expected value is 10ドル.5 = \frac{21}{2},ドル which is equivalent to 5000000014ドル$ modulo 10ドル^9+7$.