Болик добрался до музея, здание которого представляет собой квадрат N × N, разбитый на N2 равных квадратных залов. Вход в музей расположен в левом нижнем зале, а Лёлик ждет Болика в правом верхнем. Из каждого зала можно пройти в соседний с ним зал (два зала называются соседними, если у них есть общая стена).
Теперь Болик хочет определить сколько возможных путей до Лёлика у него есть. Конечно, его интересуют только пути кратчайшей длины.
Формат ввода
На вход подается одно натуральное число N (2 ≤ N ≤ 22).
Формат вывода
Выведите единственное натуральное число — количество различных путей наименьшей длины.
Пример