排列 p 是整数 p1, p2, ..., pn 的有序集合,由 n 个不同的正整数组成,每个不超过 n。我们将排列 p 的第 i 个元素表示为 pi。我们将数字 n 称为排列 p1、p2、...、pn 的大小或长度。
Petya 决定在长度为 n 的排列集合上引入求和运算。假设我们有两个长度为 n 的排列:a1, a2, ..., an 和 b1, b2, ..., bn。 Petya 将排列 a 和 b 的和称为长度为 n 的排列 c,其中 ci = ((ai - 1 + bi - 1) mod n) + 1 (1 ≤ i ≤ n)。
运算$$x \mod y$$ 表示取数字x 除以数字y 后的余数。
显然,并非所有排列 a 和 b 都存在排列 c,即 a 和 b 之和。这就是为什么 Petya 感到难过并要求你执行以下操作:给定 n,计算长度为 n 的排列 a 和 b 的数量,存在排列 c,它是 a 和 b 的和。排列对 x, y (x ≠ y) 和排列对 y, x 被视为不同对。
由于答案可能相当大,因此打印除以 1000000007 (109 + 7) 后的余数。
输入
单行包含整数 n (1 ≤ n ≤ 16)。
输出
在单行中打印一个非负整数 - 排列 a 和 b 的数量,存在排列 c,它是 a 和 b 的和,模 1000000007 (109 + 7)。
示例
输入 #1
3
输出 #1
18
输入 #2
5
输出 #2
1800