100分解法
矩阵快速幂模版题
复杂度O(Tlogn)

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct matrix{
    long long val[10][10],x,y;
    matrix(){
        memset(val,0,sizeof(val));
        x=y=1;
    }
    void setfib(){
        x=2;y=2;
        val[1][1]=1;
        val[1][2]=1;
        val[2][1]=1;
        val[2][2]=0;
    }
    void setmod(long long mod){
        int i,j;
        for(i=1;i<=x;i++) for(j=1;j<=y;j++) val[i][j]%=mod;
    }
};
matrix operator * (matrix a,matrix b){
    matrix res;
    int i,j,k;
    if(a.y!=b.x) return res;
    res.x=a.x;
    res.y=b.y;
    for(i=1;i<=a.x;i++)
        for(j=1;j<=b.y;j++)
            for(k=1;k<=a.y;k++) res.val[i][j]+=a.val[i][k]*b.val[k][j];
    return res;
}
matrix pow(matrix pi,long long q,long long mod){
    matrix res,w=pi;
    int fl=0;
    while(q){
        if(q&1){
            if(fl) res=res*w; 
            else res=w,fl=1;
        } 
        res.setmod(mod);
        w=w*w;
        w.setmod(mod);
        q>>=1;
    }
    return res;
}
long long n,ans;
int T;
int main(){
    scanf("%d",&T);
    matrix pi,st;
    st.x=2;
    st.y=1;
    st.val[1][1]=1;
    st.val[2][1]=0;
    while(T--){
        scanf("%lld",&n);
        pi.setfib();
        pi=pow(pi,n-1,1000000007);
        pi=pi*st;
        pi.setmod(1000000007);
        ans=pi.val[1][1];
        printf("%lld\n",ans);
    }
}