Предательство Юэ
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Барон Владимир Харконнен похитил жену Веллингтона Юэ (личного доктора герцога Лето Атрейдеса). Чтобы вернуть ее, Юэ должен предать герцога Лето и снять оборону города. Чтобы снять силовой щит, покрывающий город, требуется ввести специальный код.

Юэ знает про код, что:

Помогите Юэ узнать, сколько существует кодов длиной $$$2n$$$, чтобы он мог спасти свою жену.

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

Дано одно целое число $$$n$$$, где $$$2n$$$ — длина кода, снимающего щит ($$$1 \le n \le 42$$$).

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

Вывести количество кодов длины $$$2n$$$.

Система оценки

В этой задаче 42 теста. Все тесты оцениваются независимо.

ТестыБаллыДоп. ограничения
1, 2примеры из условия
3 – 12$$$10 \times 4$$$$$$n \le 12$$$
13 – 42$$$30 \times 2$$$нет

Примеры

Входные данные
1
Выходные данные
9
Входные данные
2
Выходные данные
177

Примечание

Во втором примере из условия подходят