题目大意：求斐波那契数列第n项。第一项和第二项为1。

解题思路：矩阵快速幂模板题。

公式：

$$\begin{bmatrix} F[n] \\F[n-1] \end{bmatrix} \quad =\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} ^{n-2} \quad  × \begin{bmatrix} F[2] \\ F[1] \end{bmatrix} \quad$$

C++ Code：

#include
     
      #include
      
       using namespace std;struct mat{    long long a[2][2];};mat mul(mat x,mat y){    mat ans;    memset(&ans,0,sizeof ans);    for(int i=0;i<2;++i)    for(int j=0;j<2;++j)    for(int k=0;k<2;++k)    ans.a[i][j]=(ans.a[i][j]+x.a[i][k]*y.a[k][j])%1000000007;    return ans;}void pow(long long n){    mat p;    p.a[0][0]=p.a[0][1]=p.a[1][0]=1;    p.a[1][1]=0;    mat ans;    ans.a[0][0]=ans.a[1][1]=1;    ans.a[0][1]=ans.a[1][0]=0;    while(n){        if(n&1){            ans=mul(ans,p);        }        p=mul(p,p);        n>>=1;    }    p.a[0][0]=p.a[1][0]=1;    p.a[0][1]=p.a[1][1]=0;    ans=mul(ans,p);    printf("%d\n",(int)ans.a[0][0]);}int main(){    long long n;    scanf("%lld",&n);    if(n>2)    pow(n-2);else puts("1");    return 0;}