eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 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-й цифры дробной части. Для того, чтобы исключить неоднозначность толкования подчеркнем, что искомое число подсчитывается для фиксированного набора необходимого количества неповторяющихся букв.

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

Giriş verilənləri

Файл содержит одну строку - число N.

Çıxış verilənləri

Файл содержит единственное число (разумеется целое :) ) - искомый результат.

Nümunə

Giriş verilənləri #1
1
Çıxış verilənləri #1
1
Müəllif Т.Заркуа
Mənbə Зимние сборы в Харькове 2010 День 7