Задача Spruce.

Фермер Іван Петрович купив ділянку, що складається з m квадратних грядок з півдня на північ і з n грядок із заходу на схід. Він хоче посадити на ділянці ялинки, які, коли вони виростуть, він вигідно реалізує під Новий Рік. Однак ялинки можна садити лише за такими правилами:

  1. На кожній грядці може рости не більше трьох ялин.
  2. Не можна залишати грядки порожніми.
  3. На кожному квадраті, утвореному чотирма сусідніми грядками, має рости рівно вісім ялин.

Допоможіть фермеру порахувати, скількома способами він може посадити ялинки на своїй ділянці.

Технічні умови: Програма Spruce читає з пристрою стандартного введення через пропуск числа m, n (2<=m, n<=30) і виводить на пристрій стандартного виведення шукану кількість способів.

Приклади

Введення 2 2
Виведення 19
Введення 2 3
Виведення 45

© LIKT 1998-2018