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 $x \text{mod} y$ 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).


-----Examples-----
Input
3

Output
18

Input
5

Output
1800

Difficulty: interview

Starter code:

Solutions:
n = int(input())
ans = [1, 3, 5, 7, 9, 11, 13, 15]
dct = \
{
    1 : 1,
    3 : 18,
    5 : 1800,
    7 : 670320,
    9 : 734832000,
    11 : 890786230,
    13 : 695720788,
    15 : 150347555
}
if n in ans:
    print(dct[n])
else:
    print(0)

import math
ans = [1, 3, 15, 133, 2025, 37851, 1030367, 36362925]
n = int(input())

if (n % 2 == 1):
	print(ans[n // 2] * math.factorial(n) % 1000000007)
else:
	print(0)