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