云卷疏帘观月

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

题目描述

$\hspace{15pt}$ 给定一个整数 $n$ ，设长度为 $n$ 的优美序列为 $p_1,p_2,\dots,p_n \left(0\leq p_i<n\right)$ ，且对于任意的 $i,j\left(i\neq j\right)$ 均有 $p_i\neq p_j$ 。记该序列的权值为：
$f\left(\{p_1,p_2,\dots,p_n\}\right)=\displaystyle \sum _{i=1}^{n}\sum _{j=i}^{n} \operatorname{mex}\left(\{p_i,p_{i+1},\dots,p_{j}\}\right)$

$\hspace{15pt}$ 求长度为 $n$ 且权值达到最大的优美序列个数。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

【名词解释】
$\hspace{15pt}$ mex：整数数组的 $\operatorname{mex}$ 定义为没有出现在数组中的最小非负整数。例如， $\operatorname{mex}(\{1,2,3\}) =0$ 、 $\operatorname{mex}(\{0,2,5\}) =1$ 。

输入描述:

在一行上输入一个整数 ，表示优美序列的长度。

输出描述:

输出一个整数，表示长度为  且权值达到最大的优美序列个数对  取模后的结果。

示例1

输入

复制

输出

复制

说明

在这个样例中，长度为  的优美序列有两种：
，权值为 ；
，权值为 。
因此，长度为  的优美序列的权值达到最大的优美序列个数为 。

示例2

输入

复制

输出

复制