Как известно, еще в \textbf{20}-е годы \textbf{XX} ст. польский математик Ян Лукасевич (\textit{Jan Lukasiewicz}) предложил бесскобочные формы записи алгебраических выражений, называемые в его честь польскими записями. Префиксная польская запись получается путем вставления знака операции перед соответствующими (соответствующим) операндами (операндом). Например, если имеем инфиксное выражение \textbf{(b-c/d)/(e*f-(g+h*k))}, то префиксной формой фрагмента "\textbf{c/d}" будет "\textbf{/cd}", префиксной формой фрагмента "\textbf{b-c/d}" будет "\textbf{-b/cd}". Префиксной формой фрагмента "\textbf{e*f}" будет "\textbf{*ef}", фрагмента "\textbf{h*k}" будет "\textbf{*hk}", а фрагмента "\textbf{g+h*k}" - "\textbf{+g*hk}". Тогда выражению "\textbf{e*f-(g+h*k)}" будет соответствовать префиксная запись "\textbf{-*ef+g*hk}", и рассматривая полученные префиксные записи как операнды заключительные операции - деления, окончательно получим: "\textbf{/-b/cd-*ef+g*hk}". Перед нами стоит задача по заданному целому \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{50}) определить число, равное общему количеству всевозможных префиксных выражений длины \textbf{N}, содержащему только двуместные операции '\textbf{+}' '\textbf{-}' '\textbf{*}' '\textbf{/}', а также необходимое количество неповторяющихся первых букв древнегрузинского, либо последних букв современного украинского алфавитов, либо неповторяющихся и тех и других, взятое по модулю \textbf{1 000 009}, при условии, что всевозможные префиксные выражения, удовлетворяющие приведенным условиям, упорядочены в порядке получения больших значений, если в качестве операндов взято необходимое количество подряд идущих цифр девятиричного представления числа Непера, начиная с \textbf{753}-й цифры дробной части. Для того, чтобы исключить неоднозначность толкования подчеркнем, что искомое число подсчитывается для фиксированного набора необходимого количества неповторяющихся букв. \textbf{Примечание.} Будем считать доказаным тезис о пустоте множества общих букв современного украинского и древнегрузинского алфавитов на данный момент. \InputFile Файл содержит одну строку - число \textbf{N}. \OutputFile Файл содержит единственное число (разумеется целое :) ) - искомый результат.