由于没有想到很好的智慧做法&没有题解 我直接用的快速幂+矩阵快速幂求解 如果这是唯一正解的话 那感觉可以本题评到绿+~蓝-了

代码如下

#include<bits/stdc++.h>
using namespace std;

const int N=100;
const int mod=1e9+7;
long long storing[N];

long long quickMul(long long a,long long b)
{
	long long result=1;
	
	while(b)
	{
		if (b&1) result=result*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	
	return result;
}

struct Matrix 
{
    long long a[3][3];
    
    Matrix()
    {
    	memset(a,0,sizeof(a)); 
    }
    
    Matrix operator * (const Matrix &b) const //定义2*2变换乘法
    {
        Matrix res;
        for (long long i=1;i<=2;++i)
        {
            for (long long j=1;j<=2;++j)
            {
                for (long long k=1;k<=2;++k)
                {
                    res.a[i][j]=(res.a[i][j]+a[i][k]*b.a[k][j])%mod;
                }
            }
        }
        
        return res;//返回矩阵
    }
}ans,base;

void initFibonacci() 
{
    base.a[1][1]=base.a[1][2]=base.a[2][1]=1;
    base.a[2][2]=0;
    
    ans.a[1][1]=ans.a[1][2]=1;
    ans.a[2][1]=ans.a[2][2]=0;
}

void qpow(long long b) 
{
    while(b) 
    {
        if (b&1) ans=ans*base;
        base=base*base;
        b>>=1;
    }
}


int main()
{
	int T;cin>>T;
	storing[0]=1;
	storing[1]=1;
	
	for (int i=2;i<=N-1;i++)
	{
		storing[i]=storing[i-1]+storing[i-2];
		if (storing[i]>=1e9) break;
	}
	
	while(T--)
	{
		int n;cin>>n;
	
		long long a=n;
		for (int i=1;i<=N-1;i++)
		{
			if (storing[i]>=1e9) break;
			if (a>=storing[i]) a++;
			else break;
		}
		
		long long b;
		if (n>=2)
		{
			initFibonacci();
    		qpow(n-2);
			b=ans.a[1][1];
		}
		else
		{
			b=1;
		}
    	
    	//cout<<a<<' '<<b<<'\n';
    	
		cout<<quickMul(a,b)<<'\n';
	}
}