记录编号	483229	评测结果	AAAAAAAAAA
题目名称	斐波那契平方和	最终得分	100
用户昵称	烟雨	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2018-01-15 19:54:14	内存使用	0.00 MiB

#include<cstdio>
#include<iostream>
#define mod 1000000007
using namespace std;
long long n,f,ff,o,oo;
struct node 
{
	long long s[2][2];
}c,ans;
node operator *(node x,node y)
{
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<2;j++)c.s[i][j]=0;
	}
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<2;j++)
		{
			for(int k=0;k<2;k++)
			{
				c.s[i][j]+=(x.s[i][k]*y.s[k][j])%mod;
				c.s[i][j]%=mod;
			}
		//	cout<<c.s[i][j]<<' ';
		}
		//cout<<endl;
	}
//	cout<<endl;
	return c;
}
int LL()
{
	freopen ("fibsqr.in","r",stdin);
	freopen ("fibsqr.out","w",stdout);
	cin>>n;
	f=1;ff=1;
	ans.s[0][1]=1;
	ans.s[1][0]=1;
	ans.s[1][1]=1;
	n--;
	while(n)
	{
		if(n&1)
		{
			o=(f*ans.s[0][0]+ff*ans.s[0][1])%mod;
			oo=(f*ans.s[1][0]+ff*ans.s[1][1])%mod;
			f=o;ff=oo;
			//cout<<f<<'*'<<ff<<endl;
		}
		ans=ans*ans;
		n>>=1;
	}//cout<<f<<'*'<<ff<<endl;
	cout<<f*ff%mod;
	return 0;
}
int work=LL();
int main(){;}