Problems
Сколько префиксных?
Сколько префиксных?
Как известно, идея записывать алгебраические выражения в бесскобочной форме принадлежит польскому математику Лукасевичу. Именно в его честь бесскобочные формы записи алгебраических выражений принять называть польскими. В прямой польской (префиксной) записи операция записывается перед операндами, а в т.н. обратной (постфиксной) -- наоборот, знак операции записывается после операндов. Например, для выражения \textbf{b*(c-d/f)} прямая польская запись имеет вид \textbf{*b-c/df}, а обратная польская запись выглядит так \textbf{bcdf/-*}.
Для заданного положительного \textbf{N} определить количество всемозможных прямых польских записей длины \textbf{N} при условии, что в качестве операций могут быть использованы только бинарные арифметические операции ( \textbf{-, +, *, /}), а в качестве операндов только символы \textbf{b, c, d, e, f}. Ответ выдать по модулю \textbf{1000000007}.
\InputFile
Число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{52}).
\OutputFile
Единственная строка - ответ задачи\textbf{.}
Input example #1
1
Output example #1
5