https://www.spoj.com/problems/MAIN746

#include
#include

#define ll long long

int mod = 1000000007;
using namespace std;

vector<vector> mult(vector<vector> &a, vector<vector> &b) {
return {
{ (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % mod, (a[0][0]*b[0][1] + a[0][1]*b[1][1] ) % mod },
{ (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % mod, (a[1][0]*b[0][1] + a[1][1]*b[1][1] ) % mod}
};
}

ll fib(ll n) {
vector<vector> base = {
{1, 1},
{1, 0}
};

vector<vector<ll>> res = {
	{1, 0},
	{0, 1}
};

while(n) {
	if(n & 1) {
		res = mult(res, base);
	}
	
	base = mult(base, base);
	n >>= 1;
}
return res[0][1];

}

int main() {
// your code goes here
int T;
cin >> T;
//vector ans;
while(T–) {
ll N;
cin >> N;
if(N == 0) cout << 0 << endl;
if(N == 1) cout << 2 << endl;
else cout << fib(N + 3)<< endl;
}

//for(auto& i : ans) cout << i << endl;
return 0;

}