Masala #1088

Sizda \(N \times M\) katakchalardan iborat maydon bor, bu maydonda ba’zi  katakchalar kulrang rangda bo’yalgan va qolgan katakchalar bo’sh. Siz shu bo’sh kataklarni quyidagi 9 turdagi naqshlardan xoxlaganingizcha foydalanib to’ldirishingiz kerak:

Yagona shart naqshlarni burish mumkin emas, ya’ni 3-turdagi naqshni burgan holda 4-turdagi naqsh shaklini hosil qilib bo’lmaydi. 

Misol uchun quyidagi \(4 \times 3\) maydonni 6 xil usulda naqshlar bilan to’ldirish mumkin:

Sizga \(N \times M\) maydonning dastlabki holati berilgan, siz bu maydonga naqshlarni necha xil usulda joylashtirib to’ldirish mumkinligini aniqlang.

Kirish faylining dastlabki satrida ikkida butun son, \(N(1 \leq N \leq 40)\)va \(M(1 \leq M \leq 8)\) sonlari berilgan. Keyingi \(N\) ta satrda \(M\)  ta butun son, 0 yoki 1 sonlari kiritiladi, bunda 0 bo’sh katakchani, 1 esa kulrang katakchani ifodalaydi.

Chiqish faylining yagona satrida bitta butun son, berilgan maydonga naqshlarni necha xil usulda joylashtirib to’ldirish mumkinligini chop eting.