Masala #0219

Xotira 16 MB Vaqt 1000 ms
14

Alien

Yaqinda kosmik kemamiz boshqa gallaktikadagi yerga o`xshash sayyoraga borib qo`ndi, bu yerda ham tirik mavjudod bor ekan, baxtga ko`ra ular ham idrok etish va hatto musiqa kuylab pianino chalishni yaxshi ko`rishar ekan. U yerdagilardagi o`zgacha xususiyat ularda qo`l barmoqlari aynan 10 ta emas ekan hammada har xil, \(K\) ta ekan, bizni yangicha pianinoda esa \(N\) ta klavish bo`lib har bir klavishni o`zining yangicha xususiyati bor, har bir klavishda aniq bir tovush \(A_i\) balandligi bor ba’zilarining tovush balandligi bir xil, agar siz 2 ta bir xil balandlikdagi tovush chiqaradigan klavishni bossangiz ixtiyoriy biri ovoz chiqaradi, ammo 2 ta turli xil ovozdagini bossangiz faqat baland ovozlisi ovoz chiqaradi, bu holat bir nechta klavishni bosganda ham shunday, endi biz o`zga sayyorlik do`stimizga shu holatda har doim har xil usuldagi urunishlarni hamma barmoqlari bilan tengidan klavishlarni bosganida umumiy tovush balandligining yig`indisi qancha bo`lashini so`ragandik, u buni hisoblab bera olmadi, endi siz ularni mushkulini yengillashtirish uchun bizga dastur tuzib yordam bering.


Kiruvchi ma'lumotlar:

Yagona qatorda \(N\) va \(K\) \((1 \le N \le 10^5, 1 \le K \le 50)\) butun sonlari beriladi mos ravishda bizning pianinodagi klavishlar soni va o`zga sayyoralikning barmoqlari soni.

Keyin qatorda \(N\) ta butun \(A_i (0 \le A_i \le 10^9)\) sonlari klavishlarning ovoz balandligi beriladi.


Chiquvchi ma'lumotlar:

Yagona butun son masala yechimini \(10^9+7\) ga bo`lgandagi qoldiqni chiqaring.


Misollar
# input.txt output.txt
1
5 3
2 4 2 3 4
39
2
5 1
1 0 1 1 1
4