How many prefixes?

The concept of writing algebraic expressions without brackets was introduced by the Polish mathematician Lukasiewicz. In his honor, these bracket-free expressions are known as Polish notation. In prefix Polish notation, the operator precedes the operands, while in postfix (reverse Polish) notation, the operator follows the operands. For instance, the expression (b*(c-d/f)) is represented in prefix Polish notation as (*b-c/df), and in postfix Polish notation as (bcdf/-*).

Given a positive integer (N), your task is to determine the total number of possible prefix Polish notations of length (N), using only binary arithmetic operations (-, +, *, /) and the operands (b, c, d, e, f). Provide the result modulo (1000000007).

Input

The input consists of a single integer (N) ((1 $\le$ N $\le$ 52)).

Output

Output a single line containing the answer to the problem.

Examples