Перестановкой p называется упорядоченный набор чисел p₁,  p₂,  ...,  p_n, состоящий из n различных целых положительных чисел, каждое из которых не больше чем n. Обозначим i-ый элемент перестановки p через p_i. Число n будем называть размером или длиной перестановки p₁,  p₂,  ...,  p_n.

Петя решил ввести операцию суммы на множестве перестановок длины n. Пусть заданы две перестановки длины n: a₁, a₂, ..., a_n и b₁, b₂, ..., b_n. Суммой перестановок a и b Петя назвал такую перестановку c длины n, у которой c_i = ((a_i - 1 + b_i - 1) mod n) + 1 (1 ≤ i ≤ n).

Операция обозначает взятие остатка от деления числа x на число y.

Очевидно, что не для всех перестановок a и b будет существовать перестановка c, являющаяся их суммой. Из-за этого Петя расстроился и попросил Вас для заданного n посчитать количество таких пар перестановок a и b длины n, что существует перестановка c, являющаяся суммой a и b. Пара перестановок x, y (x ≠ y) и пара перестановок y, x считаются различными парами.

Так как ответ может получиться достаточно большим, выведите его остаток от деления на 1000000007 (10⁹ + 7).