#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
	int len=0;
	char ibuf[(1<<21)+1],*iS,*iT,out[(1<<25)+1];
	#if ONLINE_JUDGE
	#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
 	#else
	#define gh() getchar()
	#endif
	#define reg register
	inline ll read(){
		reg char ch=gh();
		reg ll x=0;
		reg char t=0;
		while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
		while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
		return t?-x:x;
	}
	inline void putc(char ch){
		out[len++]=ch;
	}
	template<class T>
	inline void write(T x){
		if(x<0)putc('-'),x=-x;
		if(x>9)write(x/10);
		out[len++]=x%10+48;
	}
	inline void flush(){
		fwrite(out,1,len,stdout);
		len=0;
	}
	inline char getc(){
		char ch=gh();
		while(ch<'A'||ch>'Z') ch=gh();
		return ch;
	}
}
using IO::read;
using IO::write;
using IO::flush;
using IO::getc;
using IO::putc;
#define pii pair<int,int>
#define mpr make_pair
#define fir first
#define sec second
const int mod=1e9+7;
inline int add(int a,int b){ return a+b>=mod?a+b-mod:a+b; }
inline int dec(int a,int b){ return a>=b?a-b:a+mod-b; }
inline void inc(int &a,int b){ a=a+b>=mod?a+b-mod:a+b; }
inline int qpow(int x,int y){
	int res=1;
	while(y){
		if(y&1) res=1ll*res*x%mod;
		x=1ll*x*x%mod;
		y>>=1;
	}
	return res;
}
struct Matrix{
	int a[3][3];
	int n,m;
	inline void init(int N,int M){
		n=N,m=M;
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				a[i][j]=0;
	}
	inline int* operator[](int x){ return a[x]; }
	inline friend Matrix operator*(Matrix a,Matrix b){
		Matrix c;
		c.init(a.n,b.m);
		for(int k=0;k<a.m;k++)
			for(int i=0;i<c.n;i++)
				for(int j=0;j<b.m;j++)
					inc(c[i][j],1ll*a[i][k]*b[k][j]%mod);
		return c;
	}
	inline friend bool operator==(Matrix a,Matrix b){
		for(int i=0;i<a.n;i++)
			for(int j=0;j<a.m;j++)
				if(a[i][j]!=b[i][j])
					return 0;
		return 1;
	}
	inline void print(){
		for(int i=0;i<n;i++,puts(""))
			for(int j=0;j<m;j++)
				printf("%d ",a[i][j]);
		puts("");
	}
}D,T;
const int B=3e6;
int M[]={35135184,260651115,0,760851742,6009034,0,795986925,266660148,1,158782026,688747903,0,582367837,738690414,0,741149862,427438309,1,864690809,629292159,0,245628498,576844708,0,110319299,206136859,1,606959946,183819483,0,924552173,529849730,0,531512111,713669212,1,623490390,677105165,0,759371633,798127998,0,382862015,475233155,1,911330235,413034895,0,679508228,609220420,0,590838455,22255307,1,687570817,547424335,0,349958321,727085263,0,37529130,274509590,1,985076095,285655261,0,334017690,822978810,0,319093777,108634063,1,329649566,451314836,0,131170285,131028665,0,460819850,582343500,1,609881164,427772476,0,617352242,357589430,0,227233398,785361905,1,793976117,732007939,0,78644663,733453862,0,872620779,465461793,1,971262196,724072411,0,848958500,606283147,0,820220688,330355550,1,153807786,850336483,0,324130332,337450537,0,477938117,187787012,1,460962884,624417692,0,896768673,360081562,0,357731549,984499253,1,139035987,79412289,0,287286543,770827272,0,426322529,850239560,1,314927752,61374361,0,210227790,374519004,0,525155541,435893364,1,690769426,14569762,0,841061234,165571792,0,531830652,180141553,1,559800400,116978568,0,396443216,470388078,0,956243615,587366645,1,961714490,304646467,0,285232785,878139392,0,246947267,182785851,1,443398109,515822430,0,160535291,996508581,0,603933399,512331003,1,172597421,950804404,0,749597310,121622314,0,922194730,72426710,1,950880091,902375866,0,150336014,955760866,0,101216097,858136724,1,404326710,404060579,0,807882531,461001976,0,212209233,865062554,1,720037320,887535529,0,676589742,479625828,0,396627054,367161349,1,171675410,297129276,0,86260628,312649209,0,257936037,609778484,1,274863889,681950224,0,49451763,811314993,0,324315651,493265209,1,525420706,846098743,0,321001388,92414303,0,846422093,938513045,1,536559784,774677620,0,862376551,175858918,0,398936327,950536537,1,334540350,191318617,0,10137292,742504034,0,344677641,933822650,1,109128481,19490650,0,978202062,51063241,0,87330535,70553890,1,61220261,959876199,0,147200263,571593156,0,208420523,531469347,1,434560321,698242007,0,830438034,970943998,0,264998347,669185997,1,464535696,907027555,0,825302853,164903668,0,289838541,71931215,1,794099507,271054199,0,911614732,718821318,0,705714231,989875516,1,626802548,245909185,0,151594464,386975079,0,778397011,632884263,1,832757261,664013428,0,130484736,352595533,0,963241996,16608953,1,273019968,355757289,0,764630701,254532613,0,37650661,610289901,1,916024947,917509102,0,161391932,196626112,0,77416871,114135206,1,799473571,88256652,0,470381857,153612682,0,269855420,241869333,1,521153550,123324963,0,869263662,100235732,0,390417204,223560694,1,746291484,523939282,0,12019920,907962254,0,758311403,431901528,1,217152755,895106736,0,819570306,869862055,0,36723053,764968783,1,944547311,943343293,0,595689527,985329195,0,540236830,928672480,1,295883239,831627291,0,510768937,18701676,0,806652175,850328966,1,659531104,65078853,0,585810918,621750704,0,245342014,686829556,1,974923033,704668171,0,514721975,542423577,0,489645000,247091740,1,264432591,647700741,0,368554627,676223804,0,632987217,323924537,1,371332933,551784788,0,835597012,92648155,0,206929937,644432942,1,898703542,531036457,0,325224860,309272017,0,223928394,840308473,1,110528094,40648725,0,481622440,86446972,0,592150533,127095696,1,235541716,467175950,0,302477293,43065827,0,538019008,510241776,1,146662156,706864689,0,990392295,75546065,0,137054443,782410753,1,775496397,663977508,0,143758953,286251632,0,919255349,950229139,1,358143145,544341917,0,404084961,985995765,0,762228105,530337674,1,139039993,401425154,0,592317325,672230812,0,731357317,73655958,1,277615883,738614375,0,789452834,250672185,0,67068709,989286559,1,800817579,815440101,0,225109809,95470942,0,25927380,910911042,1,22265832,131865143,0,272593766,246840393,0,294859597,378705535,1,257871888,698429536,0,3072161,754137645,0,260944048,452567173,1,408001084,431089528,0,590575638,94451417,0,998576721,525540944,1,284641788,6091887,0,11542152,97398442,0,296183939,103490328,1,493298664,21305397,0,43911347,22037434,0,537210010,43342830,1,502690543,213162590,0,14050979,529152077,0,516741521,742314666,1,146841264,680762952,0,786627666,748241353,0,933468929,429004297,1,793593934,460118890,0,934922288,612347300,0,728516214,72466182,1,900756938,745820088,0,460027893,537186170,0,360784823,283006250,1,652042002,73512223,0,826403890,205695618,0,478445884,279207840,1,315307943,856805062,0,646749052,646499353,0,962056994,503304407,1,827275256,476200013,0,106823977,18311285,0,934099232,494511297,1,172960807,85656026,0,709663208,519419104,0,882624014,605075129,1,68542446,663548352,0,931068926,849387612,0,999611371,512935956,1,302095091,557295512,0,647802136,346420400,0,949897226,903715911,1,870086166,920716502,0,237609952,231440058,0,107696110,152156552,1,305052362,131595120,0,865992234,773292671,0,171044588,904887790,1,455177169,446816670,0,708643408,847707215,0,163820569,294523877,1,696838381,389365840,0,878490101,201258281,0,575328474,590624120,1,872563629,519124020,0,923050914,437041216,0,795614535,956165235,1,838349417,144318572,0,489710308,597914241,0,328059717,742232812,1,869961402,115228561,0,758206868,86303074,0,628168262,201531634,1,899547025,543859493,0,543338227,10077027,0,442885244,553936519,1,402504725,128671302,0,434648743,646815960,0,837153467,775487261,1,75267116,427460295,0,654696959,516575918,0,729964074,944036212,1,210430837,555926671,0,585853851,674141432,0,796284687,230068095,1,773126492,505291254,0,980122347,468313022,0,753248831,973604275,1,98628804,720560477,0,273957245,358572370,0,372586048,79132839,1,126677837,911583198,0,957390991,33020703,0,84068820,944603900,1,996351538,138310697,0,41595211,32952292,0,37946741,171262988,1,324125086,994445053,0,664287175,960809570,0,988412260,955254615,1,423865707,235120172,0,568073970,920209434,0,991939676,155329598,1,609903713,549774956,0,522889238,404532293,0,132792943,954307248,1,787774207,377774383,0,30344815,255130077,0,818119021,632904459,1,908158425,669672025,0,203166788,206806975,0,111325205,876478999,1,393898211,565313814,0,493604974,669492676,0,887503184,234806482,1,869764977,135151557,0,343011399,53671871,0,212776368,188823427,1,727374583,971961222,0,100883605,51995392,0,828258187,23956606,1,201115253,486099930,0,751157236,405939508,0,952272488,892039437,1,608977914,390436126,0,565120975,747947468,0,174098881,138383586,1,653097926,170192692,0,543108535,368489098,0,196206453,538681789,1,764649228,309827587,0,305216123,966321035,0,69865343,276148614,1,10951390,943288264,0,643810556,102759784,0,654761945,46048040,1,305458832,563991047,0,714896257,375060134,0,20355081,939051180,1,27905656,227937816,0,689024872,73039258,0,716930527,300977073,1,954241974,307548617,0,686811398,137480318,0,641053364,445028934,1,422255239,587744140,0,914940986,970965123,0,337196217,558709255,1,216853136,153551698,0,904448476,66992729,0,121301604,220544426,1,375415049,594018344,0,234020891,426505439,0,609435939,20523775,1,239076230,998739182,0,626149345,203268002,0,865225574,202007176,1,234780882,712923958,0,775573753,223353370,0,10354627,936277327,1,830637087,767463136,0,79887973,898661491,0,910525059,666124619,1,551140496,81984396,0,557283340,21099322,0,108423828,103083717,1,98309840,871595955,0,311219671,127076461,0,409529510,998672415,1,763605506,615716361,0,261129924,874557852,0,24735422,490274205,1,397005273,206996500,0,652786108,112729951,0,49791373,319726450,1,34552270,4114041,0,47377993,574507352,0,81930262,578621392,1,10115884,950923594,0,894431860,444494814,0,904547743,395418400,1,790096378,948487368,0,578364216,127565365,0,368460586,76052725,1,693063666,618714562,0,185922339,411174818,0,878986004,29889372,1,336807300,448927251,0,274693877,388809753,0,611501176,837737003,1,925174910,484824263,0,664731263,819742753,0,589906165,304567008,1,934222028,211319693,0,131997513,413585806,0,66219533,624905498,1,246844695,343597916,0,862556820,577644647,0,109401507,921242562,1,254638413,826030932,0,27346502,943923182,0,281984914,769954106,1,181711852,522887437,0,91327522,655140389,0,273039373,178027818,1,990086404,182774154,0,316815676,953914063,0,306902072,136688209,1,515576963,129294704,0,304881407,645144681,0,820458369,774439384,1,542633842,55712784,0,86065435,830970139,0,628699276,886682922,1,619520442,136499238,0,724115800,212419409,0,343636234,348918646,1,708727937,453319586,0,61297561,29257650,0,770025497,482577235,1,558901890,56382364,0,854971349,160755862,0,413873231,217138225,1,963882251,446323035,0,182261688,968569533,0,146143931,414892560,1,805772163,704720648,0,928798165,24446582,0,734570320,729167229,1,658361894,142943906,0,401545400,346823448,0,59907286,489767353,1,426848606,526571095,0,577275730,661793231,0,4124328,188364318,1,395893771,891189253,0,704599547,11750199,0,100493310,902939451,1,973226635,540433041,0,242147218,818886492,0,215373845,359319525,1,995897841,993925215,0,30341662,35583710,0,26239495,29508917,1,875750042,740489143,0,895840633,357257182,0,771590667,97746317,1,221376283,23666418,0,988893389,390456645,0,210269664,414123062,1,954983035,855895786,0,156778432,798125225,0,111761459,654021003,1,315835739,724850732,0,755282483,710587735,0,71118214,435438459,1,87432835,156780638,0,801395760,995895767,0,888828594,152676397,1,252823126,216442873,0,952904959,898165515,0,205728077,114608380,1,225600356,341311730,0,821612657,432910217,0,47213005,774221946,1,822308182,876859801,0,981502314,483747510,0,803810488,360607303,1,470031544,92150054,0,705360982,197568344,0,175392518,289718397,1,591520945,105652868,0,263587402,122949373,0,855108346,228602240,1,611016010,320605300,0,521304508,551053509,0,132320510,871658808,1,338176968,265111995,0,445153012,727794428,0,783329979,992906422,1,875845292,174336007,0,496400112,883009461,0,372245396,57345460,1,844336460,481087326,0,739740760,253893833,0,584077212,734981158,1,883347555,181750047,0,299004530,324208721,0,182352077,505958767,1,90062660,839496022,0,647468868,478810914,0,737531527,318306928,1,335345054,499919522,0,567581830,49286471,0,902926883,549205992,1,37536740,74182090,0,233133622,880716238,0,270670361,954898327,1,449751686,123980554,0,687007875,775548941,0,136759553,899529494,1,88658012,297134889,0,781563145,169820307,0,870221156,466955195,1,980172015,445431771,0,804778575,956595641,0,784950582,402027404,1,213884510,380468551,0,729839811,936115845,0,943724320,316584388,1,816038095,33662384,0,261872597,972518096,0,77910684,6180472,1,824922092,251333203,0,943662027,557879722,0,768584111,809212924,1,222831910,951950548,0,569524961,29792986,0,792356870,981743533,1,139903827,641403709,0,593507798,542298109,0,733411624,183701810,1,628579691,275703368,0,504422352,534364340,0,133002035,810067707,1,100884094,880490892,0,770320618,274220518,0,871204711,154711402,1,729205627,533172798,0,623700841,486783063,0,352906460,19955853,1,271925651,188646324,0,700602860,810226957,0,972528510,998873280,1,41854496,687299856,0,45084386,314827943,0,86938881,2127791,1,178315721,865997440,0,882468677,155434921,0,60784390,21432353,1,240710761,432480104,0,832671633,49230782,0,73382386,481710885,1,344008549,109160837,0,155934107,513257898,0,499942655,622418734,1,801462520,590710342,0,50234521,944304878,0,851697040,535015212,1,805284049,689311366,0,43359955,472027845,0,848644003,161339203,1,849881942,510480096,0,551795853,104003466,0,401677787,614483561,1,714793047,945314751,0,598360005,736745605,0,313153044,682060348,1,824361198,67159990,0,255833449,865006727,0,80194639,932166716,1,217698461,101649508,0,101056385,225250449,0,318754845,326899956,1,878150764,288754439,0,819620391,272242173,0,697771147,560996611,1,325975762,400191483,0,725443184,595712340,0,51418938,995903822,1,851881349,177939335,0,446263410,790640609,0,298144751,968579943,1,208285213,812505477,0,714740750,221305942,0,923025962,33811411,1,213163004,148148083,0,711128458,915292212,0,924291461,63440287,1,635825839,603875746,0,202263189,259039121,0,838089027,862914866,1,67458230,851634654,0,500807142,601663539,0,568265371,453298185,1,1104478,141301396,0,393788815,753293325,0,394893292,894594720,1,502302912,396885406,0,367669038,531577745,0,869971949,928463150,1,592520140,694884164,0,393483040,769058435,0,986003179,463942591,1,845033381,240217952,0,932110661,937745496,0,777144034,177963440,1,478781078,286298895,0,384800407,892389489,0,863581484,178688376,1,976553711,352250377,0,177101020,790740785,0,153654723,142991154,1,361978780,2334066,0,457289933,804681893,0,819268712,807015958,1,299143845,643783528,0,483955893,530952663,0,783099737,174736183,1,876231641,711836478,0,578444546,618387788,0,454676179,330224258,1,91198076,675887285,0,392210802,251778507,0,483408877,927665791,1,899918750,18486900,0,488708055,407630196,0,388626797,426117095,1,733833118,391037027,0,213652727,367577930,0,947485844,758614956,1,995599090,136113602,0,292431437,40382732,0,288030519,176496333,1,750146347,198047668,0,477514963,385181916,0,227661302,583229583,1,844207679,296306346,0,480385338,99150787,0,324593009,395457132,1,805984497,800643984,0,381822488,928170817,0,187806977,728814793,1,318231189,967749298,0,403017733,828574456,0,721248921,796323746,1,121568050,641645502,0,243915983,84914674,0,365484032,726560175,1,824550591,832746549,0,592729168,710922641,0,417279751,543669182,1,758741523,370168448,0,646664560,688675078,0,405406075,58843518,1,873292656,584203809,0,829046936,982702538,0,702339584,566906339,1,448310400,136664012,0,831965776,938663533,0,280276168,75327537,1,913591891,126769875,0,755902538,883460067,0,669494421,10229934,1,245389413,541551130,0,204911060,819552104,0,450300472,361103226,1,659831427,172687972,0,821286158,485739665,0,481117577,658427636,1,589675087,674334355,0,489245072,75623546,0,78920151,749957900,1,867275036,304372660,0,737748430,251552903,0,605023458,555925562,1,470759475,843461319,0,787141715,365076269,0,257901182,208537580,1,968400060,608591561,0,257203717,92532829,0,225603769,701124389,1,391353853,347021802,0,803319194,567426313,0,194673039,914448114,1,459562169,567013504,0,801161536,772303784,0,260723697,339317280,1,972347197,158751669,0,482149881,522590374,0,454497070,681342042,1,908981273,991220495,0,998729321,385474415,0,907710586,376694902,1,24027908,236489930,0,946237746,304260271,0,970265653,540750200,1,175369659,485507278,0,243420436,448411347,0,418790094,933918624,1,42021226,979122877,0,774451532,778770187,0,816472757,757893056,1,614956434,71644950,0,171793286,753064744,0,786749719,824709693,1,546036355,792591369,0,529361714,630364,0,75398061,793221732,1,341935591,582979715,0,946403287,18206776,0,288338870,601186490,1,737854623,810162517,0,628403007,106446360,0,366257622,916608876,1,995200834,343367157,0,646985243,894767510,0,642186069,238134659,1,811899229,253939062,0,479259955,651655908,0,291159176,905594969,1,889383754,831952840,0,706079171,182411193,0,595462917,14364025,1,892223039,965234958,0,41582426,841582041,0,933805464,806816991,1,373584182,866183483,0,316387542,903108185,0,689971723,769291660,1,232445070,15547208,0,985781866,419601970,0,218226928,435149177,1,759118851,272102587,0,710493360,437929299,0,469612203,710031885,1,678865379,939420307,0,305381259,989842161,0,984246637,929262460,1,255734234,669815238,0,867038437,50561428,0,122772663,720376665,1,70785179,875320602,0,117553276,537150282,0,188338454,412470876,1,917436730,283789142,0,81837435,967125012,0,999274164,250914146,1,63670328,449547758,0,879013340,304752861,0,942683667,754300618,1,683274893,473099317,0,182284568,106157143,0,865559460,579256459,1,180562750,879851537,0,675283148,722961693,0,855845897,602813222,1,666467402,186193520,0,803727971,747162997,0,470195365,933356516,1,284829615,586993965,0,417434253,8161362,0,702263867,595155326,1,106184837,697443192,0,103918809,166352852,0,210103645,863796043,1,613993780,140445778,0,407191318,874389851,0,21185090,14835621,1,369976775,777765033,0,789737912,258266640,0,159714679,36031665,1,802455323,644433205,0,400646759,469601680,0,203102074,114034877,1,529578942,312852628,0,204130021,59746738,0,733708962,372599365,1,125155535,936613135,0,89006750,6222558,0,214162284,942835692,1,184071548,346992884,0,249560430,484402806,0,433631977,831395689,1,644686135,921892007,0,390652061,210025964,0,35338188,131917963,1,632847236,762265128,0,579559522,562060784,0,212406750,324325904,1,280267349,665476244,0,554090366,339019208,0,834357714,4495444,1,807426732,450797263,0,19894482,222875180,0,827321213,673672442,1,207468757,661025501,0,312941081,863897414,0,520409837,524922907,1,601532661,545746096,0,255768350,103774907,0,857301010,649521002,1,940488338,503302778,0,538039297,42924860,0,478527627,546227637,1,58756077,917261659,0,746952075,971465813,0,805708151,888727464,1,665812588,961456476,0,934265358,467086981,0,600077938,428543449,1,708851811,40518946,0,427968390,356062147,0,136820193,396581092,1,170999101,325640553,0,518371451,612719850,0,689370551,938360402,1,479917181,81739488,0,139950553,883615645,0,619867733,965355132,1,51040214,960216442,0,205980332,100693527,0,257020545,60909961,1,945315700,454759028,0,430045386,107313286,0,375361078,562072313,1,66998642,213878428,0,714722366,442327745,0,781721007,656206172,1,159321991,588717957,0,44656147,500280021,0,203978137,88997970,1,834118861,182250752,0,462569378,983917580,0,296688231,166168324,1,686561002,900382524,0,354424106,28057871,0,40985100,928440394,1,142749819,53326600,0,523959445,525874972,0,666709263,579201571,1,46948501,348338213,0,841363052,684457576,0,888311552,32795781,1,1,461401156,0,0,1,0,0,461401156,1,1,718073277,0,0,1,0,0,718073277,1,1,484697441,0,0,1,0,0,484697441,1,1,209629281,0,0,1,0,0,209629281,1,1,461418075,0,0,1,0,0,461418075,1,1,881874272,0,0,1,0,0,881874272,1,1,322795151,0,0,1,0,0,322795151,1,1,266251473,0,0,1,0,0,266251473,1,1,339325974,0,0,1,0,0,339325974,1,1,99411624,0,0,1,0,0,99411624,1,1,804656047,0,0,1,0,0,804656047,1,1,895228597,0,0,1,0,0,895228597,1,1,477456021,0,0,1,0,0,477456021,1,1,354508240,0,0,1,0,0,354508240,1,1,871576636,0,0,1,0,0,871576636,1,1,453948817,0,0,1,0,0,453948817,1,1,865509017,0,0,1,0,0,865509017,1,1,192111678,0,0,1,0,0,192111678,1,1,46394647,0,0,1,0,0,46394647,1,1,26564919,0,0,1,0,0,26564919,1,1,439582580,0,0,1,0,0,439582580,1,1,58907053,0,0,1,0,0,58907053,1,1,745492656,0,0,1,0,0,745492656,1,1,992146528,0,0,1,0,0,992146528,1,1,277232603,0,0,1,0,0,277232603,1,1,612746842,0,0,1,0,0,612746842,1,1,421766296,0,0,1,0,0,421766296,1,1,692749130,0,0,1,0,0,692749130,1,1,307237360,0,0,1,0,0,307237360,1,1,201671535,0,0,1,0,0,201671535,1,1,655773320,0,0,1,0,0,655773320,1,1,550193415,0,0,1,0,0,550193415,1,1,276987553,0,0,1,0,0,276987553,1,1,728035362,0,0,1,0,0,728035362,1,1,474438197,0,0,1,0,0,474438197,1,1,892686004,0,0,1,0,0,892686004,1,1,734961764,0,0,1,0,0,734961764,1,1,118124667,0,0,1,0,0,118124667,1,1,658077727,0,0,1,0,0,658077727,1,1,775038670,0,0,1,0,0,775038670,1,1,519687018,0,0,1,0,0,519687018,1,1,244411899,0,0,1,0,0,244411899,1,1,172062746,0,0,1,0,0,172062746,1,1,670723081,0,0,1,0,0,670723081,1,1,89569833,0,0,1,0,0,89569833,1,1,127184141,0,0,1,0,0,127184141,1,1,398892489,0,0,1,0,0,398892489,1,1,729138999,0,0,1,0,0,729138999,1,1,165249558,0,0,1,0,0,165249558,1,1,317335425,0,0,1,0,0,317335425,1,1,387384817,0,0,1,0,0,387384817,1,1,852307595,0,0,1,0,0,852307595,1,1,613055952,0,0,1,0,0,613055952,1,1,849895929,0,0,1,0,0,849895929,1,1,667238372,0,0,1,0,0,667238372,1,1,741097854,0,0,1,0,0,741097854,1,1,181700551,0,0,1,0,0,181700551,1,1,190909706,0,0,1,0,0,190909706,1,1,154958500,0,0,1,0,0,154958500,1,1,883590633,0,0,1,0,0,883590633,1,1,317217848,0,0,1,0,0,317217848,1,1,428744859,0,0,1,0,0,428744859,1,1,584737726,0,0,1,0,0,584737726,1,1,191076670,0,0,1,0,0,191076670,1,1,182671080,0,0,1,0,0,182671080,1,1,652852777,0,0,1,0,0,652852777,1,1,917363700,0,0,1,0,0,917363700,1,1,520536017,0,0,1,0,0,520536017,1,1,702115075,0,0,1,0,0,702115075,1,1,831269480,0,0,1,0,0,831269480,1,1,744674500,0,0,1,0,0,744674500,1,1,8118746,0,0,1,0,0,8118746,1,1,832367606,0,0,1,0,0,832367606,1,1,823469357,0,0,1,0,0,823469357,1,1,195948237,0,0,1,0,0,195948237,1,1,983871879,0,0,1,0,0,983871879,1,1,799501654,0,0,1,0,0,799501654,1,1,895482979,0,0,1,0,0,895482979,1,1,897340439,0,0,1,0,0,897340439,1,1,548253259,0,0,1,0,0,548253259,1,1,523132065,0,0,1,0,0,523132065,1,1,14441005,0,0,1,0,0,14441005,1,1,935228745,0,0,1,0,0,935228745,1,1,678117804,0,0,1,0,0,678117804,1,1,103458164,0,0,1,0,0,103458164,1,1,627061251,0,0,1,0,0,627061251,1,1,698048621,0,0,1,0,0,698048621,1,1,991136692,0,0,1,0,0,991136692,1,1,641903069,0,0,1,0,0,641903069,1,1,609245440,0,0,1,0,0,609245440,1,1,603979934,0,0,1,0,0,603979934,1,1,429494683,0,0,1,0,0,429494683,1,1,517175601,0,0,1,0,0,517175601,1,1,693575530,0,0,1,0,0,693575530,1,1,120237023,0,0,1,0,0,120237023,1,1,963238328,0,0,1,0,0,963238328,1,1,357149235,0,0,1,0,0,357149235,1,1,679875338,0,0,1,0,0,679875338,1,1,456718757,0,0,1,0,0,456718757,1,1,25915945,0,0,1,0,0,25915945,1,1,661901502,0,0,1,0,0,661901502,1,1,914653617,0,0,1,0,0,914653617,1,1,868470955,0,0,1,0,0,868470955,1,1,662434285,0,0,1,0,0,662434285,1,1,19351578,0,0,1,0,0,19351578,1,1,918486490,0,0,1,0,0,918486490,1,1,417108975,0,0,1,0,0,417108975,1,1,656942729,0,0,1,0,0,656942729,1,1,160356922,0,0,1,0,0,160356922,1,1,927026347,0,0,1,0,0,927026347,1,1,963007907,0,0,1,0,0,963007907,1,1,572635447,0,0,1,0,0,572635447,1,1,316005562,0,0,1,0,0,316005562,1,1,515472702,0,0,1,0,0,515472702,1,1,580474954,0,0,1,0,0,580474954,1,1,942877008,0,0,1,0,0,942877008,1,1,179334223,0,0,1,0,0,179334223,1,1,88605894,0,0,1,0,0,88605894,1,1,747837481,0,0,1,0,0,747837481,1,1,587611116,0,0,1,0,0,587611116,1,1,796794372,0,0,1,0,0,796794372,1,1,129510857,0,0,1,0,0,129510857,1,1,120648691,0,0,1,0,0,120648691,1,1,706227128,0,0,1,0,0,706227128,1,1,347929337,0,0,1,0,0,347929337,1,1,796049130,0,0,1,0,0,796049130,1,1,932195403,0,0,1,0,0,932195403,1,1,397519995,0,0,1,0,0,397519995,1,1,327762954,0,0,1,0,0,327762954,1,1,760433678,0,0,1,0,0,760433678,1,1,743387899,0,0,1,0,0,743387899,1,1,963108853,0,0,1,0,0,963108853,1,1,907351161,0,0,1,0,0,907351161,1,1,638637608,0,0,1,0,0,638637608,1,1,423610520,0,0,1,0,0,423610520,1,1,156826441,0,0,1,0,0,156826441,1,1,817309662,0,0,1,0,0,817309662,1,1,706016044,0,0,1,0,0,706016044,1,1,697431734,0,0,1,0,0,697431734,1,1,810765292,0,0,1,0,0,810765292,1,1,708834760,0,0,1,0,0,708834760,1,1,708631107,0,0,1,0,0,708631107,1,1,269328320,0,0,1,0,0,269328320,1,1,808597006,0,0,1,0,0,808597006,1,1,38026684,0,0,1,0,0,38026684,1,1,20852056,0,0,1,0,0,20852056,1,1,68423694,0,0,1,0,0,68423694,1,1,510032754,0,0,1,0,0,510032754,1,1,381060749,0,0,1,0,0,381060749,1,1,389595635,0,0,1,0,0,389595635,1,1,460746958,0,0,1,0,0,460746958,1,1,64294528,0,0,1,0,0,64294528,1,1,861738260,0,0,1,0,0,861738260,1,1,292723761,0,0,1,0,0,292723761,1,1,550218107,0,0,1,0,0,550218107,1,1,605587008,0,0,1,0,0,605587008,1,1,276312957,0,0,1,0,0,276312957,1,1,940902835,0,0,1,0,0,940902835,1,1,189411684,0,0,1,0,0,189411684,1,1,525636887,0,0,1,0,0,525636887,1,1,462891450,0,0,1,0,0,462891450,1,1,360702173,0,0,1,0,0,360702173,1,1,272272965,0,0,1,0,0,272272965,1,1,434862004,0,0,1,0,0,434862004,1,1,665796332,0,0,1,0,0,665796332,1,1,283234787,0,0,1,0,0,283234787,1,1,889045945,0,0,1,0,0,889045945,1,1,525890193,0,0,1,0,0,525890193,1,1,824069687,0,0,1,0,0,824069687,1,1,245280387,0,0,1,0,0,245280387,1,1,965383725,0,0,1,0,0,965383725,1,1,235461239,0,0,1,0,0,235461239,1,1,306763164,0,0,1,0,0,306763164,1,1,578775617,0,0,1,0,0,578775617,1,1,527835366,0,0,1,0,0,527835366,1,1,34736424,0,0,1,0,0,34736424,1,1,483121813,0,0,1,0,0,483121813,1,1,623103346,0,0,1,0,0,623103346,1,1,684586089,0,0,1,0,0,684586089,1,1,963409203,0,0,1,0,0,963409203,1,1,664229728,0,0,1,0,0,664229728,1,1,612846931,0,0,1,0,0,612846931,1,1,764557106,0,0,1,0,0,764557106,1,1,281221366,0,0,1,0,0,281221366,1,1,159253349,0,0,1,0,0,159253349,1,1,689520926,0,0,1,0,0,689520926,1,1,181282896,0,0,1,0,0,181282896,1,1,151941440,0,0,1,0,0,151941440,1,1,645608096,0,0,1,0,0,645608096,1,1,355513235,0,0,1,0,0,355513235,1,1,546686263,0,0,1,0,0,546686263,1,1,701245302,0,0,1,0,0,701245302,1,1,952040104,0,0,1,0,0,952040104,1,1,646219478,0,0,1,0,0,646219478,1,1,747615562,0,0,1,0,0,747615562,1,1,53208798,0,0,1,0,0,53208798,1,1,591415450,0,0,1,0,0,591415450,1,1,190770971,0,0,1,0,0,190770971,1,1,54956674,0,0,1,0,0,54956674,1,1,319225953,0,0,1,0,0,319225953,1,1,318312490,0,0,1,0,0,318312490,1,1,518197399,0,0,1,0,0,518197399,1,1,273369127,0,0,1,0,0,273369127,1,1,540330710,0,0,1,0,0,540330710,1,1,623882698,0,0,1,0,0,623882698,1,1,886053799,0,0,1,0,0,886053799,1,1,95162100,0,0,1,0,0,95162100,1,1,390786749,0,0,1,0,0,390786749,1,1,977246577,0,0,1,0,0,977246577,1,1,881122780,0,0,1,0,0,881122780,1,1,388571115,0,0,1,0,0,388571115,1,1,507534935,0,0,1,0,0,507534935,1,1,49821627,0,0,1,0,0,49821627,1,1,689117670,0,0,1,0,0,689117670,1,1,332194087,0,0,1,0,0,332194087,1,1,165539726,0,0,1,0,0,165539726,1,1,174821492,0,0,1,0,0,174821492,1,1,326337275,0,0,1,0,0,326337275,1,1,857860411,0,0,1,0,0,857860411,1,1,933333718,0,0,1,0,0,933333718,1,1,740573861,0,0,1,0,0,740573861,1,1,866990811,0,0,1,0,0,866990811,1,1,192544912,0,0,1,0,0,192544912,1,1,945570714,0,0,1,0,0,945570714,1,1,412783007,0,0,1,0,0,412783007,1,1,484955153,0,0,1,0,0,484955153,1,1,809338590,0,0,1,0,0,809338590,1,1,357324294,0,0,1,0,0,357324294,1,1,746831907,0,0,1,0,0,746831907,1,1,420874275,0,0,1,0,0,420874275,1,1,358041028,0,0,1,0,0,358041028,1,1,712181013,0,0,1,0,0,712181013,1,1,261356861,0,0,1,0,0,261356861,1,1,328195876,0,0,1,0,0,328195876,1};
int main(){
	D.init(3,3),T.init(3,3);
	for(int i=0;i<3;i++)
		D[i][i]=T[i][i]=D[i][0]=T[i][1]=1;
	int QT=read();
	while(QT--){
		ll n=read();
		if(n>1500000002) n-=((n-1500000002+500000003-1)/500000003)*500000003;
		int tp=1,p=-9;
		while(tp+B<=n) tp+=B,p+=9;
		Matrix F;
		if(tp==1) F=D*T;
		else{
			F.init(3,3);
			for(int i=0;i<3;i++)
				for(int j=0;j<3;j++)
					F[i][j]=M[p++];
		}
		for(int i=tp+1;i<=n;i++)
			F=F*F*T;
		Matrix S;
		S.init(1,3),S[0][2]=1;
		S=S*F;
		write(add(S[0][0],S[0][1]+1)),putc(' ');
	}
	flush();
}
/*
10
1000000000000000000
100000000000000000
10000000000000000
1000000000000000
100000000000000
10000000000000
1000000000000
100000000000
10000000000
1000000000
*/