Предательство Юэ

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

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

он состоит из цифр от $$$1$$$ до $$$9$$$;
его длина в точности равна $$$2n$$$;
сумма первых $$$n$$$ цифр отличается от суммы последних $$$n$$$ цифр не более чем на один;
произведение первых $$$n$$$ цифр равно произведению последних $$$n$$$ цифр.

Помогите Юэ узнать, сколько существует кодов длиной $$$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$$$	нет

Примеры

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

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

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

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

Примечание

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

$$$9$$$ кодов из четырех одинаковых цифр
$$$9 \cdot 8 \cdot 2 = 144$$$ кода, в которых первые две цифры различны и совпадают в каком-то порядке с последними двумя;
$$$4$$$ кода, состоящих из цифр $$$1$$$ и $$$4$$$ в одной половине и двух цифр $$$2$$$ в другой;
$$$8$$$ кодов, состоящих из цифр $$$2$$$ и $$$6$$$ в одной половине и цифр $$$3$$$ и $$$4$$$ в другой;
$$$8$$$ кодов, состоящих из цифр $$$3$$$ и $$$8$$$ в одной половине и цифр $$$4$$$ и $$$6$$$ в другой;
$$$4$$$ кода, состоящих из цифр $$$4$$$ и $$$9$$$ в одной половине и двух цифр $$$6$$$ в другой.