Занятие 10

Из-за некоторых политических событий с витрины магазина пришлось убрать товары, привезенные из Ругзии и Лодмавии. Заполнять свободные места пришлось оставшимся товаром, привезенным из Рутции и Тикая. Витрина – это прямоугольный ящик, разбитый вертикальными и горизонтальными перегородками на ячейки, в которые кладется товар. Для того, чтобы ассортимент казался как и раньше разнообразным, при расстановке товара необходимо соблюдать следующее правило: ни в одном ряду и ни в одном столбце не должно быть более двух подряд стоящих товаров из одной страны.

Напишите программу, которая определяет количество различных расстановок товаров в витрине, состоящей из `N` рядов по `M` ячеек в каждом ряду. Две расстановки считаются различными, если есть хотя бы одна ячейка, товар в которой имеет разную страну-производителя.

Вводятся через пробел два целых числа `N` и `M\ (1≤N≤5,\ 1≤M≤100)` – размеры витрины.

Вывести количество различных расстановок.

1 3

6