$WA$与$TLE$的结合体

#include <bits/stdc++.h>
using namespace std;
struct node
{
	long long m[11][11];
};
node f,res;
long long n;
void init()
{
	f.m[1][1]=f.m[1][2]=f.m[2][1]=1;
	f.m[2][2]=0;
}
void square(node &x)
{
	for(int i=1;i<=2;i++)
	{
		for(int j=1;j<=2;j++)
		{
			if(i==j)
			x.m[i][j]=1ll;
			else
			x.m[i][j]=0ll;
		}
	}
}
void cf(node &x,node &y,node &z)
{
	memset(z.m,0,sizeof(z.m));
	for(int i=1;i<=2;i++)
	{
		for(int j=1;j<=2;j++)
		{
			if(x.m[i][j])
			{
				for(int k=1;k<=2;k++)
				{
					z.m[i][k]+=x.m[i][j]*y.m[j][k];
					z.m[i][k]%=1000000007;			
				}
			}
		}
	}
}
void quick(int k)
{
	square(res);
	node tmp=f,t;
	while(k)
	{
		if(k&1)
		{
			cf(res,tmp,t);
			res=t;
		}
		cf(tmp,tmp,t);
		tmp=t;
		k>>=1;
	}
}
long long solve()
{
	if(n<=2)
	return 1ll;
	quick(n-2);
	long long res1=res.m[1][1]+res.m[2][1];
	res1%=1000000007;
	return res1;
}
int main()
{
	cin>>n;
	init();
	cout<<solve();
	return 0;
}