Кількість дерев
Наш супергерой Керрі Аддер розгадав секретний метод, за допомогою якого злий Головний Краш генерує код доступу до своєї фортеці в Окленді. Цей код завжди є числом різних бінарних дерев пошуку з певною кількістю вузлів, що мають особливу властивість. Щоб код був коротким, він використовує лише дев'ять найменш значущих цифр.
Властивість полягає в тому, що для кожного вузла висота правого піддерева цього вузла відрізняється від висоти лівого піддерева не більше ніж на одиницю. Висота піддерева визначається як довжина найдовшого шляху від кореня цього піддерева до будь-якого листка. Піддерево з одним вузлом має висоту 0, а піддерево, яке не містить вузлів, вважається таким, що має висоту −1.
Вхідні дані
Вхідні дані подаються у такому форматі. Кожен тестовий випадок розміщується на окремому рядку. Кожен рядок містить лише одне ціле число N, яке вказує кількість вузлів. Значення N знаходиться в межах від 1 до 1427 включно.
Вихідні дані
Ваш вихід повинен містити один рядок для кожного тестового випадку, що складається лише з дев'ятизначного коду (зверніть увагу, що необхідно виводити провідні нулі).