D. Сумма перестановок
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

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

Петя решил ввести операцию суммы на множестве перестановок длины n. Пусть заданы две перестановки длины n: a1, a2, ..., an и b1, b2, ..., bn. Суммой перестановок a и b Петя назвал такую перестановку c длины n, у которой ci = ((ai - 1 + bi - 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 (109 + 7).

Входные данные

В единственной строке находится целое число n (1 ≤ n ≤ 16).

Выходные данные

В единственной строке выведите целое неотрицательное число — количество таких пар перестановок a и b, что существует перестановка c, которая является суммой a и b, по модулю 1000000007 (109 + 7).

Примеры
Входные данные
3
Выходные данные
18
Входные данные
5
Выходные данные
1800