AC code:

#include <bits/stdc++.h>//太简单了就不写注释了
using namespace std;
#define int long long
const int mod = 1e18 + 7;
struct Matrix
{
    long long z[105][105];
    Matrix()
    {
        memset(z,0,sizeof z);
    }
};
Matrix operator * (const Matrix &a, const Matrix &b)
{
	Matrix c;
	for(int i = 1;i <= 2;i ++)
	{
		for(int k = 1;k <= 2;k ++)
		{
			for(int j = 1;j <= 2;j ++)
			{
				c.z[i][j] += a.z[i][k] * b.z[k][j];
				c.z[i][j] %= mod;
			}
		}
	}
	return c;
}
Matrix qpow(Matrix a, long long b)
{
    Matrix mul;
    for(int i = 1;i <= 2;i ++)
    {
    	mul.z[i][i] = 1;
    }
    while(b)
    {
    	if(b % 2)mul = mul * a;
    	a = a * a;
    	b /= 2;
    }
    return mul;
}
Matrix A,B;
signed main()
{
	int T;
	cin>>T;
	while(T --)
	{
		A.z[1][1] = 1,A.z[1][2] = 1;
		B.z[1][1] = 1,B.z[1][2] = 1;
		B.z[2][1] = 1,B.z[2][2] = 0;
		int x;
		cin>>x;
		if(x == 1 || x == 2)
		{
			cout<<1<<endl;
			continue;
		}
		if(x == 0)
		{
			cout<<0<<endl;
			continue;
		}
		A = A * qpow(B,x - 2);
		cout<<A.z[1][1]<<endl;
	}
	return 0;
}