WA on 10,TLE on 9,11

直接从广义斐波那契改的，不知道错哪

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,out;
const int Mod=1e9+7;
struct T{
	LL m[4][4];
}ans,base;
inline void init(){
	ans.m[1][1]=1,ans.m[1][2]=1;
	base.m[1][1]=1,base.m[2][1]=1,base.m[1][2]=1;
}
inline T mul(T &a,T &b){
	T res;
	memset(res.m,0,sizeof(res.m));
	for(int i=1;i<=2;i++){
		for(int j=1;j<=2;j++){
			for(int k=1;k<=2;k++){
				res.m[i][j]=(res.m[i][j]+a.m[i][k]*b.m[k][j])%Mod;
			}
		}
	}
	return res;
}
inline void qpow(int p){
	while(p){
		if(p&1)ans=mul(ans,base);
		base=mul(base,base);
		p>>=1;
	}
}
int main(){
	cin>>n;
	if(n==1){
		cout<<1;
		return 0;
	}
	else if(n==2){
		cout<<1;
		return 0;
	}
	init();
	qpow(n-2);
    out=ans.m[1][1];
	out%=Mod;
	cout<<out;
	return 0;
}