Kompānija «Galvassāpes», kas izgatavo loģiskās rotaļlietas bērniem, piedāvā savu jauno mozaīku. Tajā ietilpst taisnstūrveida plāksnīte, kuras izmēri ir N*M kvadrātiņi. Daži plāksnītes kvadrāti sākumā ir aizņemti un tajos neko nedrīkst likt. 

Vēl komplektā ietilpst deviņu dažādu tipu detaļas mozaīkas salikšanai. Detaļu tipi ir sanumurēti no 1 līdz 9 :

Katru detaļas drīkst novietot tikai plāksnītes brīvajos kvadrātiņos. Katras detaļas konstrukcija ļauj to novietot uz plāksnītes tikai tādā veidā, kā redzams zīmējumā, un neatļauj to novietot kaut kā pagrieztu. Visas detaļas ir dažādas un nedrīkst ar pagriezienu palīdzību no vienas detaļas iegūt kādu citu. Detaļu konstrukcija ir labi pārdomāta, tāpēc ar figūru 3 un 4 palīdzību var, piemēram, salikt kvadrātu 2*2. Komplektā detaļu ir tik daudz, lai nebūtu jāuztraucas ka tās varētu beigties. Katra tipa detaļām ir sava unikāla krāsa. Mozaīku sauc par saliktu, ja visi plāksnītes kvadrātiņi ir noklāti. Divas mozaīkas sauc par dažādām, ja ir kvadrātņi, kas noklāti ar dažādas krāsas detaļām.

Uzrakstiet programmu, kas noskaidro, cik dažādas mozaīkas var izveidot uz dotās plāksnītes.

Ievaddatu pirmajā rindā doti divi naturāli skaitļi N (plāksnītes vertikālais izmērs) un M(plāksnītes horizontālais izmērs), kas atdalīti ar tukšumsimbolu. Zināms, ka 1< M <8, 1<N<21 un ka dotajiem ievaddatiem dažādo mozaīku skaits nepārsniegs 10¹⁵.
Nākamajās N faila rindās katrā atrodas tieši M cipari - 0 vai 1, kas atdalīti ar tukšumsimboliem. Vieninieks apzīmē aizņemto kvadrātu, nulle - tukšo.

Izvaddatu pirmajā rindā jāizvada viens vesels skaitlis - dažādo iespējamo mozaīku skaits.

Uzdevums ņemts no Baltkrievijas 2001. gada sacensībām.