Алфавит для слепых

Известно, что для чтения слепые используют алфавит, буквы которого представляют собой различные комбинации выступов, которые распознаются на ощупь. Предположим, что для обозначения буквы используется прямоугольная область размера N×M, где N – высота, а M – ширина таблицы соответственно, причем некоторые из ячеек содержат выступ, а все остальные ячейки пусты.

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

Заметим, что прямоугольник должен содержать хотя бы один выступ, т.к. его сложно отследить по расстоянию между таблицами. Каждый уникальный вариант может определять какую-либо букву алфавита.

В качестве примера приведем все возможные 10 комбинаций, которые можно составить для таблицы размером 2×2:

По заданным размерам таблицы требуется определить максимальное количество букв, которые возможно закодировать описанным выше способом.

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

Входной файл INPUT.TXT содержит натуральные числа N и M – размер таблицы (1 ≤ N×M ≤ 60).

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

В выходной файл OUTPUT.TXT выведите единственное число – количество различных букв, которые слепой сможет распознать при заданном размере таблицы.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]