Permutation Sum

对于从 $1$ 到 $n$ 的排列 $a$，$b$，定义序列 $c$ 满足 $c_i=(a_i+b_i-2)\bmod{n}+1$，求对于多少对 $(a,b)$ 满足对应的 $c$ 是一个从 $1$ 到 $n$ 的排列。 注意如果 $a\neq b$，$(a,b)$ 与 $(b,a)$ 算作不同的组合。$1\le n\le 16$。

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 $ ).

The single line contains integer $ n\ (1<=n<=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 $ ( $ 10^{9}+7 $ ).

3

18

5

1800