Алфавит для слепых
(Время: 1 сек. Память: 32 Мб Сложность: 27%)
Известно, что для чтения слепые используют алфавит, буквы которого представляют собой различные комбинации выступов, которые распознаются на ощупь. Предположим, что для обозначения буквы используется прямоугольная область размера N×M, где N – высота, а M – ширина таблицы соответственно, причем некоторые из ячеек содержат выступ, а все остальные ячейки пусты.
Так как слепой человек не видит границ таблицы, то он не может различать комбинации, получаемые сдвигом по горизонтали и/или вертикали. Например, он не сможет различить комбинации, представленные на рисунках а) и б). Однако, комбинации а) и в) различимы (их нельзя получить сдвигом):
Заметим, что прямоугольник должен содержать хотя бы один выступ, т.к. его сложно отследить по расстоянию между таблицами. Каждый уникальный вариант может определять какую-либо букву алфавита.
В качестве примера приведем все возможные 10 комбинаций, которые можно составить для таблицы размером 2×2:
По заданным размерам таблицы требуется определить максимальное количество букв, которые возможно закодировать описанным выше способом.
Входные данные
Входной файл INPUT.TXT содержит натуральные числа N и M – размер таблицы (1 ≤ N×M ≤ 60).
Выходные данные
В выходной файл OUTPUT.TXT выведите единственное число – количество различных букв, которые слепой сможет распознать при заданном размере таблицы.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 2 | 10 |
| 2 | 3 3 | 400 |
| 3 | 4 4 | 57856 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
