Tomy

Tomy are un vector cu $N$ numere întregi distincte. Într-o singură operație, Tomy va alege un subșir nevid și va găsi valoarea mediană al subșirului ales.

Tomy poate alege cel mult $K$ subșiruri, dar toate acestea trebuie să fie și distincte.

Mediana unui subșir de lungime $l$ este al $⌊\frac{l+1}{2}⌋$ element după sortarea subșirului.

Tomy trebuie să aleagă subșirurile astfel încât suma tuturor valorilor mediane să fie maximă. Deoarece suma poate să fie mare, afișati modulo $10^9 + 7$.

Date de intrare

Prima linie din fișierul tomy.in conține un număr întreg $T$ - numărul de întrebări.

Cele $T$ întrebări au câte două linii cu informații. În total o să fie $2 \cdot T$ linii.

Pe prima linie se găsesc două numere întregi $N,K$.
A doua linie conține $N$ numere întregi distincte $a_1,a_2,...,a_N$, acestea fiind valorile din vectorul lui Tomy.

Suma valorilor $N$ din cele $T$ întrebări nu depășește $5 \cdot 10^5$.

Date de ieșire

Pentru fiecare întrebare, afișați pe câte o linie în fișierul tomy.out un număr întreg, acesta fiind răspunsul întrebări, modulo $10^9 + 7$.

Restricții și precizări

• $1 \leq T \leq 1 \ 000$;
• $1 \leq N \leq 10^5$;
• $1 \leq K < min(2^N,10^{18})$.
• $-10^9 \leq a_i \leq 10^9$

Exemplu

tomy.in

1
3 4
1 3 5

tomy.out

14

Explicație

Cele $4$ subșiruri din șir sunt $\{ 3 \}$, $\{ 5 \}$, $\{ 3,5 \}$, $\{ 1,3,5 \}$, iar medianele lor sunt $3,5,3,3$, care sunt maxime.

Astfel, răspunsul este $3 + 5 + 3 + 3 = 14$.