eolymp
bolt
Try our new interface for solving problems
Problems

What prefix?

What prefix?

Time limit 1 second
Memory limit 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-й цифры дробной части. Для того, чтобы исключить неоднозначность толкования подчеркнем, что искомое число подсчитывается для фиксированного набора необходимого количества неповторяющихся букв.

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

Input data

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

Output data

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

Examples

Input example #1
1
Output example #1
1
Author T. Zarkua
Source Winter charges in Kharkov 2010 Day 7