rt

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int m=1000000007;
struct matrix
{
	int z[3][3];//z[i][j]矩阵第i行第j列的数 
	matrix()
	{
		memset(z,0,sizeof(z));
	}
}ans,base;
matrix operator*(const matrix &m1,const matrix &m2)
{
	matrix m3;
	for(int i=1;i<=2;++i)
		for (int j=1;j<=2;++j) 
			for (int k=1;k<=2;++k)
				m3.z[i][j] = (m3.z[i][j]+m1.z[i][k] * m2.z[k][j])%m;
	return m3;
}
void init(){ 
    base.z[1][1] = base.z[1][2] = base.z[2][1] = 1;
    ans.z[1][1] = ans.z[1][2] = 1;
}
void qsm(int b){ 
    while(b){
        if (b & 1) ans = ans * base;
        base = base * base;
        b>>=1;
    }
}
int main(){
	int n;
	cin>>n;
	if (n<=2){
		cout<<"1";
		return 0;
	} 
	init();
	qsm(n-2);
	cout<<(ans.z[1][1] % m);
	return 0; 
}

40分 其它wa