K. Раскраска матрицы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим матрицу из $$$n$$$ строк и $$$m$$$ столбцов. Изначально все клетки матрицы белые. Обозначим за $$$(i,j)$$$ клетку на пересечении $$$i$$$-й строки и $$$j$$$-го столбца.

Мы можем проводить над ней следующую операцию любое количество раз (возможно, ноль):

  • выбрать клетку $$$(x, y)$$$ и цвет $$$c$$$ (белый, синий или красный); покрасить всю строку $$$i$$$ и весь столбец $$$j$$$ в цвет $$$c$$$. Если какие-то клетки в этой строке или в этом столбце уже были покрашены — они перекрашиваются.

Назовем пару целых чисел $$$(r, b)$$$ достижимой, если путем таких операций можно получить матрицу, в которой ровно $$$r$$$ красных и $$$b$$$ синих клеток.

Ваша задача — посчитать количество достижимых пар.

Входные данные

В единственной строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n, m \le 16$$$).

Выходные данные

Выведите одно целое число — количество достижимых пар.

Примеры
Входные данные
2 2
Выходные данные
9
Входные данные
3 3
Выходные данные
45
Входные данные
16 15
Выходные данные
29161
Входные данные
4 2
Выходные данные
30
Примечание

В первом примере из условия достижимыми являются следующие пары: $$$(0, 0)$$$, $$$(0, 1)$$$, $$$(0, 3)$$$, $$$(0, 4)$$$, $$$(1, 0)$$$, $$$(1, 3)$$$, $$$(3, 0)$$$, $$$(3, 1)$$$, $$$(4, 0)$$$.

Чтобы получить, например, пару $$$(3, 1)$$$, можно сделать следующие действия:

  • провести операцию на клетке $$$(1, 1)$$$ с красным цветом;
  • провести операцию на клетке $$$(2, 2)$$$ с синим цветом;
  • провести операцию на клетке $$$(1, 2)$$$ с красным цветом.

Тогда клетка $$$(2, 1)$$$ будет синей, а остальные три — красными.