Simpatik naxışlar 2#1866
BrokenTiles zəngin müştərilərin həyətlərində 1 \times 1 metr ölçülü qara və ağ plitələrdən istifadə edərək naxışlar yaratmağı planlaşdırır. Bütün bu müştərilərin həyəti n \times m metr ölçülü düzbucaqlılardır.
Lakin şirkətin direktoru maliyyə planlaması zamanı iki əsas problemə rast gəlir. Birincisi, hər yeni müştəri istəyir ki, onun həyətindəki naxış əvvəlki bütün müştərilərin həyətlərindəki naxışlardan fərqli olsun. İkincisi isə, hər bir naxış cazibədar olmalıdır.
Naxış o zaman cazibədar sayılır ki, orada heç bir yerdə eyni rəngli plitələrlə tam örtülmüş 2 \times 2 ölçülü kvadrat olmasın.
Direktor bilməlidir ki, müəyyən ölçüdə cazibədar naxışlar bitənə qədər ən çox neçə müştəriyə xidmət göstərə bilər. Ona kömək edin!
Birinci sətirdə iki müsbət tam ədəd və verilir. 1 \leq n \cdot m \leq 300.
Bir tam ədəd çap edin — n \times m ölçülü həyətdə yaratmaq mümkün olan fərqli cazibədar naxışların sayını 2^{30} + 1 modulunda. Şiftləmə, fırlatma və ya əks etdirmə ilə birindən digərinə keçmək mümkün olan naxışlar fərqli sayılır.
Nümunə 1