记录编号	282595	评测结果	AAAAAAAAAA
题目名称	斐波那契平方和	最终得分	100
用户昵称	槿柒	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-07-13 17:46:50	内存使用	0.00 MiB

#include<cstdio>
#define LL unsigned long long
#define mod 1000000007
using namespace std;
LL n;
struct MA{
	LL a[4][4];
	
	void init(LL t){
		for(int i=0;i<4;i++)
			for(int j=0;j<4;j++)a[i][j]=0;
		for(int i=0;i<4;i++)a[i][i]=t;
	}
	
	MA operator * (const MA & b)const{
		MA c={0};
		for(int i=0;i<4;i++){
			for(int j=0;j<4;j++){
				for(int k=0;k<4;k++)
					c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j]%mod)%mod;
			}
		}
		return c;
	}
}A,B,ans;

void QuickPow(MA x,LL n){
	ans.init(1);
	for(;n;n>>=1,x=x*x)if(n&1)ans=ans*x;
}

int L(){
	freopen("fibsqr.in","r",stdin);
    freopen("fibsqr.out","w",stdout);
	scanf("%llu",&n);
	A.a[0][0]=1;A.a[0][1]=1;A.a[0][2]=1;A.a[0][3]=0;
	
	B.a[0][0]=1;B.a[0][1]=1;B.a[0][2]=1;B.a[0][3]=0;
	B.a[1][0]=1;B.a[1][1]=0;B.a[1][2]=0;B.a[1][3]=1;
	B.a[2][0]=2;B.a[2][1]=0;B.a[2][2]=1;B.a[2][3]=0;
	B.a[3][0]=0;B.a[3][1]=0;B.a[3][2]=0;B.a[3][3]=1;

	QuickPow(B,n);
	ans=A*ans;
	ans.a[0][3]=ans.a[0][3]%mod;
	printf("%llu",ans.a[0][3]);
	return 0;
}
int ll=L();
int main(){;}