80pts #2#10wa

#include<cstdio>
#define ll_ long long
#define mod_ 1000000007
struct matrix{
	ll_ f[3][3];
	int x,y;
	matrix(int a,int b){
		int i,j;
		x = a;
		y = b;
		for(i = 0;i <= x;++ i)
			for(j = 0;j <= y;++ j)
				f[i][j] = 0;
		return;
	}
};
matrix identity_matrix(int size){
	matrix a(size,size);
	int i;
	for(i = 1;i <= size;++ i)
		a.f[i][i] = 1;
	return a;
}
matrix operator*(const matrix& a,const matrix& b){
	matrix ret(a.y,b.x);
	int i,j,k;
	for(i = 1;i <= a.y;++ i)
		for(j = 1;j <= b.x;++ j)
			for(k = 1;k <= a.x;++ k)
				ret.f[i][j] = (ret.f[i][j] + a.f[k][i]*b.f[j][k]%mod_) % mod_;
	return ret;
}
matrix qpow(matrix a,int n){
	matrix ret = identity_matrix(a.x);
	matrix base = a;
	while(n > 0){
		if(n & 1)
			ret = ret * base;
		base = base * base;
		n >>= 1;
	}
	return ret;
}
void solve(void){
	int n;
	matrix fibo(2,1),m(2,2);
	fibo.f[1][1] = 1;fibo.f[2][1] = 1;
	m.f[1][1] = 1;m.f[2][1] = 1;m.f[1][2] = 1;
	scanf("%d",&n);
	m = qpow(m,n-2);
	fibo = fibo * m;
	printf("%lld",fibo.f[1][1]);
	return;
}
int main(void){
	solve();
	return 0;
}}