C. Азтай дэд дараалал

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Пэтя азын тоонд их дуртай. Азтай тоо нь зөвхөн $4$ ба $7$ гэсэн цифрүүдээс бүрдсэн эерэг бүхэл тоонууд юм. Жишээ нь $47$, $744$, $4$ нар нь азын тоо ба $5$, $17$, $467$ нар нь биш юм.

Пэтяд $n$ гишүүнтэй $a$ гэсэн бүхэл тоон дараалал байгаа.

$a$ дарааллын дэд дараалал гэдэг нь $a$ дарааллын зарим (эсвэл алийг нь ч биш) гишүүдийг устгах замаар гарч болох дарааллыг хэлэх юм.

Хоёр дэд дарааллын гишүүдийн дугааруудаас үүссэн хоёр олонлог ялгаатай бол ялгаатай дэд дарааллууд гэж үзнэ. Өөрөөр хэлбэл дэд дарааллуудыг харьцуулахад гишүүд нь давхацсан ч ялгаатай байх боломжтой юм. Тухайлбал дурын $n$ урттай дараалалд хоосон дэд дарааллыг нь оролцуулаад $2^{n}$ ялгаатай дэд дараалал байх юм.

Хэрэв тухайн дэд дарааллыг хэрэв урт нь $k$ ба азын тоо давтагдаж ороогүй бол азтай дэд дараалал гэнэ. Харин азын биш тоо давтагдаж болно.

Пэтяд $a$ дарааллын азтай дэд дарааллын тоог олоход нь туслаарай. Пэтягийн эцэг эх нь түүнийг том тоогоор тоглохыг хориглодог тул хариуг $1000000007$ $(10^{9} + 7)$ тоонд хуваан үлдэгдлийг олох хэрэгтэй болжээ.

Оролт

Эхний мөрөнд $n$ ба $k$ $(1 ≤ k ≤ n ≤ 10^{5})$ тоонууд байна. Дараагийн мөрөнд $a$ дарааллыг илэрхийлэх $a_{i}$ ($1 ≤ a_{i} ≤ 10^{9}$) гэсэн $n$ тоо байна.

Гаралт

Бодлогын хариуг $1000000007$ $(10^{9} + 7)$ гэсэн анхны тоонд хуваан үлдэгдлийг ол.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
3 2
10 10 10
Гаралт
3
Оролт
4 2
4 4 7 7
Гаралт
4

Тэмдэглэл

Эхний жишээнд нөхцөлд шаардагдсан урт бүхий гурван дэд дараалал бүгд азтай дэд дараалал байна.

Хоёр дахь жишээнд дөрвөн азтай дэд дараалал бий. Гишүүдийн дугаараар нь илэрхийлэн бичвэл (1-ээс эхлэн дугаарласан): $(1, 3)$, $(1, 4)$, $(2, 3)$, $(2, 4)$.

Сэтгэгдлүүдийг ачааллаж байна...