| Ограничение времени | 2 секунды |
| Ограничение памяти | 64Mb |
| Ввод | стандартный ввод или input.txt |
| Вывод | стандартный вывод или output.txt |
Болик добрался до музея, здание которого представляет собой квадрат N × N, разбитый на N2 равных квадратных залов. Вход в музей расположен в левом нижнем зале, а Лёлик ждет Болика в правом верхнем. Из каждого зала можно пройти в соседний с ним зал (два зала называются соседними, если у них есть общая стена).
Теперь Болик хочет определить сколько возможных путей до Лёлика у него есть. Конечно, его интересуют только пути кратчайшей длины.
На вход подается одно натуральное число N (2 N 22).
Выведите единственное натуральное число — количество различных путей наименьшей длины.
| Ввод | Вывод |
|---|---|
3 |
6 |