Statement is not available in English language
Барон Владимир Харконнен похитил жену Веллингтона Юэ (личного доктора герцога Лето Атрейдеса). Чтобы вернуть ее, Юэ должен предать герцога Лето и снять оборону города. Чтобы снять силовой щит, покрывающий город, требуется ввести специальный код.
Юэ знает про код, что:
- он состоит из цифр от $$$1$$$ до $$$9$$$;
- его длина в точности равна $$$2n$$$;
- сумма первых $$$n$$$ цифр отличается от суммы последних $$$n$$$ цифр не более чем на один;
- произведение первых $$$n$$$ цифр равно произведению последних $$$n$$$ цифр.
Помогите Юэ узнать, сколько существует кодов длиной $$$2n$$$, чтобы он мог спасти свою жену.
Выходные данные
Вывести количество кодов длины $$$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$$$ в другой.
