Permutation p is an ordered set of integers p₁,p₂,...,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₁,p₂,...,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₁,a₂,...,a_n and b₁,b₂,...,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⁹+7).