|Codeforces Round #175 (Div. 2)|
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).
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 (109 + 7).