Задача №112660. Задача С. Квадратные залы.
Здание Национальной Британской галереи представляет собой квадрат NxN, разбитый на N^2 равных квадратных залов. Вход в галерею находится в левом нижнем зале, а Холмс ждёт доктора Ватсона в самом дальнем, т.е. в правом верхнем зале. Из каждого зала можно пройти в соседний с ним зал (два зала называются соседними, если у них есть общая стена).
«Сколько же у меня есть возможных путей!», - воскликнул Ватсон, посмотрев на план галереи. А действительно, сколько? Конечно же, так как Ватсон спешит, нас интересует количество путей наименьшей длины.
Входные данные
Одно натуральное число 2 ≤ N ≤ 15.
Выходные данные
Одно натуральное число — количество различных путей наименьшей длины.
Примеры
Входные данные
3
Выходные данные
6
Сдать: для сдачи задач необходимо войти в систему