Masala G

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.