Задача №111528. Шоколад
В целях увеличения продаж фирма "Новый русский шоколад" приняла решение разбивать каждую плитку на дольки в форме прямоугольников 1 × 2 и уголков (квадрат 2 × 2 с вырезанной угловой клеткой), а не на скучные квадратики 1 × 1. При этом долек другой формы на плитке шоколада быть не должно. Через некоторое время узор на плитке будет меняться на другой (но по-прежнему состоящий только из прямоугольников 1 × 2 и уголков), через некоторое время – еще на другой и так далее. Директору фирмы "Новый русский шоколад" захотелось узнать, а сколько всего существует способов разбить плитку шоколада на такие дольки? Помогите ему найти ответ.
В одной строке вводятся два натуральных числа n и m – ширина и длина плитки (1 ≤ n, m ≤ 9).
Выведите одно целое число – количество способов разбить плитку шоколада размером n × m на прямоугольники 1 × 2 и уголки (и прямоугольник и уголок можно поворачивать, долек другой формы на плитке быть не должно).
2 3
5
3 3
8