#include<iostream>
#include<cstdio>
#define N 100000
#define M 1600
#define mod 1000000007
using namespace std;
long long read()
{
	char c=0;
	long long sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int table[M+1]={2,1,1,1,743514368,427914749,142266572,823590429,701026562,129615831,2145473,251039972,738690414,582367837,688747903,158782026,845186490,963228105,74234973,95899160,748140933,453345523,878174413,96529595,529849730,924552173,183819483,606959946,919859049,565392647,630004091,351874881,966643317,578349963,150458936,45068547,609220420,679508228,413034895,911330235,229212790,938860569,113490160,41792705,453587067,181713426,916568323,927857513,822978810,334017690,285655261,985076095,874966173,75790478,845305341,384969559,754261452,879713116,948996493,798972112,357589430,617352242,427772476,609881164,509740079,422587902,880473732,317811868,723156448,793292925,791474562,668667243,606283147,848958500,724072411,971262196,305775458,811339287,342949451,804252429,596562841,595629697,770607930,287709460,360081562,896768673,624417692,460962884,49797108,183341720,435269223,242924640,881821926,560258939,77632219,307966364,374519004,210227790,61374361,314927752,423193219,285170713,340715873,587832258,50170173,178272235,342892600,716789037,470388078,396443216,116978568,559800400,368472980,698519603,457283141,175773063,554116480,338897045,80635582,742811638,996508581,160535291,515822430,443398109,912150328,398872109,170568114,928388716,260734691,734424926,531543884,591332137,955760866,150336014,902375866,950880091,537415904,521552241,340622424,876122534,365695927,147295533,158557151,980575210,479625828,676589742,887535529,720037320,712718687,847135698,407991216,652399283,19751019,946199813,877476847,788929515,811314993,49451763,681950224,274863889,802601667,636426892,231901187,162573832,563133715,702841345,214013176,973723307,175858918,862376551,774677620,536559784,448587173,570390907,498386667,219571592,653726405,584264394,560190589,757368880,51063241,978202062,19490650,109128481,626152461,15734342,148802682,156551032,566586749,423692740,177099088,861683835,970943998,830438034,698242007,434560321,273044048,939595235,457844039,948011151,942173741,383071956,438902912,227252150,718821318,911614732,271054199,794099507,175878586,35959989,868834203,310097470,693140303,674373165,798910662,29152023,352595533,130484736,664013428,832757261,354928135,243202873,770931661,268991474,836077124,277982651,169912902,864032872,196626112,161391932,917509102,916024947,908280604,980683794,538442127,619912050,986561960,959890134,930719714,7541071,100235732,869263662,123324963,521153550,465658678,110306362,510678762,285553948,212376533,665328257,906703077,256553204,869862055,819570306,895106736,217152755,838746423,542603264,333036006,990315685,313095809,586171847,555575343,150340342,18701676,510768937,831627291,295883239,496491318,582935827,775375876,642349298,798259322,97063911,925385199,897600255,542423577,514721975,704668171,974923033,492373393,666456689,67796760,19044256,462722313,584115,214711935,132718806,92648155,835597012,551784788,371332933,282587703,887894701,992028165,956121391,450162810,41242392,688986730,435647536,86446972,481622440,40648725,110528094,515909181,916569206,974265980,262569608,223396936,476209966,758607759,496541315,75546065,990392295,706864689,146662156,827003106,59601460,366702735,153320856,656917987,781507281,964068511,790698861,985995765,404084961,544341917,358143145,519301569,662653496,61846635,273374284,458577562,860580288,294152778,789991570,250672185,789452834,738614375,277615883,424111180,865238787,432369373,798506551,663460116,603306389,281424903,878534620,246840393,272593766,131865143,22265832,227039423,101384158,652970649,442560549,127666120,573365588,600666272,604714057,94451417,590575638,431089528,408001084,156381402,614491978,746596774,328752204,675927607,959170658,447512800,880168756,22037434,43911347,21305397,493298664,376562277,746064955,682842319,72318799,797484954,634731910,553626390,106946478,748241353,786627666,680762952,146841264,55420210,850281241,40469329,605820896,467083666,239361589,15544867,112126174,537186170,460027893,745820088,900756938,771539418,501975370,308018643,972329566,310499071,522926401,434549969,524990601,646499353,646749052,856805062,315307943,992388661,828352092,118854468,406520279,729411102,551666334,763961900,508970947,519419104,709663208,85656026,172960807,617068577,791878263,428570621,244337651,100316444,619912105,808386090,939032676,346420400,647802136,557295512,302095091,391409343,794550676,6070271,441342996,540123067,64546024,989059622,294977918,773292671,865992234,131595120,305052362,169701388,128250468,857762844,410547655,459996580,53669729,405612331,737232364,201258281,878490101,389365840,696838381,985480930,227616067,290453625,714326728,347873042,455085758,501630223,775846556,597914241,489710308,144318572,838349417,626025702,406353079,735417883,246967905,138752267,291022102,43650334,56572985,10077027,543338227,543859493,899547025,903279102,337339204,258493423,769392507,43214843,455266619,824234438,329543609,516575918,654696959,427460295,75267116,793466188,464185366,318571439,367106612,52573686,832000790,5366838,176574275,468313022,980122347,505291254,773126492,921382019,884036385,613456111,819162321,522782782,724882526,709586172,440889738,33020703,957390991,911583198,126677837,626178654,191805583,816636603,203459228,144680277,366829317,322072542,396615927,960809570,664287175,994445053,324125086,280350882,779743044,214452615,248489381,928971808,333502591,86488282,833120075,404532293,522889238,549774956,609903713,949191561,139982387,468806604,811735637,677703266,958611312,632443595,69708440,206806975,203166788,669672025,908158425,383256426,816555528,594128994,371717950,565183860,385217133,629087827,694992306,53671871,343011399,135151557,869764977,264511787,607072669,886248257,868299584,42869804,306283523,265987962,771765897,405939508,751157236,486099930,201115253,896150852,382905370,227766344,990543381,628340074,596510236,830031350,339096754,368489098,543108535,170192692,653097926,762396072,194118990,863208737,930491629,948044302,912797431,167549175,501342302,102759784,643810556,943288264,10951390,153361057,551496393,208930107,81728034,930537392,395762788,12979506,824957813,73039258,689024872,227937816,27905656,602738576,889800236,530575919,943347644,499667580,139125407,671494906,492444305,970965123,914940986,587744140,422255239,663451875,676162095,70811867,643494059,665787070,730377086,856328502,375004090,426505439,234020891,594018344,375415049,878078133,927247909,172480567,147865527,223466940,489652292,207255780,813490914,223353370,775573753,712923958,234780882,205752865,595712963,926140646,31456877,718345611,950224848,862179002,805837006,21099322,557283340,81984396,551140496,671728577,981851192,176932824,227699543,416028271,643393945,74806098,646889365,874557852,261129924,615716361,763605506,740062581,311791404,284693712,613969635,958566187,51060681,557339659,489029923,574507352,47377993,4114041,34552270,4462786,995339551,576626388,861900870,159948561,101962662,540984902,252939466,127565365,578364216,948487368,790096378,708337801,453616284,927604276,966081410,573755426,567219038,984020838,28164088,388809753,274693877,448927251,336807300,68311114,540490062,932005321,802722286,782708900,47608286,789915895,466406976,413585806,131997513,211319693,934222028,878117515,508961428,112509636,722864339,435989101,509636105,696956124,4905783,943923182,27346502,826030932,254638413,335290695,759428437,797525827,716149906,48652903,382081205,529637428,806162020,953914063,316815676,182774154,990086404,811897622,672619365,941988026,390195744,214378923,158430406,438152769,816937348,830970139,86065435,55712784,542633842,368109911,269712562,41542859,255832760,172080569,369253118,63278044,714210288,29257650,61297561,453319586,708727937,527649309,909926655,904566778,246344463,942718844,726894210,448361423,710069298,968569533,182261688,446323035,963882251,229530864,909196358,104641089,479169303,713795603,701205086,556957806,62514131,346823448,401545400,142943906,658361894,440253003,699441200,52846886,89454975,49934100,28232538,570655139,900752674,11750199,704599547,891189253,395893771,77780065,948040420,53886374,130797941,64355173,69200091,981829403,245821741,35583710,30341662,993925215,995897841,173298928,531385276,891280848,6989386,512271156,324916013,192289638,768412922,390456645,988893389,23666418,221376283,559201355,768412637,183089123,36406303,640002827,128723474,574270811,755924237,710587735,755282483,724850732,315835739,152658303,49186181,638758990,866768105,401347168,792314549,730378707,184622188,898165515,952904959,216442873,252823126,603786063,93460403,193030800,306333024,787845234,525898408,211463328,404901024,483747510,981502314,876859801,822308182,470552078,425805530,467207385,318343741,653635156,217557424,361960527,236062984,122949373,263587402,105652868,591520945,505001084,526514021,605917509,360150239,246139527,149377408,286852604,222935817,727794428,445153012,265111995,338176968,109648981,773433671,601774777,484875222,612513180,140862652,743663604,817395804,253893833,739740760,481087326,844336460,984806867,626694350,148997218,140973425,280309120,45816521,276134667,846097506,478810914,647468868,839496022,90062660,846580800,126616541,543355949,347896884,713852029,244790279,526936141,917286446,880716238,233133622,74182090,37536740,826983557,363889335,68242202,205006772,312106016,393319507,660373297,939794739,169820307,781563145,297134889,88658012,484249969,521797585,839880711,729166432,179640899,335237323,236990467,496027688,936115845,729839811,380468551,213884510,641369481,283810444,505665883,959215434,359149834,301001039,500932448,423298267,557879722,943662027,251333203,824922092,711988896,966822735,118306325,737226053,270181822,888782906,688154841,888595391,542298109,593507798,641403709,139903827,973329668,126163316,742983253,70140231,511514910,47247893,600472356,56327286,274220518,770320618,880490892,100884094,145236228,561906971,922041215,852403558,242264926,85997670,596813709,134851164,810226957,700602860,188646324,271925651,405061071,944923242,168697828,767369162,377100740,543854065,870137154,114349848,155434921,882468677,865997440,178315721,305541600,196454841,594369941,258929802,779203317,406132650,641668225,617278362,513257898,155934107,109160837,344008549,574091819,499398753,136455619,328538186,979814378,401596622,183747488,315162390,472027845,43359955,689311366,805284049,112748491,504748935,510782107,108219185,393424794,663655707,691102499,505475849,736745605,598360005,945314751,714793047,415779638,959976068,764654830,344995769,236987748,616182077,318740834,387588068,225250449,101056385,101649508,217698461,732838724,848328868,342696781,991809942,758402033,373642423,622985553,740203986,595712340,725443184,400191483,325975762,779094991,400999798,807565287,154646423,469431163,621509439,596966714,6526256,221305942,714740750,812505477,208285213,76817539,349777577,783635402,320096084,229077181,104587916,807551124,218760047,259039121,202263189,603875746,635825839,142210887,134375178,465747446,979298895,977357948,266934125,970114938,988120199,753293325,393788815,141301396,1104478,109261300,722585849,366523166,842863364,129057836,73047017,293908121,888309813,769058435,393483040,694884164,592520140,398275736,860819437,350809273,191868473,106448934,213761086,952749465,401623958,892389489,384800407,286298895,478781078,734602729,820778601,210344015,999748930,313776850,416995589,713175572,2755712,804681893,457289933,2334066,361978780,755867939,106672656,625273236,844312596,254252611,825447202,796229175,797452253,618387788,578444546,711836478,876231641,470572910,260860548,293622197,521154134,473442876,898517831,440688851,242907418,407630196,488708055,18486900,899918750,480459779,167208003,423684448,244798087,822886944,300643625,360487223,505483460,40382732,292431437,136113602,995599090,389607201,778197019,13753911,615363855,431114683,522168047,133150969,248811010,99150787,480385338,296306346,844207679,493379283,638576718,78406834,590944619,1787625,586951291,856502913,853814431,828574456,403017733,967749298,318231189,964969554,851963162,600270870,179179132,266830884,907395566,688649109,331903751,710922641,592729168,832746549,824550591,310325107,660809189,80396382,549919813,830504570,134676582,625767185,250896986,982702538,829046936,584203809,873292656,481142649,2184230,190806783,268346238,491523843,141289084,823257653,215473284,883460067,755902538,126769875,913591891,857782808,202229781,989928498,313230268,733836674,153104252,497690667,503348330,485739665,821286158,172687972,659831427,695130835,709881684,975297166,911950675,357788285,106409617,499516197,243155341,251552903,737748430,304372660,867275036,409336085,520361553,236145381,695054032,537272918,530743097,363171248,863967675,92532829,257203717,608591561,968400060,910952408,205699096,734255765,375905466,798705958,60544690,771784418,409401475,772303784,801161536,567013504,459562169,712955240,298516454,940779514,384150951,622563251,913976203,266535332,703587416,385474415,998729321,991220495,908981273,353820128,182299267,280336464,450982522,945620781,726887832,507581755,72248990,448411347,243420436,485507278,175369659,491139340,574715857,796519091,363518683,562366165,812102482,106785601,334807693,753064744,171793286,71644950,614956434,671817113,570451469,584865685,266837734,332130330,27754208,288883373,321377680,18206776,946403287,582979715,341935591,629681961,76285439,557026098,658107233,634967934,154677297,289461478,215727153,894767510,646985243,343367157,995200834,384249367,512903382,261138937,823224131,781452061,754417297,111671530,824937394,182411193,706079171,831952840,889383754,233914404,55313511,379038157,961893209,127221394,65263709,662572959,835526635,903108185,316387542,866183483,373584182,277116219,739690286,744242133,893418671,747854758,637531422,714725321,844674648,437929299,710493360,272102587,759118851,44865065,392885836,374662937,43118208,632696810,199328822,103030899,933707402,50561428,867038437,669815238,255734234,221674605,567224622,973346162,269909471,923670168,898883160,880819675,429314464,967125012,81837435,283789142,917436730,11830304,616460699,579104450,337287915,599284222,705149020,611473149,258981637,106157143,182284568,473099317,683274893,636997092,170316654,21465593,973154206,730483866,303369005,886207163,379105971,747162997,803727971,186193520,666467402,524475872,363188560,102521791,21588361,540682387,551636721,601891619,83571807,166352852,103918809,697443192,106184837,608762846,570512880,602653962,561622045,663116421,872640306,17009774,669017161,258266640,789737912,777765033,369976775,207645510,426407459,968318276,802210454,787682360,655109074,389228004,460180633,59746738,204130021,312852628,529578942,223174644,739220199,197146161,216067806,352885085,431153178,611349657,135033066,484402806,249560430,346992884,184071548,861790481,365589805,203583890,689955854,730435813,864888727,443493148,923779110,562060784,579559522,762265128,632847236,642372879,109351095,13919708,234053196,857808490,53163589,636204621,511009449,222875180,19894482,450797263,807426732,892904045,126551906,832412943,120521363,296505210,63234654,681040924,451023059,103774907,255768350,545746096,601532661,991356411,570442966,84077207,219683800,1545111,20935209,706805183,251985215,971465813,746952075,917261659,58756077,646864808,13096249,323353295,467807297,769507495,276204741,68642575,368312564,356062147,427968390,40518946,708851811,693373735,937875562,744862073,70647419,124962832,562096079,840139811,612433950,883615645,139950553,81739488,479917181,194827001,230828304,793857941,313858038,324039347,815386534,554529150,497247853,107313286,430045386,454759028,945315700,642473933,693962566,119801893,135262428,295891894,219011871,989352551,414817165,500280021,44656147,588717957,159321991,696097337,118773069,493688297,860476514,296069457,572407258,431075512,69074316,28057871,354424106,900382524,686561002,460119063,912820641,353951721,666755517,315358412,934760008,461456385,221081138,684457576,841363052,348338213,46948501};
int fast_pow(int a,int b)
{
	int res=1,mul=a;
	while (b)
	{
		if (b&1) res=1ll*res*mul%mod;
		mul=1ll*mul*mul%mod,b>>=1;
	}
	return res;
}
void Adder(int &x,int d)
{
	x+=d;
	if (x>=mod) x-=mod;
	return;
}
int MD(int x)
{
	return x>=mod?x-mod:x;
}
int MD2(int x)
{
	return x<0?x+mod:x;
}
struct matrix
{
	int d[2][2];
	bool operator == (const matrix &t)const
    {
		for (int i=0;i<=1;++i)
			for (int j=0;j<=1;++j)
				if (d[i][j]!=t.d[i][j])
					return 0;
		return 1;
	}
};
matrix c,nw,zero,A=(matrix){1,1,0,1},B=(matrix){1,0,1,1},dp;
matrix operator * (matrix a,matrix b)
{
	c=zero;
	for (int k=0;k<=1;++k)
		for (int i=0;i<=1;++i)
			if (a.d[i][k])
			{
				for (int j=0;j<=1;++j) Adder(c.d[i][j],1ll*a.d[i][k]*b.d[k][j]%mod);
			}
	return c;
}
int T;
long long n;
int F(long long x)
{
	if (x<=799039878)
	{
		int ds=(x-1)/2000000;
		nw=(matrix){table[ds<<2],table[(ds<<2)+1],table[(ds<<2)+2],table[(ds<<2)+3]};
		for (int i=ds*2000000+2;i<=x;++i) nw=nw*nw*B;
		return MD2(MD(MD(MD(nw.d[0][0]+nw.d[0][1])+nw.d[1][0])+nw.d[1][1])-1);
	}
	else return fast_pow(2,(x-799039877)%(mod-1));
}
int main()
{
	T=read();
	while (T--) n=read(),printf("%d ",F(n));
	puts("");
	return 0;
}