Страница: 1 Отображать по:
Прямоугольное поле заполнено белыми и черными клетками, требуется определить количество вариантов замощения поля таким образом, чтобы на нем не встречалось ни одного белого или черного квадрата 2 на 2.

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

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

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

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

Входные данные

В первой строке входных данных содержатся два положительных целых числа, разделенных пробелом: $M$ и $N$ (1 <= $M$·$N$ <= 30).

Выходные данные

Выведите единственное число - количество различных симпатичных узоров, которые можно выложить во дворе размера $M$×$N$ . Узоры, получающиеся друг из друга сдвигом, поворотом или отражением, считаются различными.

Примеры
Входные данные
1 2
Выходные данные
4
Входные данные
4 1
Выходные данные
16
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

У Пети имеется неограниченный набор красных, синих и зеленых плиток размером 1×1. Он выбирает ровно N плиток и выкладывает их в полоску. Например, при N = 10 она может выглядеть следующим образом:


К

К

К

С

З

К

К

З

К

С


(Буквой К обозначена красная плитка, С – синяя, З – зеленая)

После этого Петя заполняет следующую таблицу:



красный

синий

зеленый

красный

Y

Y

Y

синий

Y

N

Y

зеленый

Y

Y

N


В клетке на пересечении строки, отвечающей цвету А, и столбца, отвечающего цвету Б, он записывает "Y", если в его полоске найдется место, где рядом лежат плитки цветов А и Б и "N" в противном случае. Считается, что плитки лежат рядом, если у них есть общая сторона. (Очевидно, что таблица симметрична относительно главной диагонали – если плитки цветов А и Б лежали рядом, то рядом лежали и плитки цветов Б и А.) Назовем такую таблицу диаграммой смежности данной полоски.

Так, данная таблица представляет собой диаграмму смежности приведенной выше полоски.

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

(Заметьте, что полоски, являющиеся отражением друг друга, но не совпадающие, считаются разными. Так, полоска


С

К

З

К

К

З

С

К

К

К


не совпадает с полоской, приведенной в начале условия.)

Формат входных данных

Первая строка входного файла содержит число N. (1 N 100). Следующие три строки входного файла, содержащие по три символа из набора {"Y", "N"}, соответствуют трем строкам диаграммы смежности. Других символов, включая пробелы, во входном файле не содержится. Входные данные корректны, т.е. диаграмма смежности симметрична.

Формат выходных данных

Выведите в выходной файл количество полосок длины N, имеющих приведенную во входном файле диаграмму смежности.

Примеры

Входные данные

Выходные данные

10

YYY

YNY

YYN

4596

3

YYY

YYY

YYY

0



Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест