记录编号	458159	评测结果	AAAAAAAAAA
题目名称	斐波那契平方和	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2017-10-10 14:51:33	内存使用	0.31 MiB

#include<bits/stdc++.h>//听说结构体会漂亮点qwq 
#define ll long long//好像还是很丑啊 
using namespace std;//1,0,0,1这个矩阵乘任何矩阵都等于矩阵本身,相当于自然数1 
const int mod=1e9+7;
ll n,ans=1;
struct square{
	ll a[3][3];
	square(){}
	square(ll x,ll y,ll z,ll o){
		a[1][1]=x;a[1][2]=y;a[2][1]=z;a[2][2]=o;
	}
	square operator * (const square &o)const{
		return square(a[1][1]*o.a[1][1]%mod+a[1][2]*o.a[2][1]%mod,a[1][1]*o.a[1][2]%mod+a[1][2]*o.a[2][2]%mod,a[2][1]*o.a[1][1]%mod+a[2][2]*o.a[2][1]%mod,a[2][1]*o.a[1][2]%mod+a[2][2]*o.a[2][2]%mod);
	}
}a,b;
void fast(ll x){
	while(x){
		if(x&1)b=b*a;a=a*a;x>>=1;
	}ans=ans*b.a[1][1]%mod*(b.a[2][1]+b.a[1][1])%mod;
}
int main()
{
	freopen("fibsqr.in","r",stdin);freopen("fibsqr.out","w",stdout);
	scanf("%lld",&n);
	if(!n){
		cout<<0;return 0;
	}
	a=square(1,1,1,0);b=square(1,0,0,1);
	fast(n-1);cout<<ans;
	return 0;
}