Задача Spruce. Фермер Иван Петрович купил участок, состоящий из m квадратных грядок з юга на север и из n грядок с запада на восток. Он хочет посадить на участке ели, которые, когда они вырастут, он выгодно продаст под Новый Год. Однако ели можно садить лишь по таким правилам:
- На каждой грядке может расти не более трех елей.
- Нельзя оставлять грядки пустыми.
- На каждом квадрате, образованном четырьмя соседними грядками, должно расти ровно восемь елей.
Помогите фермеру посчитать, сколькими способами он может посадить ели на своем участке.
Технические условия. Программа Spruce читает с устройства стандартного ввода через пробел числа m, n (2<=m,n<=30) и выводит на устройство стандартного вывода искомое количество способов.
Примеры
Ввод 2 2
Вывод 19
Ввод 2 3
Вывод 45