CNI "Tudor Vianu" PreOJI, clasa a X-a | Numararea din Ohio

"Doar în Ohio este posibil așa ceva..." - Baby Gronk

Cerință

În Ohio există o tastatură cu $N$ butoane conectată la un calculator, iar fiecărui buton îi este atrbiuită o valoare $a_i$. Totuși, fiind Ohio, tastatura este stricată. Atunci când se apasă o combinație de $K$ butoane, calculatorul va afișa pe ecran valoarea maximă dintre valorile butoanelor care au fost apăsate. Fiindcă Baby Gronk este din Ohio, acesta va apăsa pe toate combinațiile de $K$ butoane distincte posibile. Care este suma, modulo $1\ 000\ 000\ 007$, a valorilor care apar pe ecranul calculatorului?

Date de intrare

Pe prima linie a fișierului de intrare ohio.in se găsesc $N$ și $K$. Pe următoarea linie se găsesc $N$ valori $a_i$.

Date de ieșire

Pe prima linie a fișierului de ieșire ohio.out se va găsi răspunsul problemei, așa cum este descris în enunț.

Restricții și precizări

• $N \le 100\ 000$, $K \le 50$
• $a_i \le 10^9$
• Pentru $40$ puncte, $N \le 1000$

Exemplul 1

ohio.in

5
3 2 4 2 3 4 

ohio.out

39 

Explicație

Toate subseturile de valori corespunzătoare tuturor combinărilor posibile sunt: [2, 4, 2], [2, 4, 3], [2, 4, 4], [2, 2, 3], [2, 2, 4], [2, 3, 4], [4, 2, 3], [4, 2, 4], [4, 3, 4], [2, 3, 4].

Exemplul 2

ohio.in

5 
1 1 0 1 1 1 

ohio.out

4 

Exemplul 3

ohio.in

5 
2 3 3 4 0 0

ohio.out

31