M contest 3 thSon

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

const int N=2;
const long long base=1000000007;

struct Matrix{
    long long m[N][N];
    Matrix(){
        m[0][0]=0;
        m[0][1]=1;
        m[1][0]=1;
        m[1][1]=1;
//      for (int i=0; i<n; i++){
//          for (int j=0; j<n; j++) m[i][j]=0;
//      }
    }
};

Matrix operator * (Matrix a, Matrix b)
{
    Matrix res;
    for (int i=0; i<=1; i++)
        for (int j=0; j<=1; j++)
        {
            res.m[i][j] = 0;
            for (int k=0; k<=1; k++)
                res.m[i][j] = (res.m[i][j]+a.m[i][k]*b.m[k][j])%base;
        }
    return res;
}

Matrix Solve (Matrix a, long long n)
{
    if (n==1)
        return a;
    if (n%2!=0)
        return Solve(a,n-1)*a;
    Matrix tmp = Solve(a,n/2);
    return tmp*tmp;
}

int main() {
    int t;
    cin>>t;
    while (t--){
        long long n;
        cin>>n;
        Matrix a;
        Matrix result = Solve(a, n);
        cout<<result.m[0][1]<<endl;
    }
    return 0;
}