记录编号	282812	评测结果	AAAAAAAAAA
题目名称	斐波那契平方和	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2016-07-13 21:20:16	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long LL;
LL n,ans,Mod=1000000007;
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;
}
struct MA{
	int 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]+=mul(a[i][k],b.a[k][j]),c.a[i][j]%=Mod;
				}
			}
		}
		return c;
	}
};
MA T,F,A;

void _init();
void _work();
LL _quickpow();
int main(){
	freopen("fibsqr.in","r",stdin);freopen("fibsqr.out","w",stdout);
	scanf("%llu",&n);n--;
	_init();
	ans=_quickpow();
	printf("%llu\n",ans);
	//while(1);
	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;
}