学步园

推公式

#include<cstdio>
#define mod 1000000007
int n;
long long ans[1000001];
int main(){
	scanf("%d",&n);n++;
	ans[1]=0;ans[2]=1;
	for(int i=3;i<=n;i++)
		ans[i]=(ans[i-1]*2+ans[i-2])%mod;
	printf("%lld",ans[n]);
	return 0;
}