Masala #6JEPZREHC1

Komiljon va Sarvarjon bugun ham odatdagidek musobaqalashishmoqchi. Bugun ularda uzunligi n bo‘lgan, \([1,10^9]\) oralig‘idagi butun sonlardan tashkil topgan a massivi bor. Komlijon va Sarvarjon quyidagicha harakatlanishadi:
- Ishtirokchilar galma-gal yurishadi, birinchi bo‘lib Komiljon yuradi.
- Navbati kelgan ishtirokchi, istalgan \(i(1 ≤ i ≤ n)\) va \(x (1 < x ≤ a_i )\) sonlarini tanlaydi, keyin a massividan \(a_i\) ni olib tashlab, o‘rniga \(⌈ \frac{a_i}{x} ⌉\) ni yozadi. \(⌈h⌉\) bu h sonining tepaga yaxlitlaganini anglatadi. Misol uchun: \(⌈3⌉ = 3 \), \(⌈6.1⌉ = 7\) ,\( ⌈−2.4⌉ = − 2\) . Ko‘rsatilgan chegaralardan ma’lumki, \(a_i = 1 \)shartni qanoatlantiruvchi \(i\) ni tanlash mumkin emas.
- O‘z navbatida yurishni amalga oshira olmagan ishtirokchi, mag‘lub bo‘ladi.
Albatta ikkala ishtirokchi ham optimal o‘ynaydi.
a massivi tayyor, Komiljon va Sarvarjon birozdan so‘ng o‘yinni boshlaydi. Ammo hozir Salimjon, Sarvarjonning ukasi kelib a massividan bir nechta sonlarni shunday o‘chirmoqchi, o‘yinda akasi Sarvarjon aniq g‘olib chiqsin. Agar Salimjon ko‘pi bilan k ta sonni o‘chira olsa, u necha xil usulda buni qila oladi?

Sizning vazifangiz shu qiymatni \(10^9 + 7\) ga bo‘lgandagi qoldig‘ini topish.

Kirish oqimining birinchi qatorida ikkita son - \(n, k (1 ≤ n ≤ 3 * 10^5,0 ≤ k ≤ min(n,20)) \)massiv uzunligi va Salimjon massivdan o‘chirishi mumkin bo‘lgan elementlar soniga chegara.

Ikkinchi qatorda n ta natural sonlar - a massiv elementlari \((1 ≤ a_i ≤ 10^9)\) kiritiladi.