8. Ozajstná veda

Kleofáš sa rád hrá s číslami. Na matfyzáka by sa to aj celkom patrilo. Preto sa už dlho tešil, ako si v zimnom semestri zapíše numeriku a začne sa na nej oddávať šťastnému rátaniu, pričítavaniu, odčítavaniu a iterovaniu vzorcov pri riešení diferenciálnych rovníc – no proste samým úžasným veciam.

Ani numerika však Kleofáša neuspokojila. Stále bol akýsi nesvoj. Nemal pocit absolútneho naplnenia svojej bezhraničnej číselnej zvedavosti. Veci mu nedávali zmysel. Videl čísla a nevedel čo znamenajú. Nevedel, čo sa mu snažia povedať. Nevedel z nich získať poznanie. Vrcholom bolo, keď začal v číslach aj snívať. Začali sa mu totiž snívať dlhé číselné postupnosti. Vtedy sa Kleofáš rozhodol, že vyhľadá pomoc odborníka. Sadol za internet a o chvíľu mal dohodnuté stretnutie s numerologičkou 83470u.

83474 mu povedala nasledovné múdrosti: Každé číslo niečo znamená. To, čo dané číslo znamená, sa dá určiť z jeho cifier. Traktor. Každý si je strojcom svojho šťastia a vyberá si, čo sa mu stane. Rovnaké šťastie znamená, že sa porušil metrix. Čím viac možností, tým viac abibash.

Kleofáš síce nerozumel ani slovo, ale rozhodol sa, že tomu bude veriť a pokúsil sa 83471n3 slová nejako interpretovať. Každé číslo asi bude znamenať nejakú udalosť, ktorá sa mu udeje. To, aká bude, sa dá určiť z cifier daného čísla. Všetci vedia, že najšťastnejšie číslo je 47. Šťastné cifry teda musia byť štvorka a sedmička. No a úplne šťastné udalosti teda budú zodpovedať takým číslam, ktorých úplne každá cifra je štvorka alebo sedmička.

Kleofášov život ešte nie je jednoznačne určený. Vie si vybrať, ktorých \(k\) spomedzi \(n\) udalostí, ktoré sa mu prisnili, sa mu naozaj stane. Určite však nechce, aby sa mu stali dve rovnaké šťastné udalosti, lebo by tým pokazil metrix. (Nech už to znamená, čo chce.) Abibash? Jasné, že Kleofáš chce byť čo najviac abibash! (Nech už to znamená, čo chce.)

Úloha

Prirodzené čísla delíme na šťastné a ostatné. Šťastné sú tie, ktorých každá cifra je 4 alebo 7.

Kleofáš má postupnosť \(n\) prirodzených čísel a tiež číslo \(k\). Zo svojej postupnosti chce vybrať presne \(k\)-prvkovú podpostupnosť. Vo vybranej postupnosti sa nesmú vyskytovať dve rovnaké šťastné čísla.

Vašou úlohou je zistiť, koľkými spôsobmi môže Kleofáš vybrať vyhovujúcu \(k\)-prvkovú podpostupnosť.¹ Dva spôsoby považujeme za rôzne, ak vyberieme prvky na rôznych indexoch, bez ohľadu na to, aké majú hodnoty.

Formát vstupu

V prvom riadku vstupu sú prirodzené čísla \(n\) a \(k\). Platí \(1 \leq k \leq n \leq 10^5\). Číslo \(n\) udáva počet čísel, ktoré sa Kleofášovi snívali a číslo \(k\) je počet čísel, ktoré z nich chce Kleofáš vybrať.

V druhom riadku je postupne \(n\) kladných celých čísel, ktoré sa Kleofášovi snívali. Každé z nich je menšie ako \(10^9\).

Formát výstupu

Vypíšte jeden riadok a v ňom jedno celé číslo: počet spôsobov ktorými vie Kleofáš vybrať vyhovujúcu podpostupnosť. Keďže toto číslo môže byť veľmi veľké, vypočítajte a vypíšte ho modulo \(10^9+7\).

Príklady

Input:

5 2
7 7 3 7 77

Output:

7

Existuje desať možností ako vybrať 2-prvkovú podpostupnosť danej postupnosti. Z nich však tri nevyhovujú, lebo obsahujú dve rovnaké šťastné udalosti. Vyhovujúcich výberov je teda len \(10-3 = 7\).

Input:

5 3
3 7 77 7 77

Output:

4

Tu si Kleofáš musí vybrať udalosť 3, jednu z dvoch udalostí 7 a jednu z dvoch udalostí 77.

Input:

34 17
14 14 14 ... 14 14 14

Output:

333606206

V tomto príklade vstupu je v druhom riadku postupnosť 34 štrnástok. Číslo 14 nie je šťastné. Kleofáš si teda môže vybrať ako svoju podpostupnosť ľubovoľných 17 prvkov danej postupnosti. Všimnite si, že počet možných výberov je veľký, a že vypísaná odpoveď je rovná zvyšku, ktorý tento počet dáva po delení \(1\,000\,000\,007\).