Porsuqçığa Hədiyyə#1860
Donuzcuq bir dəfə Vinni-Puxa danışdı ki, əgər 2\times 2 ölçüsündə bir kvadrat varsa və hər bir hüceyrəsinə ən çox bir palıd qoyulursa, bu kvadrat ya gözəl, ya da çirkin ola bilər. Donuzcuq bütün gözəl şəkilləri də sadaladı.
Bir müddət sonra Vinni Donuzcuğa hədiyyə vermək qərarına gəldi — hündürlüyü və eni olan bir düzbucaqlı, burada bütün 2\times 2 kvadratlar gözəldir. Vinni-Puxa bu işdə kömək edin və bunun neçə fərqli üsulla edilə biləcəyini hesablayın.
Birinci sətrdə və təbii ədədləri verilir (2 \leq m \leq 8; 2 \leq n \leq 100). İkinci sətrdə gözəl kvadratların sayı olan təbii ədəd verilir. Sonra kvadratların təsviri gəlir: hər biri üçün iki sətr, hər sətrdə iki ədəd. palıd, isə onun olmamasını göstərir. Bütün kvadratlar fərqlidir.
Bütün kvadratların gözəl olduğu düzbucaqlıların sayını çıxarın. Cavabın 10^9-u keçməyəcəyinə zəmanət verilir.
Nümunə 1