评测记录

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

#define ll long long
#define int long long
ll n;
const int mod=1e7+7;

inline ll read(){
	ll ret=0,f=1;
	char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-f;
	for(;c>='0'&&c<='9';c=getchar()) ret=ret*10+c-'0';
	return ret*f;
}

struct mat{
	int a[3][3];
	mat(){
		memset(a,0,sizeof(a));
	}
	mat operator*(const mat &b) const {
		mat res;
		for(int i=1;i<=2;i++){
			for(int j=1;j<=2;j++){
				for(int k=1;k<=2;k++){
					res.a[i][j]=(res.a[i][j]+a[i][k]*b.a[k][j])%mod;
				}
			}
		}
		
		return res;
	}
}ans,base;

void init(){
	base.a[1][1]=base.a[1][2]=base.a[2][1]=1;
	ans.a[1][1]=ans.a[1][2]=1;
}

void qpow(int b){
	while(b){
		if(b&1){
			ans=ans*base;
		}
		base=base*base;
		b>>=1;
	}
}

signed main(void){
	
	n=read();
	
	if(n<=2){
		puts("1");
		return 0;
	}
	
	init();
	qpow(n-2);
	cout<<ans.a[1][1]%mod<<endl;
	
	return 0;
}