矩阵快速幂！

显然这题可以用矩阵快速幂完成，起始矩阵是斐波那契数列前两项 $\begin{bmatrix} 1\\ 1 \end{bmatrix}$，转移矩阵是 $\begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}$，即矩阵递推式 $\begin{bmatrix} f(i)=1\times f(i-1)+1\times f(i-2)\\ f(i)=1\times f(i-1)+0\times f(i-2) \end{bmatrix}$ 中各项的系数。时间复杂度是 $O(\log n)$ 的，跑得飞快，加上模数后 $n$ 在 $\text{long long}$ 范围都能轻松跑过。

#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(long long x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar((x%10)^48);
}

struct mat{
	long long 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]+a.a[i][k]*b.a[k][j];
	return c;
}

int main(){
	long long n=read();
	if(n<=2){
		putchar(49);putchar(10);return 0;
	}
	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);
	
	write(ans.a[2][1]);putchar(10);
	return 0;
}