Permutation $*p*$ is an ordered set of integers $*p*_{1},  *p*_{2},  ...,  *p*_{*n*}$, consisting of $*n*$ distinct positive integers, each of them doesn't exceed $*n*$. We'll denote the $*i*$-th element of permutation $*p*$ as $*p*_{*i*}$. We'll call number $*n*$ the size or the length of permutation $*p*_{1},  *p*_{2},  ...,  *p*_{*n*}$.

Petya decided to introduce the sum operation on the set of permutations of length $*n*$. Let's assume that we are given two permutations of length $*n*$: $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ and $*b*_{1}, *b*_{2}, ..., *b*_{*n*}$. Petya calls the sum of permutations $*a*$ and $*b*$ such permutation $*c*$ of length $*n*$, where $*c*_{*i*} = ((*a*_{*i*} - 1 + *b*_{*i*} - 1) *mod* *n*) + 1$ $(1 ≤ *i* ≤ *n*)$.

Operation means taking the remainder after dividing number $*x*$ by number $*y*$.

Obviously, not for all permutations $*a*$ and $*b*$ exists permutation $*c*$ that is sum of $*a*$ and $*b*$. That's why Petya got sad and asked you to do the following: given $*n*$, count the number of such pairs of permutations $*a*$ and $*b*$ of length $*n*$, that exists permutation $*c*$ that is sum of $*a*$ and $*b*$. The pair of permutations $*x*, *y*$ $(*x* ≠ *y*)$ and the pair of permutations $*y*, *x*$ are considered distinct pairs.

As the answer can be rather large, print the remainder after dividing it by $1000000007$ ($10^{9} + 7$).

Input

The single line contains integer $*n* (1 ≤ *n* ≤ 16)$.

Output

In the single line print a single non-negative integer — the number of such pairs of permutations $*a*$ and $*b*$, that exists permutation $*c*$ that is sum of $*a*$ and $*b*$, modulo $1000000007$ ($10^{9} + 7$).