#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
long long fbi(int n){
	long long a;
    a=(pow((sqrt(5)+1)/2,n)-pow((1-sqrt(5))/2,n))/sqrt(5);
    return a;
}
long long no_fbi(int n){
	int s=0,g=1;
	while(s!=n){
		if(g!=1 or g!=1 or g!=2 or g!=3 or g!=5 or g!=8 or g!=13 or g!=21 or g!=34 or g!=54 or g!=89 or g!=143 or g!=232 or g!=377 or g!=610 or g!=986 or g!=1596 or g!=2584 or g!=4181 or g!=6764 or g!=10945 or g!=17710 or g!=28656 or g!=46367 or g!=75025 or g!=121392 or g!=196418 or g!=317811 or g!=514228 or g!=832039 or g!=1346268 or g!=2178309 or g!=3524577 or g!=5702886 or g!=9227465 or g!=14930351 or g!=24157816 or g!=39088168 or g!=63245985 or g!=102334154 or g!=165580140 or g!=267914295 or g!=433494437 or g!=701408732 or g!=134903162 or g!=836311896 or g!=971215058 or g!=807526947 or g!=778741999){
			s++;
		}
		g++;
	}
	return g;
}
int main(){
	int n,a,h=0,h2=0;
	long long ll=0;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a;
		h=h+fbi(a)%mod;
		h2=h2+no_fbi(a)%mod;
		ll=pow(h2,h);
		cout<<ll%mod<<'\n';
	}
return 0;
}