Perica

-"Σταματάω από το σπίτι του Žnidaršić, συνέχισε να παίζεις πιάνο, Perica".
-"Εντάξει, μπαμπά, θα το κάνω!"

Και έτσι, η Perica άρχισε να παίζει πιάνο. Το πιάνο του αποτελείται από ~N~ πλήκτρα. Κάθε κλειδί έχει μια τιμή γραμμένη πάνω του, ~a_i~. Όταν ο Perica παίζει πιάνο, πατάει ακριβώς ~K~ διαφορετικά πλήκτρα ταυτόχρονα. Το πιάνο είναι λίγο περίεργο γιατί, αφού πατήσετε τα ~K~ πλήκτρα ταυτόχρονα, θα παίξει μόνο το πλήκτρο με τη μεγαλύτερη τιμή. Η Perica πρόκειται να παίξει κάθε συνδυασμό πλήκτρων ~K~ στο πιάνο και θέλει να μάθει το άθροισμα των τιμών των πλήκτρων που θα παιχτούν.
Βοηθήστε τον Perica να προσδιορίσει το υπόλοιπο αυτού του αριθμού ως modulo ~1\,000\,000\,007~.

Είσοδος

Η πρώτη γραμμή εισόοδυ περιέχει δύο ακέραιους ~N~ και ~K\;(1 \leq N \leq 100\,000,\;1 \leq K \leq 50)~.
Η ακόλουθη γραμμή εισόδου περιέχει ~N~ ακέραιους αριθμούς ~a_i\;(0 \leq a_{ij} \leq 10^9)~

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον απαιτούμενο αριθμό από την εργασία.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας ~40~% των συνολικών πόντων, θα έχει επιπλέον ~1 \leq N \leq 1000~.

Παραδείγματα

input

5 3
2 4 2 3 4

output

39

Επεξήγηση του 1ου παραδείγματος: Όλες οι επιλογές των πλήκτρων ~K~ είναι: ~[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]~.

input

5 1
1 0 1 1 1

output

4

input

5 2
3 3 4 0 0

output

31