牛牛即将要参加考试，他学会了填答题卡。

可惜他竖着的答题卡填成了横着的 : (
 

好奇的他想知道对于 n 道题，每道题 n 个选项的答题卡 ( n * n 的矩阵 )，满足横答题卡和竖答题卡图形一致的方案数有多少种。

 

注：每道题只能选择一个选项，即 n * n 的矩阵中只能涂黑 n 个空。求横竖对称的方案数。

 

输入描述:

第一行给出 n。

输出描述:

输出方案数，答案对 10^9+7109+7 取模

示例1

输入

复制

3

输出

复制

4

说明

  
备注:
  
对于 50\;\%50% 的数据有 n \leq 10n≤10

对于 100\;\%100% 的数据有 n\le 10^5n≤105
  
代码
  
#include <bits/stdc++.h>
using namespace std;
long long n,m,s,k,t,l,ans,mod=1e9+7; 
long long a[1000001],b[1000001];
map<long long,long long>p;
int main() 
{
	cin>>n;
	a[1]=1;
	b[1]=1;
	a[2]=2;
	b[2]=0;
	for(int i=3;i<=n;i++)
	{
		a[i]=a[i-1]+(i-1)*a[i-2];
		a[i]%=mod;
	}
	cout<<a[n]%mod;
}