eolymp
bolt
Try our new interface for solving problems
Məsələlər

Симпатичные узоры 2

Симпатичные узоры 2

Zaman məhdudiyyəti 5 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Компания BrokenTiles планирует заняться выкладыванием во дворах у состоятельных клиентов узор из черных и белых плиток, каждая из которых имеет размер 1×1 метр. Известно, что дворы всех состоятельных людей имеют наиболее модную на сегодня форму прямоугольника n×m метров.

Однако при составлении финансового плана у директора этой организации появилось целых две серьезных проблемы: во первых, каждый новый клиент очевидно захочет, чтобы узор, выложенный у него во дворе, отличался от узоров всех остальных клиентов этой фирмы, а во вторых, этот узор должен быть симпатичным.

Как показало исследование, узор является симпатичным, если в нем нигде не встречается квадрата 2×2 метра, полностью покрытого плитками одного цвета.

Для составления финансового плана директору необходимо узнать, сколько клиентов он сможет обслужить, прежде чем симпатичные узоры данного размера закончатся. Помогите ему!

Giriş verilənləri

На первой строке входного файла находятся два натуральных числа n и m. 1 ≤ n·m300.

Çıxış verilənləri

Выведите в выходной файл единственное число — количество различных симпатичных узоров, которые можно выложить во дворе размера n×m по модулю 2^30 + 1. Узоры, получающиеся друг из друга сдвигом, поворотом или отражением считаются различными.

Nümunə

Giriş verilənləri #1
1 1
Çıxış verilənləri #1
2
Müəllif Михаил Дворкин
Mənbə Зимняя школа, Харьков 2011, День 3