|
Симпатичные узоры
(Время: 1 сек. Память: 16 Мб Сложность: 66%)
Компания BrokenTiles планирует заняться выкладыванием во дворах у состоятельных клиентов узор из черных и белых плиток, каждая из которых имеет размер 1×1 метр. Известно, что дворы всех состоятельных людей имеют наиболее модную на сегодня форму прямоугольника M×N метров.
Однако при составлении финансового плана у директора этой организации появилось целых две серьезных проблемы: во первых, каждый новый клиент очевидно захочет, чтобы узор, выложенный у него во дворе, отличался от узоров всех остальных клиентов этой фирмы, а во вторых, этот узор должен быть симпатичным. Как показало исследование, узор является симпатичным, если в нем нигде не встречается квадрата 2×2 метра, полностью покрытого плитками одного цвета. На рисунке 1 показаны примеры различных симпатичных узоров, а на рисунке 2 – несимпатичных.
Для составления финансового плана директору необходимо узнать, сколько клиентов он сможет обслужить, прежде чем симпатичные узоры данного размера закончатся. Помогите ему!
Входные данные
В первой строке входного файла INPUT.TXT находятся два положительных целых числа, разделенные пробелом – M и N (1 ≤ M∙N ≤ 30).
Выходные данные
Выведите в выходной файл OUTPUT.TXT единственное число – количество различных симпатичных узоров, которые можно выложить во дворе размера M×N. Узоры, получающиеся друг из друга сдвигом, поворотом или отражением считаются различными.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 2 | 14 |
| 2 | 3 3 | 322 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
