#include <iostream>
using namespace std;
using ull = unsigned long long;

ull Adder(ull a, ull b, ull carry) {
	ull ret = 0;
	for (ull mask = 1; mask != 0; mask <<= 1) {
		ull am = (a & mask);
		ull bm = (b & mask);
		ull rm = am ^ bm ^ carry;
		ret |= rm;
		carry = (am & bm | am & carry | bm & carry) << 1;
	}
	return ret;
}

ull Plus(ull a, ull b) {
	return Adder(a, b, 0);
}

ull Minus(ull a, ull b) {
	return Adder(a, ~b, 1);
}

ull Mul(ull a, ull b) {
	ull ret = 0;
	for (ull mask = 1; mask != 0; mask <<= 1, a <<= 1) {
		ull bm = (b & mask);
		if (bm) {
			ret = Plus(ret, a);
		}
	}
	return ret;
}

ull Mod(ull dividend) {
	const ull Modulo = 1000000007;
	for (ull divisor = Modulo << 34; divisor >= Modulo; divisor >>= 1) {
		if (dividend >= divisor) {
			dividend = Minus(dividend, divisor);
		}
	}
	return dividend;
}

struct Hoge {
	ull k;
	ull l;
};

Hoge FormHoge(ull i) {
	if (i == 0) return Hoge{ 1, 0 };
	if (i == 1) return Hoge{ 0, 1 };
	ull half = i >> 1;
	if ((half << 1) != i) {
		Hoge sub = FormHoge(Minus(i, 1));
		return Hoge{ sub.l, Mod(Plus(sub.k, sub.l)) };
	}

	Hoge tmp = FormHoge(half);
	ull new_k = Mod(Plus(Mul(tmp.k, tmp.k), Mul(tmp.l, tmp.l)));
	ull new_l = Mod(Mul(tmp.l, Plus(tmp.k << 1, tmp.l)));
	return Hoge{ new_k, new_l };
}

ull Lucas(ull i) {
	Hoge hoge = FormHoge(i);
	return Mod(Plus(hoge.k << 1, hoge.l));
}

int main() {
	ull T;
	cin >> T;
	for (ull i = 0; i < T; i = Plus(i, 1)) {
		ull a;
		cin >> a;
		cout << Lucas(a) << endl;
	}
	return 0;
}