← 返回题目列表

Codeforces · 285/D

D. 排列和

中文机器翻译题面 查看原题

排列 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