CF285D.Permutation Sum

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 (109 + 7).

排列 $p$ 是一个由 $n$ 个互不相同的正整数构成的有序集合 $p_1,\,p_2,\,\dots,\,p_n$，其中每个数均不超过 $n$。我们将排列 $p$ 的第 $i$ 个元素记作 $p_i$。我们称 $n$ 为排列 $p_1,\,p_2,\,\dots,\,p_n$ 的大小（或长度）。

佩佳决定在长度为 $n$ 的排列集合上定义一种“求和”运算。假设我们给定两个长度为 $n$ 的排列：$a_1,\,a_2,\,\dots,\,a_n$ 和 $b_1,\,b_2,\,\dots,\,b_n$。佩佳将排列 $a$ 与 $b$ 的和定义为一个长度为 $n$ 的排列 $c$，其中对每个 $1 \le i \le n$，有

$$c_i = ((a_i - 1 + b_i - 1) \bmod n) + 1.$$

符号 表示 $x$ 除以 $y$ 所得的余数。

显然，并非对任意两个排列 $a$ 和 $b$，都存在一个排列 $c$ 恰好是 $a$ 与 $b$ 的和。因此佩佳感到难过，并请你完成如下任务：给定 $n$，计算满足“存在某个排列 $c$ 是 $a$ 与 $b$ 的和”的、长度为 $n$ 的排列对 $(a, b)$ 的个数。注意：若 $x \ne y$，则排列对 $(x, y)$ 与 $(y, x)$ 被视为不同的对。

由于答案可能非常大，请输出其对 $1000000007$（即 $10^9 + 7$）取模的结果。

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

单行包含一个整数 $n$（$1 \leq n \leq 16$）。

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 (109 + 7).

在单行中输出一个非负整数——满足存在排列 $c$ 使得 $c$ 是排列 $a$ 与 $b$ 的和的排列对 $(a, b)$ 的个数，结果对 $1000000007$（即 $10^9 + 7$）取模。