Количество деревьев
Наш супергерой Керрі Аддер раскрыл секретный метод, который злодей Хед Краш использует для генерации кода доступа к своей крепости в Окленде. Код всегда представляет собой число различных бинарных деревьев поиска с определённым количеством узлов, обладающих специфическим свойством. Чтобы код был коротким, он использует только девять наименее значимых цифр.
Свойство заключается в том, что для каждого узла высота правого поддерева этого узла отличается не более чем на единицу от высоты левого поддерева этого узла. Здесь высота поддерева — это длина самого длинного пути от корня этого поддерева до любого листа этого поддерева. Поддерево с одним узлом имеет высоту 0, а по соглашению поддерево, не содержащее узлов, считается имеющим высоту −1.
Входные данные
Входные данные будут отформатированы следующим образом. Каждый тестовый случай будет на отдельной строке. Каждая строка будет содержать только одно целое число, N, количество узлов. Значение N будет от 1 до 1427 включительно.
Выходные данные
Ваш вывод должен содержать одну строку для каждого тестового случая, содержащую только девятизначный код (обратите внимание, что вы должны выводить ведущие нули).