C-小红的双生排列_牛客周赛 Round 75

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小红定义一个排列是双生排列，当且仅当任意相邻两项之和均为奇数。
$\hspace{15pt}$ 现在小红想知道，长度为 $n$ 的双生排列共有多少种？由于答案可能过大，请对 $10^9+7$ 取模。

$\hspace{15pt}$ 长度为 $n$ 的排列是由 $1 \sim n$ 这 $n$ 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如， $\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述:

输入一个整数  代表排列的长度。

输出描述:

输出一个整数，代表长度为  的双生排列数量对  取模的答案。

示例1

输入

复制

输出

复制

说明

在这个样例中，长度为  的排列有：
  且为双生排列；
 ；
 ；
 ；
 ；
  且为双生排列。