#include<bits/stdc++.h>

#define fast ios_base::sync_with_stdio(false); cin.tie(nullptr); cin.tie(nullptr);
#define int long long
#define ld long double
#define pb emplace_back
#define range(v) v.begin(),v.end()
#define mod 1000000007
#define inf (int)1e15
#define pii pair<int,int>
#define ff first
#define ss second
// #define N --

using namespace std;

vector<vector<int>> multiply(vector<vector<int>>& a, vector<vector<int>>& b) {
	vector<vector<int>> c(2, vector<int>(2));
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			for (int x = 0; x < 2; x++) {
				c[i][j] += (a[i][x] % mod * b[x][j] % mod) % mod;
				c[i][j] %= mod;
			}
		}
	}
	return c;
}

vector<vector<int>> power(vector<vector<int>> a, int p) {
	if (p == 1) return a;
	vector<vector<int>> ans = power(a, p / 2);
	ans = multiply(ans, ans);
	return (p & 1) ? multiply(a, ans) : ans;
}

int fastFib(int n) {
	if (n == 0 or n == 1) return n;
	vector<vector<int>> t{{1, 1}, {1, 0}};
	vector<int> fb{1, 0};
	t = power(t, n - 1);

	int ans = 0;
	for (int i = 0; i < 2; i++) {
		ans += (t[0][i] % mod * fb[i] % mod) % mod;
		ans %= mod;
	}
	return ans %= mod;
}

int32_t main() {
	fast
	int t_c = 1;
	cin >> t_c;
	while (t_c--) {
		// cout << "#: ";
		int n;
		cin >> n;
		cout << fastFib(n) << endl;
	}
}