Maheshmati and Sangu are playing a game. First, Maheshmati gives Sangu a sequence of $N$ distinct integers $a_1, a_2, \dots, a_N$ (not necessarily sorted) and an integer $K$. Sangu has to create all subsequences of this sequence with length $K$. For each subsequence, he has to write down the product of $K-2$ integers: all elements of this subsequence except the minimum and maximum element.
Sangu wins the game if he is able to write down all these numbers and tell Maheshmati their product (modulo $10^9+7$, since it can be very large). However, Sangu is a very lazy child and thus wants you to help him win this game. Compute the number Sangu should tell Maheshmati!

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $K$.
- The second line contains $N$ space-separated integers $a_1, a_2, \dots, a_N$.

-----Output-----
For each test case, print a single line containing one integer — the product of all numbers written down by Sangu modulo $10^9+7$.

-----Constraints-----
- $1 \le T \le 10$
- $3 \le N \le 5,000$
- $3 \le K \le N$
- $1 \le a_i \le 10,000$ for each valid $i$
- the numbers $a_1, a_2, \dots, a_N$ are pairwise distinct

-----Subtasks-----
Subtask #1 (20 points): $1 \le N \le 10$
Subtask #2 (80 points): original constraints

-----Example Input-----
1
4 3 
1 2 3 4 

-----Example Output-----
36

-----Explanation-----
Example case 1: There are four possible subsequences:
- $[1, 2, 3]$ (Sangu should write down $2$.)
- $[1, 3, 4]$ (Sangu should write down $3$.)
- $[1, 2, 4]$ (Sangu should write down $2$.)
- $[2, 3, 4]$ (Sangu should write down $3$.)
The required product is $2 \cdot 3 \cdot 2 \cdot 3 = 36$.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# cook your dish here\nMOD = (10**9) + 7\n\ndef nCrModpDP(n, r, p): \n  \n # The array C is going to store \n # last row of pascal triangle \n # at the end. And last entry  \n # of last row is nCr \n C = [0] * (n + 1); \n \n # Top row of Pascal Triangle \n C[0] = 1;  \n \n # One by constructs remaining  \n # rows of Pascal Triangle from  \n # top to bottom \n for i in range(1, (n + 1)): \n   \n  # Fill entries of current  \n  # row using previous row \n  # values \n  j = min(i, r);  \n  while(j > 0): \n   C[j] = (C[j] + C[j - 1]) % p; \n   j -= 1; \n return C[r]; \n \n# Lucas Theorem based function that   \n# returns nCr % p. This function \n# works like decimal to binary  \n# conversion recursive function. \n# First we compute last digits of  \n# n and r in base p, then recur \n# for remaining digits \ndef nCrModpLucas(n, r, p): \n  \n # Base case \n if (r == 0): \n  return 1; \n   \n # Compute last digits of n \n # and r in base p \n ni = int(n % p); \n ri = int(r % p); \n   \n # Compute result for last digits  \n # computed above, and for remaining  \n # digits. Multiply the two results  \n # and compute the result of  \n # multiplication in modulo p. \n # Last digits of n and r \n return (nCrModpLucas(int(n / p), int(r / p), p) * \n   nCrModpDP(ni, ri, p)) % p;\n\nfor _ in range(int(input())):\n \n n , k = list(map( int, input().split()))\n \n arr = list( map( int, input().split()) )\n \n arr = sorted(arr)\n \n value = nCrModpLucas(n-1,k-1,MOD)\n \n ans = 1\n \n \n \n for x in range(1,n-1):\n  \n  if (n - x - 1) >= (k-1) :\n   \n   temp1 = nCrModpLucas(n-x-1,k-1,MOD)\n  else:\n   temp1 = 0\n   \n  if x >= (k-1):\n   \n   temp2 = nCrModpLucas(x,k-1,MOD)\n  else:\n   temp2 = 0 \n   \n   \n  # print(value,ans,temp1,temp2)\n  ans = ( ans * (arr[x]**( value - temp2 - temp1 )) )%MOD\n  \n print(ans)\n   \n  \n  \n \n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13619