代碼如下。

const int N=1e5+10,MOD=1e9+7;
lnt pow(lnt a,lnt b,lnt p){
    lnt ans=1;
    for(;b;debug("pw1"),b>>=1,a=a*a%p) if(b&1) ans=ans*a%p;
    return ans;
}
// Warning - Make mod be a prime!!!!!!!!
template<int mod>
struct Z{
    lnt val;
    Z(lnt x=0):val(x){
        val%=mod;
    }
    Z operator+(const Z &rhs)const{
        return Z(val+rhs.val);
    }
    Z operator-(const Z &rhs)const{
        return Z(val+mod-rhs.val);
    }
    Z operator*(const Z &rhs)const{
        return Z(val*rhs.val);
    }
    Z operator/(const Z &rhs)const{
        return Z(val*pow(rhs.val,mod-2,mod));
    }
    Z operator+=(const Z &rhs){
        return (*this=*this+rhs);
    }
    Z operator-=(const Z &rhs){
        return (*this=*this-rhs);
    }
    Z operator*=(const Z &rhs){
        return (*this=*this*rhs);
    }
    Z operator/=(const Z &rhs){
        return (*this=*this/rhs);
    }
};
typedef Z<MOD-1> eulerm;
struct mat{
    int r,c;
    eulerm dta[3][3];
    mat(int r,int c):r(r),c(c){
        memset(dta,0,sizeof(dta));
        if(r==c) for(int i=1;i<=r;++i) dta[i][i]=1;
    }
    mat operator*(const mat &rhs)const{
        if(c!=rhs.r) throw "WTF!!!!";
        mat ans=mat(r,rhs.c);
        for(int i=1;i<=r;++i){
            for(int j=1;j<=rhs.c;++j){
                ans.dta[i][j]=0;
                for(int k=1;k<=c;++k) ans.dta[i][j]+=dta[i][k]*dta[k][j];
                debug("mmul");
            }
        }
        return ans;
    }
}fib=mat(2,2);
mat pow(mat a,lnt b){
    if(a.r!=a.c) throw "WTF!!!";
    mat ans=mat(1,2);
    ans.dta[1][1]=1,ans.dta[1][2]=1;
    for(;b;debug("pow2"),b>>=1,a=a*a,debug("pow2 b = "+to_string(b))) if(b&1) ans=ans*a;
    return ans;
}
lnt fibo(lnt k){
    if(k<=2) return 1;
    fib.dta[1][1]=1,fib.dta[1][2]=1,fib.dta[2][1]=1,fib.dta[2][2]=0;
    debug("fib");
    return pow(fib,k-2).dta[1][1].val;
}