小欧的排列计算
题号：NC262065
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

定义一个排列为“好排列”，当且仅当所有相邻两个数的乘积均为偶数。
小欧想知道，长度 n 的“好排列”一共有多少种？由于答案可能很大，请将答案对 (10^9+7) 取模后输出。

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

输入描述:

一个正整数n。

输出描述:

输出一个整数，代表“好排列”的数量。由于答案可能很大，请将答案对 (10^9+7) 取模后输出。
示例1

输入

复制 
2

输出

复制 
2

说明

好排列有[1,2]和[2,1]。
示例2

输入

复制 
3

输出

复制 
2

说明

好排列有[1,2,3]和[3,2,1]。