记录编号	282826	评测结果	AAAAAAAAAA
题目名称	斐波那契平方和	最终得分	100
用户昵称	面对疾风吧 疾风 疾风吧	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-07-13 21:24:49	内存使用	0.00 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long LL;
/*LL mul(LL a,LL b){
    LL sum=0;
    while(b){
        if(b&1) sum=(sum+a)%Mod;
        a=(a+a)%Mod;b>>=1;
    }
    return sum;
}*/
LL n,ans,Mod=1000000007;
struct MA{
	LL a[5][5];
	void init(bool flag){
		for(int i=1;i<=4;i++){
			for(int j=1;j<=4;j++){
				a[i][j]=0;
			}
		}
		if(flag){
			for(int i=1;i<=4;i++)a[i][i]=1;
		}
	}
	MA operator *(const MA &b)const{
		MA c;
		for(int i=1;i<=4;i++){
			for(int j=1;j<=4;j++){
				c.a[i][j]=0;
				for(int k=1;k<=4;k++){
					c.a[i][j]+=a[i][k]*b.a[k][j]%Mod;
				}
			}
		}
		return c;
	}
};
MA T,F,A;

void _init();
void _work();
LL _quickpow();
int Main();
int haha=Main();
int main(){;}
int Main(){
	freopen("fibsqr.in","r",stdin);
	freopen("fibsqr.out","w",stdout);
	scanf("%llu",&n);n--;
	_init();
	ans=_quickpow();
	printf("%llu\n",ans);
	return 0;
}
void _init(){
	F.a[1][1]=1;F.a[1][2]=1;F.a[1][3]=1;F.a[1][4]=1;
	F.a[2][1]=1;F.a[2][2]=0;F.a[2][3]=0;F.a[2][4]=0;
	F.a[3][1]=2;F.a[3][2]=0;F.a[3][3]=1;F.a[3][4]=0;
	F.a[4][1]=0;F.a[4][2]=0;F.a[3][4]=0;F.a[4][4]=1;
	A.a[1][1]=1;A.a[1][2]=1;A.a[1][3]=1;A.a[1][4]=1;
}
LL _quickpow(){
	T.init(1);
	for(;n;n>>=1,F=F*F)if(n&1)T=T*F;
	A=A*T;
	return A.a[1][4]%Mod;
}