记录编号	142393	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]整数的lqp拆分	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.128 s
提交时间	2014-12-08 17:00:54	内存使用	7.94 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const LL MOD=1000000000+7;
const int SIZEN=1000010;
LL G[SIZEN];
int main(){
	freopen("partition.in","r",stdin);
	freopen("partition.out","w",stdout);
	LL N;
	cin>>N;
	G[0]=0;G[1]=1;
	for(int i=2;i<=N;i++) G[i]=(2*G[i-1]+G[i-2])%MOD;
	cout<<G[N]<<endl;
	return 0;
}