eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Скільки префіксних?

Скільки префіксних?

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

Як відомно, ще у 20-ті роки XX ст. польский математик Ян Лукасевич (Jan Lukasiewicz) запропонував бездужкові форми запису алгебраїчних виразів, названі у його честь польскими записами. Префіксний польский запис отримується шляхом вставки знаку операції перед відповідними (відповідним) операндами (операндом). Наприклад, якщо маємо інфіксний вираз (b-c/d)/(e*f-(g+h*k)), то префіксною формою фрагменту "c/d" буде "/cd", префіксною формою фрагменту "b-c/d" буде "-b/cd". Префіксною формою фрагменту "e*f" буде "*ef", фрагменту "h*k" буде "*hk", а фрагменту "g+h*k" - "+g*hk". Тоді виразу "e*f-(g+h*k)" буде відповідати префіксний запис "-*ef+g*hk", і розглядаючи отримані префіксні записи як операнди завершаючі операції - ділення, врешті решт отримаємо: "/-b/cd-*ef+g*hk".

Перед нами поствленор задачу за заданим цілим N (1N50) визначити число, рівне загальній кількості всіх можливих префіксних виразів довжини N, які містять лише двомісні операції '+' '-' '*' '/', а також необхідну кількість неповторюваних перших літер давньогрузинського, або останніх літер сучасного українського алфавітів, або неповторюваних і тих і інших, взяту по модулю 1 000 009, при умові, що всі можливі префіксні вирази, які задовольняють наведеним умовам, впорядковані у порядку отримання більших значень, якщо в якості операндів взято необхідну кількість підряд ідучих цифр дев'яткового подання числа Непера, починаючи з 753-ї цифри дробової частини. Для того, щоб виключити неоднозначність тлумачення підкреслимо, що шукане число підраховується для фіксованого набору необхідної кількості неповторюваних літер.

Примітка. Будемо вважати доведеним тезис про пустоту множини спільних літер сучасного українського і давньогрузинського алфавітів на даний момент.

Вхідні дані

Файл містит один рядок - число N.

Вихідні дані

Файл містить єдине число (зрозуміло ціле :) ) - шуканий результат.

Приклад

Вхідні дані #1
1
Вихідні дані #1
1
Автор Т.Заркуа
Джерело Зимові збори у Харкові 2010 День 7