• “Idem prek k žnidaršiću, ti se igraj s klavirom, Perica”.

• ”Dobro tata, budem!”

I tako, Perica se počeo igrati s klavirom. Njegov klavir se sastoji od N tipaka. Na svakoj tipki piše njena vrijednost, ai. Perica kada svira klavir pritisne točno K različitih tipaka istovremeno. Klavir je pomalo neobičan i nakon pritiska K tipki istovremeno, on će odsvirati samo tipku na kojoj piše najveća vrijednost. Perica će odsvirati svaku kombinaciju K tipaka na klaviru i zanima ga koliko je suma vrijednosti tipaka koje će se čuti.

Pomognite Perici izračunati ostatak pri dijeljenju tog broja s 1 000 000 007.

Ulazni podaci

U prvom retku nalazi se dva prirodna broja N i K (1 <= N <= 100 000, 1 <= K <= 50).

U sljedećem retku nalazi se N brojeva ai (0 <= aij <= 10^9).

Izlazni podaci

U prvi i jedini redak ispišite broj iz teksta zadatka.

Bodovanje

U test podacima vrijednim 40% bodova vrijedit će dodatno 1 <= N <= 1000.

Primjeri test podataka

Ulaz

5 3
2 4 2 3 4

Izlaz

39

Ulaz

5 1
1 0 1 1 1

Izlaz

4

Ulaz

5 2
3 3 4 0 0

Izlaz

31