p1962,悬赏关注

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1000000007;
struct matrix{
    LL c[3][3];
    matrix(){memset(c,0,sizeof c);} 
}F, A;
matrix operator*(matrix &a,matrix &b){
    matrix t;
    for(int i=1;i<=2;++i){
        for(int j=1;j<=2;++j){
            for(int k=1;k<=2;k++){
                t.c[i][j]=(t.c[i][j]+(a.c[i][k]*b.c[k][j])%mod)%mod;
            }
        }
    }
    return t;
}
void quickpow(LL n){
    F.c[1][1]=F.c[1][2]=1;
    A.c[1][1]=A.c[1][2]=A.c[2][1]=1;
    while(n){
        if(n&1){
            F=F*A;  
        }
        A=A*A;
        n>>=1;
    }
}
int main(){
    int n;
    cin>>n;
    if(n<=2){
        cout<<1;
    }else{
        quickpow(n-2);
        cout<<F.c[1][1];
    }
    return 0;   
}