CF285D Permutation Sum

排列 $p$ 是一组有序的整数 $p_{1},p_{2},...,p_{n}$，包含 $n$ 个互不相同的正整数，并且每个整数都不超过 $n$。我们用 $p_{i}$ 表示排列 $p$ 的第 $i$ 个元素。我们称排列 $p_{1},p_{2},...,p_{n}$ 的长度为 $n$。 Petya 决定在长度为 $n$ 的排列集合上定义一种“和”操作。假设有两个长度为 $n$ 的排列：$a_{1},a_{2},...,a_{n}$ 和 $b_{1},b_{2},...,b_{n}$。Petya 定义这两个排列的“和”为长度为 $n$ 的排列 $c$，其中 $c_{i}=((a_{i}-1+b_{i}-1)\mod n)+1$，$(1\leq i\leq n)$。 操作 $\mod$ 表示 $x$ 除以 $y$ 后的余数。 显然，并不是所有排列 $a$ 和 $b$ 都能使得存在排列 $c$ 满足上面的和定义。因此，Petya 感到很沮丧，并请你做如下事情：给定 $n$，求有多少对长度为 $n$ 的排列 $a$ 和 $b$，满足存在排列 $c$，使得 $c$ 是 $a$ 和 $b$ 的“和”。 对于两个排列 $x$ 和 $y$，$(x\neq y)$，排列对 $(x,y)$ 和 $(y,x)$ 被认为是不同的对。 由于答案可能很大，请输出答案对 $1000000007$（$10^{9}+7$）取模后的结果。

一行一个整数 $n\ (1\leq n\leq 16)$。

输出一个非负整数，表示满足条件的排列对 $(a,b)$ 的个数，对 $1000000007$ 取模。

由 ChatGPT 5 翻译