Задача №112660. Задача С. Квадратные залы.

Здание Национальной Британской галереи представляет собой квадрат NxN, разбитый на N^2 равных квадратных залов. Вход в галерею находится в левом нижнем зале, а Холмс ждёт доктора Ватсона в самом дальнем, т.е. в правом верхнем зале. Из каждого зала можно пройти в соседний с ним зал (два зала называются соседними, если у них есть общая стена).

«Сколько же у меня есть возможных путей!», - воскликнул Ватсон, посмотрев на план галереи. А действительно, сколько? Конечно же, так как Ватсон спешит, нас интересует количество путей наименьшей длины.

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

Одно натуральное число 2 ≤ N ≤ 15.

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

Одно натуральное число — количество различных путей наименьшей длины.

Примеры
Входные данные
3
Выходные данные
6
Сдать: для сдачи задач необходимо войти в систему