#include <bits/stdc++.h>
#define fr first
#define se second
#define Un unsigned
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define pLi pair<LL,int>
#define pLL pair<LL,LL>
#define __ __int128
#define ld long double
#define VE vector<LL>
#define db double
#define Ve vector<int>
 
using namespace std;
 
inline LL read()
{
    LL x = 0,f = 1;char ch = getchar();
    while(!isdigit(ch)) (ch == '-') && (f = -1),ch = getchar();
    while(isdigit(ch)) x = x*10+ch-48,ch = getchar();
    return x*f;
}
 
const int P = 1e9+7,N = 1e6+5;
 
struct squ
{
    LL a[3][3];
    squ(){memset(a,0,sizeof(a));}
    void set(){a[0][0] = a[1][1] = a[2][2] = 1;}
    squ operator*(const squ &b)const
    {
        squ c;
        for (int k = 0;k < 3;k++)
            for (int i = 0;i < 3;i++)
                for (int j = 0;j < 3;j++)
                    c.a[i][j] = (c.a[i][j]+a[i][k]*b.a[k][j])%P;
        return c;
    }
}T;
 
int a[767][3][3] = {{{12367702,246857733,0},{770977592,175213814,0},{783345293,422071546,1}},{{167082569,634065725,0},{809157355,633652180,0},{976239923,267717897,1}},{{527185335,760668470,0},{851320224,166201864,0},{378505551,926870333,1}},{{808817335,601659759,0},{590002915,834515473,0},{398820242,436175224,1}},{{279179014,909284460,0},{416484371,220845028,0},{695663384,130129480,1}},{{115347206,125526137,0},{333944572,720061025,0},{449291777,845587161,1}},{{465692307,253249368,0},{376518057,318915211,0},{842210363,572164578,1}},{{907622766,258560185,0},{777220127,564124230,0},{684842885,822684414,1}},{{65405461,989923928,0},{228691521,101754091,0},{294096981,91678011,1}},{{109134225,103183704,0},{295649056,954870621,0},{404783280,58054317,1}},{{11286962,433748618,0},{475568687,276028778,0},{486855648,709777395,1}},{{649145432,677756358,0},{414841063,443640289,0},{63986487,121396639,1}},{{711983632,504999392,0},{562130748,394818603,0},{274114372,899817994,1}},{{557012665,541791998,0},{613579228,866066819,0},{170591885,407858809,1}},{{261238758,910321492,0},{223196700,885708759,0},{484435457,796030243,1}},{{30957817,901681613,0},{136018520,524237215,0},{166976336,425918820,1}},{{718664862,542228163,0},{661270386,983088248,0},{379935240,525316403,1}},{{287955519,339516260,0},{620185648,286434881,0},{908141166,625951140,1}},{{270803601,169250837,0},{428516182,250438599,0},{699319782,419689435,1}},{{841069791,664076694,0},{784256974,327728822,0},{625326757,991805515,1}},{{312282372,365705932,0},{215846415,165966458,0},{528128786,531672389,1}},{{723957260,622764153,0},{373438049,816052620,0},{97395301,438816765,1}},{{326613227,936031509,0},{639475884,357221982,0},{966089110,293253483,1}},{{226846473,8868982,0},{247749023,542046781,0},{474595495,550915762,1}},{{587550602,348148076,0},{300843101,694518039,0},{888393702,42666107,1}},{{595185969,492855758,0},{221584778,803084379,0},{816770746,295940129,1}},{{99883979,377432529,0},{152807250,767842458,0},{252691228,145274979,1}},{{988169803,834972101,0},{14696850,523634369,0},{2866645,358606462,1}},{{810849697,33666793,0},{48430253,458571119,0},{859279949,492237911,1}},{{623500383,571029258,0},{321170625,880189163,0},{944671007,451218413,1}},{{678064021,651078338,0},{879401347,3307532,0},{557465360,654385869,1}},{{589926984,2129183,0},{946310286,970923647,0},{536237262,973052829,1}},{{638042661,685361412,0},{664278746,155965773,0},{302321399,841327184,1}},{{706242854,41014227,0},{689674631,8223709,0},{395917477,49237935,1}},{{954348513,503002931,0},{644667682,449062058,0},{599016187,952064988,1}},{{633983638,652644561,0},{565406967,450829378,0},{199390597,103473931,1}},{{980991511,164654627,0},{680963535,597755341,0},{661955038,762409967,1}},{{363349367,939257728,0},{260624581,131019357,0},{623973947,70277077,1}},{{747399267,650451801,0},{504970956,465156778,0},{252370215,115608571,1}},{{584996842,554243241,0},{477303566,474078454,0},{62300400,28321687,1}},{{692277005,441922336,0},{574387337,346597060,0},{266664334,788519395,1}},{{558863663,223420895,0},{291352005,892841442,0},{850215667,116262329,1}},{{997968782,89678848,0},{632278336,890511697,0},{630247110,980190544,1}},{{889043999,981362247,0},{139030339,767307469,0},{28074330,748669708,1}},{{730624111,8959573,0},{979159596,317327159,0},{709783699,326286731,1}},{{485770277,933830134,0},{935643754,469396969,0},{421414023,403227095,1}},{{592088250,834989189,0},{854932761,360353240,0},{447021003,195342421,1}},{{700117122,762124500,0},{976016904,531801471,0},{676134018,293925963,1}},{{44620638,909819521,0},{742826163,489386710,0},{787446800,399206223,1}},{{292654256,676144217,0},{891851340,159453410,0},{184505588,835597626,1}},{{633800444,789120898,0},{361677380,631120878,0},{995477823,420241768,1}},{{448486979,622285560,0},{697875001,241246470,0},{146361972,863532029,1}},{{148624185,886573663,0},{268293176,719495726,0},{416917360,606069381,1}},{{699451871,961173686,0},{580809953,20384467,0},{280261816,981558152,1}},{{346875962,204566694,0},{452104899,843779019,0},{798980860,48345705,1}},{{25827511,519317479,0},{773911676,975339587,0},{799739186,494657058,1}},{{854358246,889501921,0},{201129640,762086905,0},{55487878,651588818,1}},{{588100645,901195596,0},{773558873,956897508,0},{361659510,858093096,1}},{{940234895,622281084,0},{715394809,696532070,0},{655629696,318813146,1}},{{389597449,767198029,0},{768923698,84669822,0},{158521139,851867850,1}},{{725698847,483642376,0},{205761452,837305113,0},{931460298,320947481,1}},{{313783237,768338992,0},{352172768,386480609,0},{665956004,154819593,1}},{{216767876,224677365,0},{686857147,349056432,0},{903625022,573733796,1}},{{586779706,929443566,0},{926215233,331216781,0},{512994931,260660339,1}},{{79321818,358873586,0},{831579005,329106434,0},{910900822,687980019,1}},{{242735367,524146993,0},{114206597,417490541,0},{356941963,941637533,1}},{{50474097,257840440,0},{962653181,723472780,0},{13127270,981313219,1}},{{327727739,387810015,0},{571798094,404630222,0},{899525832,792440236,1}},{{886613980,849311890,0},{163482532,463886208,0},{50096504,313198090,1}},{{62426864,695337153,0},{129592652,26297622,0},{192019515,721634774,1}},{{763590422,157463819,0},{89709083,563351673,0},{853299504,720815491,1}},{{190900058,277549271,0},{376415509,611781921,0},{567315566,889331191,1}},{{90288033,290532786,0},{302474394,537714141,0},{392762426,828246926,1}},{{813482024,832469999,0},{442355692,259122931,0},{255837708,91592922,1}},{{841827420,466412344,0},{280050021,80143946,0},{121877433,546556289,1}},{{987895500,740143095,0},{134499784,315183949,0},{122395276,55327036,1}},{{680873036,735982870,0},{292959898,86750133,0},{973832933,822733002,1}},{{816587254,297762368,0},{285556368,777982081,0},{102143614,75744441,1}},{{207605873,349623112,0},{118532146,790450329,0},{326138018,140073433,1}},{{492894206,696361811,0},{746716477,960891717,0},{239610675,657253520,1}},{{908762876,179157393,0},{555054710,249793037,0},{463817578,428950429,1}},{{17326474,379996738,0},{483942263,587220291,0},{501268736,967217028,1}},{{318161896,852460918,0},{549604002,912784829,0},{867765897,765245739,1}},{{98308042,613015892,0},{157967048,818653287,0},{256275089,431669171,1}},{{615433514,240526070,0},{823065229,733995295,0},{438498735,974521364,1}},{{516522239,364690354,0},{184312979,162975743,0},{700835217,527666096,1}},{{477703403,423650153,0},{564144068,704719563,0},{41847463,128369708,1}},{{979720594,347131733,0},{855735109,198022681,0},{835455695,545154413,1}},{{487882812,243701060,0},{178284257,447310000,0},{666167068,691011059,1}},{{153569363,523413358,0},{462760215,471279033,0},{616329577,994692390,1}},{{470360945,805408100,0},{734506942,105863942,0},{204867879,911272041,1}},{{644293951,33575906,0},{220634956,23333931,0},{864928906,56909836,1}},{{347105513,91657554,0},{809007802,201425773,0},{156113307,293083326,1}},{{826542516,408884387,0},{701745491,995627870,0},{528287999,404512249,1}},{{748272746,907729748,0},{819968848,789948415,0},{568241586,697678155,1}},{{282955197,142820440,0},{500449323,482447608,0},{783404519,625268047,1}},{{792763939,110396621,0},{816698625,33142793,0},{609462556,143539413,1}},{{333126601,830341389,0},{219003864,627669172,0},{552130464,458010553,1}},{{508124935,119209108,0},{218247982,898908394,0},{726372916,18117494,1}},{{967070739,69054137,0},{639838877,228028904,0},{606909608,297083040,1}},{{397567342,60638869,0},{531444459,543484445,0},{929011800,604123313,1}},{{586700027,372449834,0},{442818342,662529846,0},{29518361,34979672,1}},{{703840383,857100456,0},{523929893,100494496,0},{227770268,957594951,1}},{{924817215,559915793,0},{265597880,712358126,0},{190415087,272273911,1}},{{453596415,952727893,0},{723266267,542989835,0},{176862674,495717720,1}},{{164316374,650495208,0},{951398100,378143593,0},{115714466,28638793,1}},{{106995651,830367354,0},{897319729,239106214,0},{4315372,69473560,1}},{{944210514,170288335,0},{638541117,28604116,0},{582751623,198892450,1}},{{62843324,869447543,0},{394567425,638738207,0},{457410748,508185742,1}},{{911780632,492874195,0},{110493665,530799697,0},{22274289,23673884,1}},{{806230288,172968080,0},{780514004,686945550,0},{586744284,859913629,1}},{{826104227,904045894,0},{832073489,403337134,0},{658177708,307383020,1}},{{120227505,975145994,0},{589590937,839820472,0},{709818441,814966458,1}},{{642377433,542201411,0},{837461093,410236027,0},{479838518,952437437,1}},{{374198266,575937140,0},{910400999,18049167,0},{284599257,593986306,1}},{{479916447,766713501,0},{308310081,906728083,0},{788226527,673441576,1}},{{730780566,643852721,0},{289543403,79803210,0},{20323961,723655930,1}},{{222850487,369427443,0},{775026709,7702933,0},{997877195,377130375,1}},{{295649065,995054771,0},{237034938,41392072,0},{532684002,36446835,1}},{{623375894,397385380,0},{529069760,274757789,0},{152445646,672143168,1}},{{205947463,641095765,0},{173272341,775862237,0},{379219803,416957994,1}},{{193264761,785392754,0},{940821569,494900033,0},{134086322,280292779,1}},{{501899066,316839668,0},{161812406,199053027,0},{663711471,515892694,1}},{{564014843,339667171,0},{207769727,246593620,0},{771784569,586260790,1}},{{930384373,121214947,0},{230072925,279640417,0},{160457290,400855363,1}},{{362358053,919990046,0},{591160374,514344405,0},{953518426,434334443,1}},{{257178260,118915195,0},{810135489,512876679,0},{67313741,631791873,1}},{{396942843,428923045,0},{645904325,673279001,0},{42847160,102202038,1}},{{239841716,636635575,0},{768602731,80769837,0},{8444439,717405411,1}},{{291840689,932702702,0},{955570428,529984604,0},{247411109,462687298,1}},{{74773613,899051704,0},{66145731,132295932,0},{140919343,31347628,1}},{{24665703,621616254,0},{279581734,902295593,0},{304247436,523911839,1}},{{248884874,678326011,0},{675342920,253412874,0},{924227793,931738884,1}},{{287992480,367198153,0},{140061377,497083096,0},{428053856,864281248,1}},{{789031919,379743284,0},{836475028,191135464,0},{625506939,570878747,1}},{{316258958,661706700,0},{336848272,579947472,0},{653107229,241654164,1}},{{680325176,26297376,0},{7958304,697485155,0},{688283479,723782530,1}},{{815928670,780592922,0},{617776670,86197008,0},{433705332,866789929,1}},{{50657156,623292181,0},{338228684,461314840,0},{388885839,84607013,1}},{{508728393,868147356,0},{427832510,422904110,0},{936560902,291051458,1}},{{739624087,298482581,0},{706577996,295057965,0},{446202075,593540545,1}},{{83305816,802464565,0},{681914386,64256382,0},{765220201,866720946,1}},{{919291610,191655242,0},{202886317,696538583,0},{122177919,888193824,1}},{{635128894,699389576,0},{368466402,965409664,0},{3595288,664799232,1}},{{194220353,633562144,0},{647461683,435762537,0},{841682035,69324673,1}},{{232617772,320148820,0},{227364664,261865967,0},{459982435,582014786,1}},{{800179450,557783270,0},{266322083,465001358,0},{66501525,22784620,1}},{{122868384,89926829,0},{998457264,776730397,0},{121325640,866657225,1}},{{76639983,850456389,0},{957701863,235732197,0},{34341838,86188578,1}},{{182660733,700497068,0},{889170364,605323446,0},{71831089,305820506,1}},{{881171582,241980998,0},{904859851,697411367,0},{786031425,939392364,1}},{{182871572,669209941,0},{333358399,130137434,0},{516229970,799347374,1}},{{53880500,835584669,0},{871020454,504864874,0},{924900953,340449535,1}},{{674638068,611186952,0},{585210355,935871677,0},{259848415,547058621,1}},{{477796785,270407172,0},{314966320,274804924,0},{792763104,545212095,1}},{{335733546,220842267,0},{271256059,895229572,0},{606989604,116071831,1}},{{24954670,963418047,0},{967455873,21567314,0},{992410542,984985360,1}},{{661059035,514115259,0},{216874720,423895645,0},{877933754,938010903,1}},{{193159015,608360556,0},{421515145,585913290,0},{614674159,194273838,1}},{{988328991,277670980,0},{872839977,365052788,0},{861168960,642723767,1}},{{305147172,751586770,0},{866971429,17102300,0},{172118593,768689069,1}},{{799859984,818222080,0},{467056697,316268191,0},{266916673,134490263,1}},{{897166524,460338199,0},{411749402,807000272,0},{308915918,267338463,1}},{{123349226,828332225,0},{629828356,135732339,0},{753177581,964064563,1}},{{316040666,764566915,0},{497788563,435795779,0},{813829228,200362686,1}},{{973399031,577827798,0},{853674109,239663608,0},{827073132,817491405,1}},{{526540225,996591290,0},{202956644,357634216,0},{729496868,354225498,1}},{{979188730,97838142,0},{153892265,601534491,0},{133080987,699372632,1}},{{429389742,118918743,0},{449047551,789174070,0},{878437292,908092812,1}},{{386462958,287686577,0},{356708914,673555644,0},{743171871,961242220,1}},{{543018799,288635795,0},{97511788,57021117,0},{640530586,345656911,1}},{{873555043,597309556,0},{912068469,271079794,0},{785623504,868389349,1}},{{307501372,503283384,0},{489811399,783395527,0},{797312770,286678903,1}},{{775093924,948458353,0},{518267091,62498852,0},{293361007,10957197,1}},{{220008787,568393614,0},{421365701,543287495,0},{641374487,111681101,1}},{{869873458,271007779,0},{636012789,491024989,0},{505886239,762032767,1}},{{732216838,649511431,0},{702846810,981492469,0},{435063640,631003892,1}},{{203764017,58951604,0},{393883778,417188428,0},{597647794,476140031,1}},{{809895529,108328184,0},{99346150,980388628,0},{909241678,88716804,1}},{{73454397,322727116,0},{771204960,896965437,0},{844659356,219692545,1}},{{558326207,147965745,0},{496110725,773799641,0},{54436924,921765385,1}},{{334087641,492852189,0},{670591570,149267432,0},{4679203,642119620,1}},{{656944581,970015669,0},{875831825,963325036,0},{532776398,933340697,1}},{{270183206,304247248,0},{260711660,149566194,0},{530894865,453813441,1}},{{629213801,290963419,0},{18679992,81542955,0},{647893792,372506373,1}},{{978060061,449740773,0},{830718533,129815427,0},{808778586,579556199,1}},{{447488262,145705847,0},{917607463,200726249,0},{365095717,346432095,1}},{{457852,897119538,0},{410515661,842028784,0},{410973512,739148314,1}},{{283088817,995206444,0},{773078768,396717123,0},{56167577,391923559,1}},{{818181076,538127417,0},{242649712,666799141,0},{60830780,204926550,1}},{{712553264,764561152,0},{498228754,293329019,0},{210782010,57890163,1}},{{390535041,712382204,0},{356098930,559651241,0},{746633970,272033437,1}},{{631944432,683549434,0},{176642787,7019078,0},{808587218,690568511,1}},{{57936297,720360081,0},{149047643,753989882,0},{206983939,474349955,1}},{{445261182,611612160,0},{221844666,65204475,0},{667105847,676816634,1}},{{847712467,299277249,0},{622213806,759676274,0},{469926265,58953515,1}},{{585722596,80573396,0},{918423139,662722854,0},{504145727,743296249,1}},{{246262050,594061716,0},{338635051,294316512,0},{584897100,888378227,1}},{{691761454,927025089,0},{977933134,720637789,0},{669694580,647662870,1}},{{482998543,519917575,0},{426184541,621995126,0},{909183083,141912693,1}},{{883847504,664996145,0},{668713866,640001883,0},{552561362,304998020,1}},{{548184222,690387132,0},{68620679,385925416,0},{616804900,76312540,1}},{{515932798,793312407,0},{975338676,769913424,0},{491271466,563225823,1}},{{966515051,415548156,0},{970955785,778563842,0},{937470828,194111990,1}},{{211770538,473140077,0},{599164100,565570789,0},{810934637,38710858,1}},{{520434711,608514711,0},{150352315,343271462,0},{670787025,951786172,1}},{{702720972,182620881,0},{446599994,676714026,0},{149320958,859334906,1}},{{956967422,44726075,0},{69430219,999831108,0},{26397633,44557175,1}},{{760955453,19746760,0},{579567149,213579708,0},{340522594,233326467,1}},{{812231918,163644319,0},{919152146,860616743,0},{731384056,24261054,1}},{{753410056,490283487,0},{768101207,722273860,0},{521511255,212557339,1}},{{293991343,745795387,0},{531721171,327855509,0},{825712513,73650888,1}},{{987005441,588338197,0},{61938471,324505792,0},{48943904,912843988,1}},{{146195532,343594963,0},{25187013,655227982,0},{171382544,998822944,1}},{{463361966,765481657,0},{946899790,984854690,0},{410261748,750336339,1}},{{119348887,367052872,0},{696150843,160569588,0},{815499729,527622459,1}},{{990797937,596928867,0},{215329320,594029052,0},{206127249,190957911,1}},{{108978706,175033721,0},{138482061,175230695,0},{247460766,350264415,1}},{{387228889,712223262,0},{693341496,728076635,0},{80570377,440299889,1}},{{506675667,989007005,0},{155500642,518980498,0},{662176308,507987495,1}},{{389367238,621700169,0},{384005763,239867728,0},{773373000,861567896,1}},{{267786092,386531833,0},{639099545,531523078,0},{906885636,918054910,1}},{{67383836,178530523,0},{516597412,448502972,0},{583981247,627033494,1}},{{477875894,282886460,0},{83607211,87507329,0},{561483104,370393788,1}},{{154839054,400921399,0},{508342877,140234247,0},{663181930,541155645,1}},{{677784195,59119170,0},{617327336,271361643,0},{295111523,330480812,1}},{{142404785,888522940,0},{772126424,404106631,0},{914531208,292629563,1}},{{71980783,909242092,0},{824738843,900369494,0},{896719625,809611578,1}},{{660310740,136722616,0},{578194086,609607318,0},{238504818,746329933,1}},{{237639607,410575216,0},{408292341,897136631,0},{645931947,307711839,1}},{{538798081,662736986,0},{900571173,692320293,0},{439369246,355057271,1}},{{559625539,400079723,0},{532342135,65489977,0},{91967666,465569699,1}},{{481842926,193198012,0},{6889955,957081200,0},{488732880,150279204,1}},{{930028836,560010737,0},{609001149,650455077,0},{539029977,210465806,1}},{{505452040,163444319,0},{134523398,270210596,0},{639975437,433654914,1}},{{179720440,848564616,0},{918525600,667198764,0},{98246032,515763372,1}},{{652703320,547777386,0},{731888244,158071652,0},{384591556,705849037,1}},{{278098358,326429735,0},{261205794,100158645,0},{539304151,426588379,1}},{{262659779,795046174,0},{712131633,627434246,0},{974791411,422480412,1}},{{78400065,778620165,0},{560169836,65408034,0},{638569900,844028198,1}},{{562612759,403890786,0},{343292639,134413129,0},{905905397,538303914,1}},{{630818754,848680780,0},{948588017,227417057,0},{579406763,76097829,1}},{{558342622,500500902,0},{880514821,222113122,0},{438857435,722614023,1}},{{142679375,376235617,0},{430919769,435613644,0},{573599143,811849260,1}},{{23729443,545293592,0},{407984644,478020640,0},{431714086,23314224,1}},{{487782756,618919374,0},{107529298,660446530,0},{595312053,279365896,1}},{{334047069,925952313,0},{381176643,626767859,0},{715223711,552720164,1}},{{299567937,751362598,0},{971368802,969629866,0},{270936731,720992456,1}},{{688464804,822440214,0},{88310662,208127504,0},{776775465,30567710,1}},{{528452240,884414485,0},{402964001,606631663,0},{931416240,491046140,1}},{{310133921,921583507,0},{87898231,43863862,0},{398032151,965447368,1}},{{619139429,187048522,0},{701171054,927113835,0},{320310475,114162349,1}},{{467079378,23179588,0},{880940969,581056018,0},{348020339,604235605,1}},{{673665158,283399694,0},{741850235,439071372,0},{415515385,722471065,1}},{{871967045,108483269,0},{979088483,215907679,0},{851055520,324390947,1}},{{433019981,126124273,0},{475306541,680968132,0},{908326521,807092404,1}},{{640868620,199416539,0},{596776116,595297792,0},{237644728,794714330,1}},{{813641429,91336427,0},{775337059,823373877,0},{588978480,914710303,1}},{{717016920,47337251,0},{135587616,870593958,0},{852604535,917931208,1}},{{955734073,520350199,0},{188502983,960952914,0},{144237048,481303105,1}},{{941998134,365186212,0},{724906671,945371540,0},{666904797,310557744,1}},{{3443407,709327470,0},{404005710,562368360,0},{407449116,271695822,1}},{{615102290,525555823,0},{232112048,991511488,0},{847214337,517067303,1}},{{955566249,127114946,0},{773704742,904173162,0},{729270983,31288100,1}},{{123413404,593329619,0},{374380101,441538275,0},{497793504,34867886,1}},{{358724215,280433573,0},{333720704,757952057,0},{692444918,38385622,1}},{{503312954,754291326,0},{740150870,986317872,0},{243463816,740609190,1}},{{77831115,967686208,0},{117538319,463816761,0},{195369433,431502961,1}},{{438004421,123717612,0},{103364976,545111280,0},{541369396,668828891,1}},{{591347449,670542808,0},{3592980,705975613,0},{594940428,376518413,1}},{{399879740,318883052,0},{263988755,391204109,0},{663868494,710087160,1}},{{269174900,542441412,0},{881466532,714005627,0},{150641424,256447031,1}},{{75887127,56298752,0},{42100902,368190766,0},{117988028,424489517,1}},{{259629681,452451571,0},{295615398,155753273,0},{555245078,608204843,1}},{{575688472,205489108,0},{983354036,150649770,0},{559042500,356138877,1}},{{682294747,31739611,0},{136757352,901096368,0},{819052098,932835978,1}},{{248225424,888977354,0},{203902831,627042321,0},{452128254,516019667,1}},{{653547265,344902916,0},{917603304,663448643,0},{571150561,8351551,1}},{{851482460,188233508,0},{230054791,42562560,0},{81537243,230796067,1}},{{629582663,111307624,0},{777488742,934407395,0},{407071397,45715011,1}},{{400423973,267952528,0},{609847657,842128637,0},{10271622,110081157,1}},{{692503213,809121159,0},{264736861,346566418,0},{957240073,155687569,1}},{{306469637,355671588,0},{723118592,954916076,0},{29588221,310587656,1}},{{881949598,441473018,0},{963947722,745383945,0},{845897312,186856955,1}},{{880657331,976348631,0},{130201318,672750625,0},{10858641,649099248,1}},{{32194144,110126542,0},{87837239,720878135,0},{120031382,831004676,1}},{{818208240,300934849,0},{15286298,9072398,0},{833494537,310007246,1}},{{135290850,245842857,0},{946473921,167631716,0},{81764763,413474572,1}},{{636707647,727741017,0},{960661491,802850576,0},{597369130,530591585,1}},{{762708021,438631972,0},{282200853,658940999,0},{44908866,97572963,1}},{{682641626,789152513,0},{436828159,337246886,0},{119469777,126399391,1}},{{45425739,803723873,0},{536407423,939584864,0},{581833161,743308729,1}},{{165823969,459231313,0},{988516699,255870662,0},{154340660,715101974,1}},{{957342478,189091359,0},{65468100,870643875,0},{22810570,59735226,1}},{{929384838,886492032,0},{916608749,35277778,0},{845993579,921769809,1}},{{658233379,58424794,0},{223457222,472790989,0},{881690600,531215782,1}},{{102713404,731347583,0},{154394379,677456290,0},{257107782,408803865,1}},{{579887737,601093601,0},{702594819,766780926,0},{282482548,367874519,1}},{{573759162,63407017,0},{617736356,519830417,0},{191495510,583237433,1}},{{878406736,639351605,0},{133499259,347500121,0},{11905987,986851725,1}},{{746581712,952431901,0},{540358442,85252624,0},{286940146,37684517,1}},{{729818100,593728742,0},{638008900,963769028,0},{367826992,557497762,1}},{{365651391,629530429,0},{254023279,526840099,0},{619674669,156370520,1}},{{201991555,868871642,0},{267470486,911946002,0},{469462040,780817636,1}},{{228616746,832156461,0},{288809826,953993272,0},{517426571,786149725,1}},{{947130213,538453970,0},{900669974,963175298,0},{847800179,501629260,1}},{{424641965,215819246,0},{786184902,183292490,0},{210826859,399111735,1}},{{366377982,363823596,0},{205093837,942289895,0},{571471818,306113483,1}},{{518259872,733556760,0},{8789502,951665845,0},{527049373,685222597,1}},{{563830750,348454450,0},{621272515,498262608,0},{185103257,846717057,1}},{{606205792,253401380,0},{268856838,833622853,0},{875062629,87024225,1}},{{659814893,325633028,0},{610202668,649449004,0},{270017553,975082031,1}},{{392089148,355921854,0},{597025660,546724524,0},{989114807,902646377,1}},{{288400031,909520989,0},{991642627,621898327,0},{280042650,531419308,1}},{{840598771,346052585,0},{93561758,177358005,0},{934160528,523410589,1}},{{855509929,621352012,0},{969519087,412776151,0},{825029008,34128155,1}},{{821218874,466931374,0},{37965848,701544393,0},{859184721,168475759,1}},{{933004240,917072975,0},{914555111,889073064,0},{847559343,806146031,1}},{{107356499,323381276,0},{372928345,632946867,0},{480284843,956328142,1}},{{372814171,836166561,0},{490593753,897891708,0},{863407923,734058261,1}},{{676246524,987418458,0},{560023793,427169195,0},{236270309,414587645,1}},{{997281871,874904746,0},{823967140,377130033,0},{821249003,252034771,1}},{{933620053,645265818,0},{432365881,203965751,0},{365985926,849231568,1}},{{907026884,355801625,0},{906102145,581119546,0},{813129021,936921170,1}},{{719865612,293126219,0},{288030818,699989790,0},{7896422,993116008,1}},{{473703025,77714810,0},{120943539,299471419,0},{594646563,377186228,1}},{{816033365,554536373,0},{227981783,319161548,0},{44015140,873697920,1}},{{741984773,111232380,0},{85164770,242018785,0},{827149542,353251164,1}},{{902438886,353187605,0},{987645451,506079777,0},{890084329,859267381,1}},{{919830686,268965495,0},{10299290,555951231,0},{930129975,824916725,1}},{{872640362,778064292,0},{501164146,26574472,0},{373804500,804638763,1}},{{287432890,57016987,0},{845094583,58034836,0},{132527465,115051822,1}},{{576008317,5804559,0},{698835101,28767900,0},{274843410,34572458,1}},{{694308332,355263589,0},{269900457,555597822,0},{964208788,910861410,1}},{{49006469,623313480,0},{956761709,159716307,0},{5768170,783029786,1}},{{391608788,839209272,0},{247995715,545995920,0},{639604502,385205184,1}},{{473536683,123482964,0},{616785631,130369040,0},{90322306,253852003,1}},{{348514881,37994492,0},{69263245,650315277,0},{417778125,688309768,1}},{{531931637,449714566,0},{719533943,341829027,0},{251465572,791543592,1}},{{767549806,668393118,0},{250215326,789512815,0},{17765124,457905925,1}},{{838465747,302840194,0},{164839030,299440997,0},{3304769,602281190,1}},{{576702904,273291220,0},{929829942,790469239,0},{506532838,63760451,1}},{{475544883,436610295,0},{756007894,976798391,0},{231552769,413408678,1}},{{179581589,742463710,0},{623885048,743199143,0},{803466636,485662845,1}},{{159407076,34987314,0},{792375406,526796066,0},{951782481,561783379,1}},{{745711448,263942562,0},{122178970,204531633,0},{867890417,468474194,1}},{{438935510,755784802,0},{780203797,61550849,0},{219139299,817335650,1}},{{703675829,816502988,0},{392203640,449291911,0},{95879461,265794891,1}},{{497241066,89806794,0},{215227173,710661898,0},{712468238,800468691,1}},{{47632858,554567409,0},{959413395,133970482,0},{7046245,688537890,1}},{{617733853,4111389,0},{950063198,328429235,0},{567797043,332540623,1}},{{258500874,669038642,0},{245714696,636809319,0},{504215569,305847953,1}},{{194995420,780628705,0},{804404779,248986714,0},{999400198,29615411,1}},{{33935545,298127963,0},{63339214,278592602,0},{97274758,576720564,1}},{{862302054,26178701,0},{725952047,488853796,0},{588254093,515032496,1}},{{527440478,683914128,0},{437033764,909346582,0},{964474241,593260702,1}},{{930923896,330202657,0},{726016872,351522275,0},{656940760,681724931,1}},{{205483824,138146205,0},{996086294,916261850,0},{201570110,54408047,1}},{{541841290,777865134,0},{80514100,699214876,0},{622355389,477080002,1}},{{159117768,279157160,0},{762189965,869276915,0},{921307732,148434067,1}},{{543135156,172327313,0},{360712809,479502764,0},{903847964,651830076,1}},{{705008209,87149073,0},{143481745,930507827,0},{848489953,17656892,1}},{{287632648,509516167,0},{521455260,777300392,0},{809087907,286816551,1}},{{374338976,376538899,0},{294107302,334238759,0},{668446277,710777657,1}},{{831228724,879796876,0},{562931958,613610878,0},{394160674,493407746,1}},{{497252254,686506658,0},{637599979,668541784,0},{134852225,355048434,1}},{{883364188,962771876,0},{441575240,371506673,0},{324939420,334278541,1}},{{63651812,763961994,0},{878746869,336174133,0},{942398680,100136119,1}},{{345428694,195217709,0},{144012597,833221322,0},{489441290,28439023,1}},{{165150161,587552280,0},{39811922,21291335,0},{204962082,608843614,1}},{{493766569,540593304,0},{483756332,108348614,0},{977522900,648941917,1}},{{67819790,848775137,0},{385104451,19767193,0},{452924240,868542329,1}},{{533085868,158327389,0},{218537687,586779583,0},{751623554,745106971,1}},{{750910764,262973492,0},{64728482,13817956,0},{815639245,276791447,1}},{{821420214,395780042,0},{857143291,188383413,0},{678563497,584163454,1}},{{356011176,392603131,0},{823342628,551147579,0},{179353796,943750709,1}},{{766979632,240569970,0},{670516543,680718502,0},{437496167,921288471,1}},{{484536921,46820846,0},{341054886,761563899,0},{825591806,808384744,1}},{{132906383,486844692,0},{179877957,511513901,0},{312784339,998358592,1}},{{14910753,685172568,0},{968247029,6988693,0},{983157781,692161260,1}},{{171844988,539986308,0},{346345198,375352541,0},{518190185,915338848,1}},{{840042881,257053011,0},{557918096,187502317,0},{397960969,444555327,1}},{{763186332,665671741,0},{508292688,45580923,0},{271479012,711252663,1}},{{561652005,998965387,0},{957342617,499358750,0},{518994614,498324129,1}},{{767546226,202958860,0},{929564828,28870959,0},{697111046,231829818,1}},{{451039543,824476909,0},{861518384,15240700,0},{312557919,839717608,1}},{{571981369,893162614,0},{639568567,950817335,0},{211549928,843979941,1}},{{679483778,766674894,0},{361133286,290054036,0},{40617056,56728922,1}},{{378083705,225135276,0},{462720642,758337487,0},{840804346,983472762,1}},{{790397140,543448593,0},{379100167,567065764,0},{169497299,110514349,1}},{{208197945,929045692,0},{620076779,764909977,0},{828274723,693955661,1}},{{108592231,131371787,0},{771055609,730090692,0},{879647839,861462478,1}},{{561688688,376196915,0},{371382684,86373070,0},{933071371,462569984,1}},{{968401548,801776101,0},{462662994,183897836,0},{431064534,985673936,1}},{{625664976,638690656,0},{137567003,42343198,0},{763231978,681033853,1}},{{315175307,50925772,0},{221988708,462377550,0},{537164014,513303321,1}},{{102110484,872512148,0},{319293134,461804623,0},{421403617,334316763,1}},{{526493399,776863422,0},{152144428,782279806,0},{678637826,559143220,1}},{{126187375,440814131,0},{388290578,479762979,0},{514477952,920577109,1}},{{994759789,374727883,0},{377556999,907148534,0},{372316780,281876409,1}},{{432877168,111320302,0},{167446543,853008069,0},{600323710,964328370,1}},{{894439910,481219829,0},{580201359,246864915,0},{474641261,728084743,1}},{{353534857,652580611,0},{430169816,349115313,0},{783704672,1695916,1}},{{403355289,373479778,0},{986885882,714377199,0},{390241163,87856969,1}},{{271466614,98141445,0},{211173081,495591322,0},{482639694,593732766,1}},{{526412681,645403340,0},{827709959,573185091,0},{354122632,218588423,1}},{{559472455,434769379,0},{714093781,176007527,0},{273566228,610776905,1}},{{163307039,83373711,0},{505310248,988102377,0},{668617286,71476080,1}},{{515954342,508310623,0},{912907165,996475952,0},{428861499,504786567,1}},{{669728933,707392163,0},{612965444,658019401,0},{282694369,365411556,1}},{{722101484,893233017,0},{9455801,158246799,0},{731557284,51479808,1}},{{109474272,317514657,0},{374926208,834969509,0},{484400479,152484158,1}},{{543412141,229702233,0},{354907843,748862601,0},{898319983,978564833,1}},{{338553909,840973386,0},{840627013,869354752,0},{179180914,710328130,1}},{{650109566,417769656,0},{758574487,695725244,0},{408684045,113494892,1}},{{736289632,565959899,0},{337506043,230611271,0},{73795667,796571169,1}},{{378128554,7341047,0},{380859768,838047715,0},{758988321,845388761,1}},{{160798626,534208189,0},{229035746,801601216,0},{389834371,335809397,1}},{{19658322,758863763,0},{648960486,365423155,0},{668618807,124286910,1}},{{503026637,424930306,0},{96851397,294858126,0},{599878033,719788431,1}},{{672599607,428467784,0},{265092095,350136903,0},{937691701,778604686,1}},{{625721451,50812320,0},{920416018,717592124,0},{546137461,768404443,1}},{{552885439,881617112,0},{763983589,793211052,0},{316869020,674828156,1}},{{247593308,992071006,0},{33873545,892109823,0},{281466852,884180821,1}},{{254155444,111634310,0},{316070388,392669382,0},{570225831,504303691,1}},{{858161776,88402213,0},{600367134,836336382,0},{458528902,924738594,1}},{{330876079,292353540,0},{881480609,252600797,0},{212356680,544954336,1}},{{729269292,338801688,0},{18316010,420620851,0},{747585301,759422538,1}},{{770259767,531322639,0},{957183473,232705333,0},{727443232,764027971,1}},{{298379321,826881138,0},{600389549,522575330,0},{898768869,349456460,1}},{{504713514,970570246,0},{25549211,450191921,0},{530262724,420762159,1}},{{438443633,223880991,0},{363982193,844334777,0},{802425825,68215760,1}},{{817465311,41366023,0},{14257038,65471696,0},{831722348,106837718,1}},{{609086392,290281154,0},{228244064,88002477,0},{837330455,378283630,1}},{{508296608,220694836,0},{479125115,71035680,0},{987421722,291730515,1}},{{894892915,455443784,0},{74712648,346770819,0},{969605562,802214602,1}},{{637300612,348755574,0},{621724953,982227528,0},{259025557,330983094,1}},{{80545630,877478595,0},{489241815,122231082,0},{569787444,999709676,1}},{{304430865,668525389,0},{984606946,7624447,0},{289037803,676149835,1}},{{936114599,428081505,0},{286002026,627714617,0},{222116617,55796114,1}},{{671629796,73901974,0},{53624541,491136919,0},{725254336,565038892,1}},{{795014769,217880241,0},{643315736,868015655,0},{438330497,85895888,1}},{{432412809,73277892,0},{299504481,909674111,0},{731917289,982952002,1}},{{213324096,779207048,0},{924247895,94894962,0},{137571983,874102009,1}},{{345906511,223425883,0},{599799878,928250650,0},{945706388,151676525,1}},{{946416212,257907621,0},{133129428,542452870,0},{79545632,800360490,1}},{{756486279,47034318,0},{283347201,503519110,0},{39833472,550553427,1}},{{809878009,692768113,0},{386010149,838190510,0},{195888150,530958615,1}},{{733002797,885688630,0},{663721878,556880678,0},{396724667,442569300,1}},{{154529406,679056552,0},{159303450,200061650,0},{313832855,879118201,1}},{{749861811,106181148,0},{947047984,748007261,0},{696909787,854188408,1}},{{588984344,317908014,0},{188329008,769542507,0},{777313351,87450513,1}},{{488111239,661834711,0},{252906833,584340828,0},{741018071,246175531,1}},{{1494195,172797799,0},{814918923,991190094,0},{816413117,163987885,1}},{{317607751,879395651,0},{278027042,387073292,0},{595634792,266468935,1}},{{752839641,256113646,0},{852077468,110517160,0},{604917101,366630805,1}},{{852911760,208214620,0},{685922323,788988273,0},{538834075,997202892,1}},{{792944685,16545347,0},{232813967,796432411,0},{25758644,812977757,1}},{{559382251,81593737,0},{714530996,570334762,0},{273913239,651928498,1}},{{766329083,649064831,0},{408895485,411967146,0},{175224560,61031969,1}},{{285540952,772740798,0},{213425974,450454400,0},{498966925,223195190,1}},{{761525495,298469584,0},{371558239,669604305,0},{133083726,968073888,1}},{{738261085,40371007,0},{246971270,171567416,0},{985232354,211938422,1}},{{854589889,741334293,0},{295161994,211814453,0},{149751875,953148745,1}},{{19725627,450180765,0},{337632226,187216850,0},{357357852,637397614,1}},{{355295193,984864016,0},{548897118,471626472,0},{904192310,456490480,1}},{{822955360,923210484,0},{291381363,488584692,0},{114336715,411795168,1}},{{916546,240360574,0},{695653528,583326018,0},{696570073,823686591,1}},{{959733307,182945124,0},{94003076,945373497,0},{53736375,128318613,1}},{{800650918,607437196,0},{372258744,313420762,0},{172909654,920857957,1}},{{107739468,293035644,0},{264701957,404187342,0},{372441424,697222985,1}},{{28739594,726296249,0},{404397470,981675827,0},{433137063,707972068,1}},{{55484207,473064066,0},{949850583,691840545,0},{5334782,164904603,1}},{{703645624,647551661,0},{990105799,647773882,0},{693751415,295325535,1}},{{185017564,414423506,0},{83719073,588106669,0},{268736636,2530167,1}},{{461360816,661106829,0},{936035039,456466935,0},{397395847,117573756,1}},{{286632027,91598372,0},{765540866,82842971,0},{52172885,174441342,1}},{{372508622,297689168,0},{262457374,558738292,0},{634965995,856427459,1}},{{823307477,439720214,0},{725717609,880309043,0},{549025078,320029249,1}},{{696199692,844248166,0},{304839439,318505513,0},{1039123,162753671,1}},{{888392380,768316778,0},{475248468,461098391,0},{363640840,229415161,1}},{{776782247,892961648,0},{664094663,443284957,0},{440876902,336246597,1}},{{231964125,869371032,0},{963008790,686764097,0},{194972907,556135121,1}},{{65850330,376222588,0},{44611264,26842327,0},{110461593,403064914,1}},{{430247345,508377428,0},{497963259,168208872,0},{928210603,676586299,1}},{{852632078,474825743,0},{910717626,770790817,0},{763349696,245616552,1}},{{413697057,35431506,0},{444886997,750520624,0},{858584053,785952129,1}},{{546727616,291393042,0},{936265958,982901556,0},{482993566,274294590,1}},{{350323606,461493459,0},{720955430,650959169,0},{71279028,112452620,1}},{{525576495,595143022,0},{834126993,909758832,0},{359703480,504901846,1}},{{517224798,474891529,0},{266545771,224198691,0},{783770568,699090219,1}},{{921615243,255547802,0},{221631636,616341797,0},{143246871,871889598,1}},{{925694499,38226426,0},{438970273,593623837,0},{364664764,631850262,1}},{{206660421,475484516,0},{599206623,966540272,0},{805867043,442024780,1}},{{719588053,367819309,0},{54173483,705688697,0},{773761535,73507998,1}},{{929725807,11015840,0},{786755839,467665898,0},{716481638,478681737,1}},{{598441216,59690887,0},{262110620,621338753,0},{860551835,681029639,1}},{{214632669,159589307,0},{475113178,370873000,0},{689745846,530462306,1}},{{732596456,521776693,0},{235400947,402303154,0},{967997402,924079846,1}},{{667631060,735025992,0},{7653971,505258175,0},{675285030,240284159,1}},{{516849064,270703564,0},{158421262,530518571,0},{675270325,801222134,1}},{{141811907,692477613,0},{721247237,122937693,0},{863059143,815415305,1}},{{387017293,394556046,0},{648799999,750562522,0},{35817284,145118560,1}},{{845828249,203810511,0},{134238546,582934620,0},{980066794,786745130,1}},{{566424308,619535758,0},{980780045,443719709,0},{547204345,63255459,1}},{{902886252,666463645,0},{855024170,71215217,0},{757910414,737678861,1}},{{788902839,913680468,0},{677527430,144205100,0},{466430261,57885560,1}},{{374126229,80545332,0},{863127827,909947766,0},{237254048,990493097,1}},{{340746926,667051351,0},{304078638,314045752,0},{644825563,981097102,1}},{{664713990,658318656,0},{927360196,111613407,0},{592074178,769932062,1}},{{814463402,188826496,0},{338503499,637239329,0},{152966893,826065824,1}},{{354533569,102884134,0},{960486626,130969269,0},{315020187,233853402,1}},{{14148380,196835030,0},{829613682,695653489,0},{843762061,892488518,1}},{{293692436,105101250,0},{807492022,10871391,0},{101184450,115972640,1}},{{153778007,19641178,0},{109659874,914202296,0},{263437880,933843473,1}},{{164831045,900199578,0},{225715150,841896527,0},{390546194,742096097,1}},{{894505645,951399573,0},{795004630,846178447,0},{689510267,797578012,1}},{{667740713,752460545,0},{234438950,490320073,0},{902179662,242780610,1}},{{734653746,664089362,0},{646409232,213556542,0},{381062970,877645903,1}},{{432309549,851071658,0},{365621029,682850647,0},{797930577,533922297,1}},{{344351204,497044753,0},{35673752,7990668,0},{380024955,505035420,1}},{{627178552,753001559,0},{817878000,95776257,0},{445056544,848777815,1}},{{697874043,713119993,0},{209146502,150173013,0},{907020544,863293005,1}},{{567503410,771427436,0},{179822443,482838209,0},{747325852,254265637,1}},{{384533886,227959747,0},{112956312,669399713,0},{497490197,897359459,1}},{{540588922,792002615,0},{601530708,77034608,0},{142119622,869037222,1}},{{39509191,804726116,0},{385342736,226870000,0},{424851926,31596108,1}},{{755562047,913742932,0},{323725483,195814682,0},{79287522,109557606,1}},{{198920477,768304239,0},{221650258,890675377,0},{420570734,658979608,1}},{{410090259,789249670,0},{109194783,222327562,0},{519285041,11577224,1}},{{229412568,697685580,0},{757537991,67232716,0},{986950558,764918295,1}},{{140040503,114846902,0},{790226402,365757390,0},{930266904,480604291,1}},{{487565772,531318208,0},{53658027,754421535,0},{541223798,285739735,1}},{{846134652,266993833,0},{924665145,298069723,0},{770799789,565063555,1}},{{138594996,447095310,0},{158427203,817338360,0},{297022198,264433662,1}},{{688107395,888255918,0},{892645636,631066840,0},{580753023,519322750,1}},{{644374419,956060967,0},{746534877,778366169,0},{390909288,734427128,1}},{{113269147,348427909,0},{524401596,254853729,0},{637670742,603281637,1}},{{732130754,992240584,0},{589502274,952016853,0},{321633020,944257429,1}},{{637365132,417274594,0},{361360738,997067470,0},{998725869,414342056,1}},{{852769031,94794987,0},{496788261,812670918,0},{349557284,907465904,1}},{{986446831,91633828,0},{929734433,524721772,0},{916181256,616355599,1}},{{976096504,299076066,0},{85193054,135323252,0},{61289550,434399317,1}},{{358852553,160839457,0},{138604338,655840389,0},{497456890,816679845,1}},{{742884550,320750988,0},{810807585,483507029,0},{553692127,804258016,1}},{{772823148,383133693,0},{509407528,128141855,0},{282230668,511275547,1}},{{168288509,576172665,0},{617143595,479995422,0},{785432103,56168079,1}},{{37173628,930378342,0},{915362191,969042970,0},{952535818,899421304,1}},{{908436638,955010470,0},{961208457,550486303,0},{869645087,505496765,1}},{{333042933,792883111,0},{712955285,389118040,0},{45998210,182001143,1}},{{361967830,830106445,0},{693000295,248828908,0},{54968117,78935345,1}},{{965382532,417570230,0},{654762709,414120759,0},{620145233,831690988,1}},{{251249180,393799376,0},{231955700,114698828,0},{483204879,508498203,1}},{{443457812,622573227,0},{342321395,85391817,0},{785779206,707965043,1}},{{17878817,664178984,0},{503389082,594876315,0},{521267898,259055291,1}},{{239799053,562950812,0},{910698623,950935358,0},{150497668,513886162,1}},{{561089592,159315317,0},{945899815,342209016,0},{506989399,501524332,1}},{{653816769,362204477,0},{858936812,253791846,0},{512753573,615996322,1}},{{597891723,97097775,0},{313844175,949202762,0},{911735897,46300529,1}},{{591998778,434585742,0},{396656698,128744316,0},{988655475,563330057,1}},{{975299058,70190338,0},{364202047,37501693,0},{339501097,107692030,1}},{{436807742,153849038,0},{168538330,53973670,0},{605346071,207822707,1}},{{678759949,982199315,0},{370548902,681189042,0},{49308843,663388349,1}},{{714367000,869604016,0},{318119118,557275933,0},{32486110,426879941,1}},{{814297558,391066776,0},{224629092,410828138,0},{38926642,801894913,1}},{{415952646,212782717,0},{820370753,479506506,0},{236323391,692289222,1}},{{374428347,388770029,0},{765985745,817959310,0},{140414084,206729331,1}},{{358240627,528010788,0},{511807735,838692538,0},{870048361,366703318,1}},{{323860341,516993040,0},{631726176,333178392,0},{955586516,850171431,1}},{{640108644,240150622,0},{992704670,811104602,0},{632813306,51255216,1}},{{870441877,75511147,0},{648664092,645914898,0},{519105961,721426044,1}},{{120355607,2530093,0},{345055973,425268721,0},{465411579,427798813,1}},{{106786907,932848059,0},{537686434,131878114,0},{644473340,64726165,1}},{{53103441,934526579,0},{664990171,500181060,0},{718093611,434707631,1}},{{655075505,95624797,0},{476579719,65388511,0},{131655216,161013307,1}},{{5331553,244844100,0},{735866041,855500508,0},{741197593,100344600,1}},{{196413674,355311746,0},{100825558,111298483,0},{297239231,466610228,1}},{{703413208,728953185,0},{286106717,433975862,0},{989519924,162929039,1}},{{488572121,822567748,0},{568037260,134514775,0},{56609373,957082522,1}},{{172516064,626320720,0},{119676100,414027427,0},{292192163,40348139,1}},{{139381797,156568527,0},{5304104,835139947,0},{144685900,991708473,1}},{{106181466,6970751,0},{118555890,222713018,0},{224737355,229683768,1}},{{923734226,217300640,0},{542655854,91823586,0},{466390072,309124225,1}},{{787287761,189073412,0},{72239955,970977683,0},{859527715,160051087,1}},{{447764960,612341527,0},{889314621,349284201,0},{337079573,961625727,1}},{{549192428,686761879,0},{579882787,621392890,0},{129075207,308154761,1}},{{910582676,212513613,0},{904312551,156448071,0},{814895219,368961683,1}},{{165222891,996165429,0},{878604096,158892688,0},{43826979,155058109,1}},{{318363538,115861829,0},{992607073,244470586,0},{310970603,360332414,1}},{{733154037,617069589,0},{242602920,619519272,0},{975756956,236588853,1}},{{837734215,445986396,0},{200345082,728503241,0},{38079289,174489629,1}},{{273003677,875285617,0},{935163683,328723987,0},{208167352,204009596,1}},{{73984841,699446153,0},{685587471,929639509,0},{759572311,629085654,1}},{{443781387,267801972,0},{312271259,486734102,0},{756052645,754536073,1}},{{74689000,492258687,0},{758838734,220406209,0},{833527733,712664895,1}},{{146878717,449138825,0},{74702803,386847996,0},{221581519,835986820,1}},{{815418571,552864265,0},{72734904,131045238,0},{888153474,683909502,1}},{{732114487,297280038,0},{682889828,891010847,0},{415004307,188290877,1}},{{182677016,891374360,0},{571621254,818208022,0},{754298269,709582374,1}},{{242246274,198490008,0},{349504530,46505506,0},{591750803,244995513,1}},{{362869729,390315195,0},{237738305,776613136,0},{600608033,166928323,1}},{{631109931,666990643,0},{237766497,333635696,0},{868876427,626331,1}},{{225257353,596769944,0},{482973358,152614814,0},{708230710,749384757,1}},{{546519311,574100485,0},{621164640,794896202,0},{167683943,368996679,1}},{{246322213,417594104,0},{864244712,821806895,0},{110566917,239400991,1}},{{78269476,835859944,0},{352391247,345000433,0},{430660722,180860369,1}},{{938916497,336989090,0},{475535579,894520673,0},{414452068,231509755,1}},{{912348155,836521072,0},{65571266,882397490,0},{977919420,718918554,1}},{{651346906,999189571,0},{157292968,675429686,0},{808639873,674619249,1}},{{806963397,746415748,0},{129486723,262333486,0},{936450119,8749226,1}},{{837809032,87600850,0},{960307112,175836692,0},{798116136,263437541,1}},{{734139212,781711123,0},{305768303,782266391,0},{39907507,563977506,1}},{{766234974,554456624,0},{462244861,142559764,0},{228479827,697016387,1}},{{779584000,850992433,0},{208805545,950934017,0},{988389544,801926442,1}},{{315110168,824132039,0},{77661196,132104822,0},{392771363,956236860,1}},{{549881036,385205260,0},{823622054,783229828,0},{373503082,168435080,1}},{{15331662,441926414,0},{512044000,915108241,0},{527375661,357034647,1}},{{927556862,691221091,0},{583367753,646367513,0},{510924607,337588596,1}},{{95408496,944357174,0},{841636163,319263497,0},{937044658,263620663,1}},{{344565084,565488325,0},{55161862,422896978,0},{399726945,988385302,1}},{{239240363,547222076,0},{977904016,706576955,0},{217144371,253799023,1}},{{699922967,504371520,0},{318681953,816714817,0},{18604912,321086329,1}},{{85233090,404029485,0},{852937872,693274926,0},{938170961,97304403,1}},{{15974509,297636861,0},{255767776,719490755,0},{271742284,17127608,1}},{{565535540,935394410,0},{286252326,995012594,0},{851787865,930406996,1}},{{692139717,221110073,0},{715139428,552631540,0},{407279137,773741612,1}},{{548300551,35672957,0},{216264766,731400765,0},{764565316,767073721,1}},{{587859202,964053182,0},{178397356,999984579,0},{766256557,964037753,1}},{{424513309,488727933,0},{956014204,805473776,0},{380527505,294201701,1}},{{821316489,705777853,0},{157361040,152563232,0},{978677528,858341084,1}},{{317784579,704494278,0},{109521121,81294677,0},{427305699,785788954,1}},{{406771640,861266614,0},{743667476,848018490,0},{150439108,709285096,1}},{{920905754,747365144,0},{948184347,622264329,0},{869090093,369629465,1}},{{677614646,3004859,0},{603645547,183211460,0},{281260185,186216318,1}},{{71375382,658846472,0},{244761865,298615218,0},{316137246,957461689,1}},{{802971318,308472487,0},{430825295,239920005,0},{233796605,548392491,1}},{{480402168,856173837,0},{647830434,185021938,0},{128232594,41195767,1}},{{153860409,757379860,0},{36630091,167450011,0},{190490499,924829870,1}},{{441619845,199552720,0},{798181460,681518953,0},{239801297,881071672,1}},{{422545615,966094981,0},{300451241,820420040,0},{722996855,786515013,1}},{{758553510,97528061,0},{582412941,556789832,0},{340966443,654317892,1}},{{817270691,543274312,0},{153217013,893763918,0},{970487703,437038222,1}},{{800420404,219007391,0},{891798999,252244302,0},{692219395,471251692,1}},{{422333834,600505451,0},{826273967,996812651,0},{248607793,597318094,1}},{{417946641,683008433,0},{805726695,48534568,0},{223673328,731543000,1}},{{90797997,911953746,0},{223423120,51884711,0},{314221116,963838456,1}},{{949170123,238624972,0},{178305444,494078560,0},{127475559,732703531,1}},{{770739850,324944645,0},{754071375,883120083,0},{524811217,208064720,1}},{{540577862,207209335,0},{208730174,405662496,0},{749308035,612871830,1}},{{673852577,25917980,0},{253600831,638488285,0},{927453407,664406264,1}},{{773880248,196961288,0},{100955712,100409603,0},{874835959,297370890,1}},{{718233679,683703051,0},{417917660,712151195,0},{136151331,395854238,1}},{{541666472,995476873,0},{260663580,72859996,0},{802330051,68336861,1}},{{759085956,471158106,0},{36564129,807281995,0},{795650084,278440093,1}},{{640390740,51533394,0},{1242566,481974928,0},{641633305,533508321,1}},{{936783673,109543052,0},{49216802,431388801,0},{986000474,540931852,1}},{{241548625,482481268,0},{298910687,99741617,0},{540459311,582222884,1}},{{74038506,137229176,0},{172451097,295288656,0},{246489602,432517831,1}},{{615646105,357635085,0},{674342922,483525045,0},{289989019,841160129,1}},{{633942111,740363085,0},{156171114,37017571,0},{790113224,777380655,1}},{{350029305,481267354,0},{773713106,733769701,0},{123742403,215037047,1}},{{45374118,806152062,0},{181353422,486779164,0},{226727539,292931218,1}},{{742553260,4015895,0},{301095626,835734126,0},{43648878,839750020,1}},{{740477853,577681190,0},{870866508,329567627,0},{611344353,907248816,1}},{{771727640,399477747,0},{124748685,735994786,0},{896476324,135472525,1}},{{299527689,199843229,0},{174948002,206137663,0},{474475690,405980891,1}},{{730608148,52680282,0},{364694009,199768239,0},{95302149,252448520,1}},{{14205800,764760425,0},{812485075,869458883,0},{826690874,634219300,1}},{{217711441,355655154,0},{697753453,457630124,0},{915464893,813285277,1}},{{46648290,259381812,0},{963176356,315949799,0},{9824638,575331610,1}},{{610355341,66532776,0},{893617876,744324937,0},{503973209,810857712,1}},{{637094169,623101357,0},{615331513,622679334,0},{252425674,245780683,1}},{{737784418,880442913,0},{746984122,481289494,0},{484768532,361732399,1}},{{993511074,318131134,0},{541217700,348370769,0},{534728766,666501902,1}},{{487793132,661190465,0},{892849704,527889084,0},{380642828,189079541,1}},{{91851611,819621700,0},{906347258,990842358,0},{998198868,810464050,1}},{{290924672,640681443,0},{432949405,662010051,0},{723874076,302691486,1}},{{792250927,463189821,0},{611702185,328211489,0},{403953104,791401309,1}},{{410158716,421433273,0},{180073461,271212021,0},{590232176,692645293,1}},{{922050608,724493854,0},{163895406,560217248,0},{85946006,284711094,1}},{{92758579,697118356,0},{559340633,299664681,0},{652099211,996783036,1}},{{316019884,152949921,0},{168079026,503608658,0},{484098909,656558578,1}},{{179674381,706224634,0},{161691184,293644439,0},{341365564,999869072,1}},{{371635638,317943382,0},{388791469,49554437,0},{760427106,367497818,1}},{{782266507,468114327,0},{945073391,533369020,0},{727339890,1483339,1}},{{844488183,826709909,0},{401149525,753892166,0},{245637700,580602067,1}},{{886803851,494648312,0},{210046198,725397981,0},{96850041,220046285,1}},{{988016198,711086701,0},{701823484,60981494,0},{689839674,772068194,1}},{{807304965,913845432,0},{168551925,759041327,0},{975856889,672886751,1}},{{590381506,735804301,0},{719372553,2642303,0},{309754051,738446603,1}},{{634111016,152919044,0},{315718305,251961324,0},{949829320,404880367,1}},{{644628082,156662626,0},{562771993,663832845,0},{207400067,820495470,1}},{{737892499,722567234,0},{806311358,820362509,0},{544203849,542929735,1}},{{883854932,354091891,0},{431980877,363117375,0},{315835801,717209265,1}},{{512736785,862521284,0},{583601,65818534,0},{513320385,928339817,1}},{{379723463,620667891,0},{693065724,457274926,0},{72789179,77942809,1}},{{530840343,816999401,0},{717892891,129212921,0},{248733226,946212321,1}},{{118500101,25937173,0},{223020879,106406012,0},{341520979,132343184,1}},{{253110907,193500950,0},{179500099,599280210,0},{432611005,792781159,1}},{{572509200,330692109,0},{456998844,833403800,0},{29508036,164095901,1}},{{391246967,656591335,0},{689086471,129355766,0},{80333430,785947100,1}},{{961768756,589262100,0},{184353818,981498672,0},{146122566,570760764,1}},{{728376838,338019428,0},{669965201,729630273,0},{398342031,67649693,1}},{{652405592,49205600,0},{322283212,659059585,0},{974688803,708265184,1}},{{710049220,752613508,0},{567715278,253141367,0},{277764490,5754867,1}},{{413271090,815432301,0},{171902274,484902857,0},{585173363,300335150,1}},{{741515327,13976609,0},{186429783,371986334,0},{927945109,385962942,1}},{{897899963,644011738,0},{857748972,417304942,0},{755648927,61316672,1}},{{720969589,540642074,0},{823455384,378237258,0},{544424965,918879331,1}},{{252199460,766823344,0},{92024602,177336644,0},{344224061,944159987,1}},{{21714305,527068163,0},{809507524,374260041,0},{831221828,901328203,1}},{{239137599,85330857,0},{285579745,926868216,0},{524717343,12199065,1}},{{703314204,824492488,0},{188898025,104146526,0},{892212228,928639013,1}},{{709694573,444477471,0},{337096623,663074126,0},{46791188,107551589,1}},{{440810565,464484079,0},{318533836,280737850,0},{759344400,745221928,1}},{{702670138,292650891,0},{51997461,950302029,0},{754667598,242952912,1}},{{567837264,123879347,0},{195223181,893923671,0},{763060444,17803010,1}},{{463709035,726681122,0},{204154524,931461328,0},{667863558,658142442,1}},{{498596440,223184544,0},{278934311,387711659,0},{777530750,610896202,1}},{{327875448,713783091,0},{993157243,47329887,0},{321032683,761112977,1}},{{166267992,739135328,0},{502164351,13690685,0},{668432342,752826012,1}},{{212142747,329039546,0},{942696086,354564738,0},{154838825,683604283,1}},{{261900753,260204418,0},{102844262,807663106,0},{364745014,67867516,1}},{{558911444,437447134,0},{922153766,341402853,0},{481065202,778849986,1}},{{961985607,124334458,0},{954225627,613219092,0},{916211226,737553549,1}},{{31225147,878773800,0},{878069787,11459097,0},{909294933,890232896,1}},{{821387933,751101818,0},{712406266,977268370,0},{533794191,728370180,1}},{{271160253,992310335,0},{757463204,511913110,0},{28623449,504223437,1}},{{613983829,557968816,0},{417415432,214980966,0},{31399253,772949781,1}},{{399414719,364214199,0},{717427191,536698129,0},{116841902,900912327,1}},{{104791618,124389802,0},{719136090,341298695,0},{823927707,465688496,1}},{{423800841,444397037,0},{785837645,87274673,0},{209638478,531671709,1}},{{405526961,489587763,0},{734695757,673740732,0},{140222710,163328487,1}},{{381177899,101429172,0},{524311147,193477229,0},{905489045,294906400,1}},{{43509603,754212882,0},{880290765,45617728,0},{923800367,799830609,1}},{{386441203,611654630,0},{839589026,195729165,0},{226030221,807383794,1}},{{293264948,913697779,0},{654857409,128841256,0},{948122356,42539027,1}},{{620570347,786589266,0},{63332304,285386455,0},{683902650,71975713,1}},{{628767566,486939299,0},{304092146,310043635,0},{932859711,796982933,1}},{{117661594,768187900,0},{418251354,200210820,0},{535912947,968398719,1}},{{335840067,351798683,0},{142166214,124187290,0},{478006280,475985972,1}},{{243848566,778205460,0},{319041392,951234768,0},{562889957,729440220,1}},{{504645156,429766117,0},{728908968,448010834,0},{233554116,877776950,1}},{{831050413,186505015,0},{469121905,137985125,0},{300172310,324490139,1}},{{396931857,550395665,0},{330981205,496286864,0},{727913061,46682521,1}},{{345636394,489690197,0},{452503157,731220105,0},{798139550,220910294,1}},{{839365989,484760259,0},{94789451,601650207,0},{934155439,86410458,1}},{{813374968,843428651,0},{516721156,428191943,0},{330096116,271620586,1}},{{385530167,895423749,0},{153233210,464625897,0},{538763376,360049638,1}},{{306101877,500665433,0},{643971440,870565640,0},{950073316,371231065,1}},{{798984587,867900326,0},{629960707,777885751,0},{428945286,645786069,1}},{{883033801,646856867,0},{776840687,194344123,0},{659874480,841200989,1}},{{298044732,892738132,0},{242584390,182113989,0},{540629121,74852113,1}},{{946926474,939434561,0},{570889010,717728826,0},{517815476,657163379,1}},{{143531619,140255087,0},{519069270,323221655,0},{662600888,463476741,1}},{{670203431,809265135,0},{713158118,663778007,0},{383361541,473043134,1}},{{440451658,247496059,0},{44728925,8782686,0},{485180582,256278744,1}},{{470032096,302267608,0},{774477813,480564776,0},{244509901,782832383,1}},{{929897513,588513623,0},{752541724,350787289,0},{682439229,939300911,1}},{{989671332,649172798,0},{294237587,355263355,0},{283908911,4436145,1}},{{269678404,100206888,0},{424697816,458749363,0},{694376219,558956250,1}},{{52295794,559448903,0},{426015067,344219735,0},{478310860,903668637,1}},{{709737873,126162304,0},{282787046,371080703,0},{992524918,497243006,1}},{{462189100,741884169,0},{830302294,85388172,0},{292491386,827272340,1}},{{607812687,714509177,0},{478823099,365930538,0},{86635778,80439707,1}},{{1000000006,1000000006,0},{0,1000000006,0},{1000000005,1000000004,1}}};
 
LL qp(LL x,LL y)
{
    LL res = 1;
    while(y)
    {
        if (y&1) res = res*x%P;
        x = x*x%P,y >>= 1;
    }
    return res;
}
 
int main()
{
    T.a[0][0] = T.a[0][1] = T.a[1][1] = T.a[2][1] = T.a[2][2] = 1;
    int t = read();
    while (t--)
    {
        LL n = read();squ A,G;A.a[0][2] = 1;
        if (n >= 799039878) n -= 799039878,G.set(),G.a[0][1] = G.a[2][1] = qp(2,n+1)-1;
        else
        {
            int k = (n-1)/1043133;n %= 1043133;
            if (!k) G.a[0][0] = G.a[1][0] = G.a[1][1] = G.a[2][0] = G.a[2][2] = 1,G = G*T,n--;
            else
            {
                G.a[0][0] = a[k-1][0][0],G.a[0][1] = a[k-1][0][1],G.a[0][2] = a[k-1][0][2],
                G.a[1][0] = a[k-1][1][0],G.a[1][1] = a[k-1][1][1],G.a[1][2] = a[k-1][1][2],
                G.a[2][0] = a[k-1][2][0],G.a[2][1] = a[k-1][2][1],G.a[2][2] = a[k-1][2][2];
            }
            for (int i = 1;i <= n;i++) G = G*G*T;
        }
        A = A*G;
        printf("%lld ",(A.a[0][0]+A.a[0][1]+A.a[0][2])%P);
    }
    return 0;
}