题目描述

求将一个集合$U=${$1,2,3,\dots,n$}划分成两个集合$T$和$P$,使得$|T|\notin T, |P|\notin P$的方案数。

由于答案可能会很大,你只需要输出答案对$10^9+7$取模的结果即可。


输入格式

一行一个整数 n。


输出格式

一行,一个整数,表示答案对$10^9+7$取模的结果。


样例数据

输入

6

输出

10

备注

$1\leq n \leq 10^5$


操作

评测记录

优秀代码

信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

题解