矩阵快速幂前来宣战

时间复杂度 $O(\log n)$，遥遥领先。

#include <cstdio>
#include <algorithm>
#include <memory.h>

using namespace std;

inline long long read(){
	long long x=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x*w;
}

void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar((x%10)^48);
}

struct mat{
	int a[3][3];
};

mat mul(mat& a,mat& b){
	mat c;
	memset(c.a,0,sizeof(c.a));
	for(int k=1;k<=2;k++)
		for(int i=1;i<=2;i++)
			for(int j=1;j<=2;j++)
				c.a[i][j]=(c.a[i][j]+(0ll+a.a[i][k])*b.a[k][j]%1000000007)%1000000007;
	return c;
}

int main(){
	long long n=read();
	if(n<=2){
		putchar(49);putchar(10);return 0;
	}
	n-=2;
	mat a;
	
	#define a a.a
	a[1][1]=1;a[1][2]=1;
	a[2][1]=1;a[2][2]=0;
	#undef a
	
	mat ans;
	memset(ans.a,0,sizeof(ans.a));
	ans.a[1][1]=1;ans.a[2][2]=1;
	
	do{
		if(n&1) ans=mul(ans,a);
		a=mul(a,a);n>>=1;
	}while(n);
	
	mat b;
	b.a[1][1]=b.a[2][1]=1;
	ans=mul(ans,b);
	
	write(ans.a[1][1]);putchar(10);
	return 0;
}