2WA 10TLE

#include<bits/stdc++.h>
#define LL long long
#define RE register
using namespace std;
const LL mod=1000000007; 
LL n;
LL f[3]={0,1,1},a[3][3],ans[3][3],s[3][3];
int main(){
	cin>>n;
	if(n==1){
		cout<<1;
		return 0;
	}
	a[1][1]=a[2][1]=a[1][2]=1;
	ans[1][1]=ans[2][2]=1;
	int k=n-2;
	for(;k;k>>=1){
		if(k&1){
			for(RE int i=1;i<=2;i++){
				for(RE int j=1;j<=2;j++){
					for(RE int k=1;k<=2;k++){
						s[i][j]=(s[i][j]+ans[i][k]*a[k][j])%mod;
					}
				}
			}
			for(RE int i=1;i<=2;i++){
				for(RE int j=1;j<=2;j++){
					ans[i][j]=s[i][j];
					s[i][j]=0;
				}
			}
		}
		for(RE int i=1;i<=2;i++){
			for(RE int j=1;j<=2;j++){
				for(RE int k=1;k<=2;k++){
					s[i][j]=(s[i][j]+a[i][k]*a[k][j])%mod;
				}
			}
		}
		for(RE int i=1;i<=2;i++){
			for(RE int j=1;j<=2;j++){
				a[i][j]=s[i][j];
				s[i][j]=0;
			}
		}
	}
	cout<<(ans[1][1]+ans[2][1])%mod;
	return 0;
}