#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int p=1e9+7;
const int db00[]={0,351414877,992644086,243187594,970593294,808163324,838350589,400045985,773003678,272469119,171336485,99232354,374943291,120991754,918828861,58430464,233575843,430230130,314945522,920136431,629988826,9286095,538985525,569599399,952732966,812227065,923708986,825466219,722180776,454370715,391886036,440882993,946930188,802992635,594868609,391366129,780002268,991313688,3576763,174306542,524177508,404021975,884687717,819441943,467630368,952264775,740436501,548951520,176890692,961169723,454746590,963121080,77419906,952803271,255999824,640243362,490797605,798383545,928580445,90718247,963642677,19631280,661867729,261006473,204074223,345539254,439481421,575850342,175082343,152138907,142661295,791062760,172956148,125025482,658706907,865045879,296178073,742451930,946927034,298320732,623883723,658737656,868955278,605922797,716157614,808853780,416549744,599637600,66674121,77510211,476144980,693507674,391932585,179153149,177542017,483764175,267361928,237749282,586319702,131889083,724756848,380903222,960315030,250750674,927051050,321464949,125381239,64581487,340789903,170225291,117665561,959343777,25376646,333493403,160723575,60557017,154000990,711655122,874767552,599318901,429420369,451620789,771861106,731096508,704231318,316994080,636168130,771667652,565848642,669275366,157959714,837777531,821917725,355055845,117492601,834839650,967222634,606380478,126167307,60575937,397518024,18915045,156629445,868531538,522028635,552835758,351283455,123374846,63742820,797229512,607627717,960343842,565356844,909447907,333279676,849084073,871055983,191086326,233701337,749999892,4178849,915648900,59314744,182648949,891021542,715537062,157845682,607145029,631147903,612245363,764770755,409368154,930421968,641445508,222384726,158361283,933842117,524289060,307339313,485058180,677265230,650963979,503750622,785447019,633693691,770926732,230622879,66678610,953925068,441234638,229760002,982891999,758493924,154400357,545537897,379597092,786779168,672975749,16436312,801203244,712323772,264792406,678333839,970000604,886409971,756363812,827919987,271851265,344765547,219652012,267367793,711064284,517363081,687405977,255242950,314693810,831082256,921735583,778614217,400230512,257365862,555926677,979751628,568507255,464961579,624127181,200783288,940201838,829524576,258393558,583932498,514425621,940757223,609574593,89803359,750186395,449052692,238296917,401037814,488212916,410982194,365301481,67538239,746778054,781342465,508602499,365800857,35728264,390481998,20394970,643171183,981837684,846228118,475161574,567524183,780673497,639847073,102659457,753496338,157910821,634358526,404452208,193098977,917740563,158400759,877027814,766727493,486244684,112813005,906664096,138511903,665797086,225677323,806427504,264229843,801857614,25576734,793340346,159206100,917882369,620989915,687034628,99449773,360561927,274474435,387291336,334392722,700430890,87337377,125268108,921003783,541630735,245365448,637081023,275204499,954620644,761323755,99986178,60601090,84233257,631036082,218336185,54859296,937637555,660429447,193761180,539273239,891819441,412734519,199203638,380926243,797728406,594363472,102944664,986030858,193931166,800450780,167077557,734082124,364487720,161843796,696265031,537252135,454226173,204690608,145822611,777594678,873783314,26639584,701207145,555494462,203811839,324384840,163081440,622875445,933993308,952548181,626577478,633136189,722085471,283590694,466302891,784388329,269577090,610520882,794701752,358849463,650946064,426479901,716721350,9934752,290932466,42179415,718228854,810213208,262308491,989316300,435635803,475457359,698035577,462471557,473096995,909615490,802271976,157995054,164909179,800544667,555295152,659371258,10391806,620147081,295954847,230405822,320429334,791848593,650118521,518843232,214929606,690034586,789813422,764040106,681430901,538120245,181027632,116862575,772875333,964537281,93190871,940859511,541509426,743912623,966790667,678256600,778431260,464387180,981761630,728639344,719923969,847945850,253569355,927674523,105621392,645800064,150888803,277898785,578163694,569227431,836890169,777493098,588782389,467728311,635873519,130715061,41442543,91073834,329293994,105392576,868937788,227753998,852739138,864765312,206299340,325628434,182503912,490802584,321971357,956623562,699707405,429715609,853374201,558583797,174074286,412156968,319334606,985884482,398680326,526588418,120541985,774256917,294442508,890969075,400433259,339425797,318826075,636232599,681274101,865130968,775183799,124446707,16580513,128518638,71495267,995884328,895941485,149696807,591143748,694478447,629353670,10770646,271729083,118973135,797013866,198590884,685018704,104952091,252861475,971560082,255346334,774050852,815634354,811117335,114343305,279976198,163701895,97316971,751109176,344220374,452271416,771895507,939918211,395351188,56603168,661445314,19178342,587488986,80003577,207009519,141105499,212751123,454127246,202146393,932737689,156197042,711740720,855161818,623405044,543167048,805896065,159162631,953777997,434952521,819720225,838548270,592803971,269641136,283625657,868926781,431692595,35652052,132319357,340702108,723587824,311704107,43356005,1824627,159782316,861497693,682769329,883121098,635253082,827254797,536517749,537843037,952078557,11478853,783603548,936170281,693444923,345647741,689634962,562130382,697481053,337147370,816368493,893619299,768986883,125112603,54257249,389553394,594017072,369087102,728587271,685957613,382738127,167074771,348133285,512872728,179884049,664208272,958399831,599485074,204645657,86894891,406514939,778361115,74867047,485185854,296836657,849120681,921860687,822502576,386839340,834068786,410158625,165424580,324116462,550417565,528292750,533839410,771112414,640695418,395694635,968891154,368376327,682059098,663588588,504472923,223495340,114454605,707474114,869521089,437005850,791733101,337665914,858690582,50377583,892991754,481410347,423127456,852739142,386686792,296620772,224220000,665117294,806741201,840567518,868240179,808001284,418013057,594067609,216244818,728395664,562878920,588274468,56296333,162259164,661421440,321466091,747899648,711246037,897295852,72996963,203844152,303894312,852580716,892350649,628559101,529414053,635691175,513537708,793552701,588032089,79412738,565475114,773485818,664268618,133752131,735616386,703710433,543148069,897187407,748748056,828192379,647779338,72064660,860410002,605234648,424657721,243781297,616435207,29360799,578347267,868922177,59134328,898115716,711230741,665743593,170093286,874215984,677802151,214831768,726969190,842967817,367432259,587236330,353534785,810697044,75114827,210554820,666723118,773238955,771205619,152653063,3630766,685512565,742007165,65888089,634806048,866235048,335848336,188759508,208807512,146895051,663749506,795660130,95430810,161097983,534113312,574065417,912244242,573700283,67221491,603873880,348543476,957497688,605859154,845759243,487521484,38568409,816345228,943014059,479914929,445475248,894081576,881892441,209772787,54911793,200498908,700125064,636286863,646533710,280361103,739319166,704993416,544742062,460202296,943288787,728332138,495436514,548466657,961562365,511104342,315495283,829071352,992227687,686713290,938742262,572309599,409527881,264860789,303048441,639266922,376189479,605277166,112433019,339564233,403553992,488912142,61056724,834687636,704301187,602712552,79366404,366911781,567396810,609824875,790621723,907394808,915482593,23898290,294139298,74548481,767085482,163842944,133386794,989920964,494310044,931914043,137060559,242933210,962252957,90568060,121798875,450066499,454054059,108598784,357006270,137530510,706938197,562307458,164610071,172507587,160882347,374333615,301600865,561569884,245876509,382738260,126497536,487786317,371024810,213492934,771390799,85897425,830285249,645757575,115248063,416024202,63872839,197202010,347929159,794324244,681072949,290464760,176047982,278830101,751125886,280156018,582404840,210547085,620328596,759244370,64848549,640554505,479452367,792156746,77593351,235277040,841698084,771446101,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
const int db01[]={0,898710604,52980829,628810107,667485330,516481879,961066123,872191005,974469605,466931932,293687595,905221790,408999680,749219668,389885847,822459658,510516113,896722092,810007735,216681923,585597481,138197612,15711960,785302526,892082986,496180347,310697553,150708965,509742820,8044709,457460167,407158391,912474455,189360339,496518259,932373090,573506182,77594279,491381858,777533595,299845991,718255700,19193914,90421758,591709515,641817424,127334987,208820532,171133358,854161283,527996713,52621530,993349999,399902451,350824238,168096872,580747536,369683954,388316151,485566099,809093723,414210176,637856037,965176691,417633052,467262142,825904643,247412511,443257283,676017796,451182553,665003812,797975530,424372530,178935897,955000866,54093834,483877258,818098713,561229726,845081496,400081926,821417470,13074827,738202409,82915987,754476698,315928900,936645547,17604941,374632347,85575582,873890932,248970090,46768060,858198526,98923099,946769224,393369813,401007954,524315534,511921611,52445192,574454187,168730511,518025096,487153973,902853048,980325115,168612282,766373911,795709705,543026296,183625102,14538761,630208496,135827127,200672824,83635317,282593664,52838375,379236756,244896796,805007081,658878547,428623868,251412769,907078016,719067782,916013116,251889499,287734914,902909645,603823555,225328149,386398722,49881718,508663083,400081181,242988602,80360128,863095839,174356573,969880405,395050930,205893536,786539974,623495921,431990290,685063113,826872828,580471792,148670314,241313424,674818289,261176530,173083748,892960460,370107509,762061675,202527916,453672021,513274655,709229689,243808187,746054539,849693757,709421012,102107031,719142941,134673949,79316080,676771724,337648830,681906205,996223089,480382658,843963857,510648386,659602864,738831938,344518742,818038399,770460864,514057228,157069490,874947577,554534405,475467050,881259315,105784360,360878361,408313241,109795486,937819963,954320440,715960468,465929405,698919091,289450953,306148771,33339153,473075461,5396284,167992087,556915649,110934880,544759879,647463187,300090843,384743190,62285507,396177921,554522609,604113056,997321612,497310182,569070069,733018346,411700949,862307482,865968625,198925033,837215846,844779921,624762429,964872950,623223409,101584228,829658456,631833018,461675260,503777693,932944193,339067568,386841400,53349159,640524636,170560069,379698617,129736452,64498065,588809231,907556691,424251634,592147926,697973355,534929206,985457784,331969973,564714923,689990983,989929831,287360788,916471360,319974199,103292871,550754342,689845004,207428192,61129791,705911162,541741423,21500882,619669289,644417328,152622514,728759850,996070311,350663270,615250110,702798597,936915975,517544609,66016835,37781471,272463127,327272038,622737607,124808858,699429762,923217285,39314111,366993221,345594348,252842597,297092871,259513190,987730679,405924339,415204026,755961355,495091212,793235747,843130938,931004083,446577106,964330319,506010630,65180685,655011131,614895671,580209624,734180975,705691795,341905916,219310483,348784061,262751574,563257499,988692875,316682085,542083747,136319601,860981658,690608891,225229220,365112816,220521475,528897305,666663079,608106768,757057467,123286198,327012054,870421373,986336553,563421504,353847155,503127000,893437473,528228268,529423067,199105575,555867710,870812584,857401511,773920645,274424217,301767957,737944584,312803727,192404969,724099948,212676315,357581687,446016861,763734159,71306156,302095308,460652466,571655664,35570377,764150663,889322413,212755299,961158961,554394954,413377325,809805606,255388197,388519320,927928339,292391317,181878419,110336886,346976416,405512804,790189373,285093223,380323792,836570679,903001082,870115794,980615034,877660436,178591868,500139020,92186987,909096922,192885722,407602667,221444162,662147782,369289031,715433906,987695645,168227140,830612921,333523531,575442255,386312259,408814539,177696165,385558556,142563410,241629993,215172639,125080232,987430759,870103438,425029584,711407134,664162348,5905308,338279530,180283622,175938865,840381631,410806628,834813854,955412728,258443714,165251107,570813121,18486881,564884595,454546320,918710580,3859911,159989455,696208035,311492792,753041497,838536163,890866726,532961314,694868446,821776989,741906631,677184581,196885027,552618172,777912229,475799479,165925121,239611500,856728152,450875990,501642440,796157425,893975758,269166194,934661124,351556408,102114727,624166982,9173633,291228675,595009190,260049157,832708886,296555749,30969472,746593969,463687844,532660256,70395232,10463547,363631060,577175188,842885022,55534747,867892130,461996493,458037764,22381733,385615896,919036373,958937491,316341080,423139916,690323686,129272190,277874762,615972859,836774877,507773611,138833071,708049132,623128591,660926488,796442098,329549945,90708044,138993271,978533222,796897682,827672625,787762214,683717266,291714836,411171773,64073774,166570277,794855465,81345016,953750748,375145994,827729299,33860197,640937035,673810842,521215560,254912682,248840294,469820780,611582347,385024549,203573084,876490919,359863026,751883318,260543023,719327889,427085327,423133019,9927204,306785226,103674767,706645012,666200346,782476777,762441521,245773959,465758738,619790254,820042698,531903848,793779511,324742837,368741956,828742171,763757731,206414756,281514238,452822954,397550329,624356011,354480672,5685726,305729978,41099581,790816813,728901567,803578821,187987927,254606236,639322316,964262366,707937781,227976339,299714911,789357352,749196816,657085174,907082453,956898700,395015949,306768889,332276062,264524184,160019920,31640640,447065855,574651782,866363465,989448781,830637398,53911021,532215477,25226650,775775624,490342742,903969558,929450235,93242291,370308808,929888133,171305030,830437613,148686213,234034405,130646685,563325835,16438271,586018206,592096857,636739597,565970170,889383393,465976358,7155406,179309674,116795909,715068847,799787725,568592767,989124012,27539396,79582735,615604696,879032840,579732793,896565699,192248598,412333482,809985889,791496243,478582287,15017523,903944014,694916507,470678012,736381216,507089435,955072381,483406685,428082983,955113720,749659373,71857236,914515983,78493190,433989108,217715742,494765272,416457685,740060208,132411973,743927795,45110188,539694185,777817075,965802357,463163656,850661862,390473526,698110501,976273587,188085766,955687321,669350731,593483510,928751569,60002158,690889743,285125827,590409828,664792833,918954839,949755766,654470944,350477649,935803645,667799249,819977425,840034232,225930920,266002540,268947645,624310654,330728175,826710518,537030898,123026422,233052607,261075497,452555282,753113049,470963769,159211425,741665350,210779947,746072202,947417360,162860608,568733634,296085096,575425676,740860617,62904925,914015374,754495592,788505539,976762197,28320043,708047960,886502658,752046682,707761713,121653752,182098389,207312849,128522555,988813982,25492810,296041643,159430341,776670629,809892766,81791212,453637611,383276698,770933806,386663923,445727273,505756507,442472356,100896806,657622875,905911408,639527110,125975503,101635455,703610725,737568822,564115411,739417403,880383864,565489537,327350580,19954976,159497285,569872755,978020602,500707827,954604087,636648358,930821856,258869306,11948717,657618508,195032810,830423263,663160650,714110255,292579656,922793404,255640015,631495673,738805402,634196355,6454277,737550280,492180623,606957591,841707116,759106527,438966216,198933586,70273250,263988426,297375236,286396222,585638990,290560395,362895600,752507530,665332040,400239272,959178806,591217069,377491811,595118754,887466288,177276923,956479377,147955478,973784475,264781393,16564339,401320123,109351611,990051662,492853358,812620318,31753767,823313552,102670431,216074082,986922450,565020627,287898512,286724912,408366640,452051815,668952497,854428100,388087987,247317729,600444946,185627399,255813006,114391661,378059718,741118273,53748220,793750557,41695639,922801991,730700581,103560761,561701019,359036638,296278730,484681394,242348720,981121551,97121771,104814640,861534882,383165579,230709037,941844959,107560400,940937139,227052652,688964072,161397575,315102457,5844711,133125736,111341453,417024317,669662990,138945699,188589718,549705815,932487248,461989643,402328023,492413373,493932101,447614298,738344345,120054595,238728010,853636794,530477068,677254123,656918901,241274227,935788321,451387713,963197453,226974408,58228406,577767144,432754508,124885460,687130853,596055842,637013399,98516019,23197323,758083693,84815088,13282459,725131587,296404751,719791293,607765763,560314470,29453526,582432373,454945344,872746331,422052936,625075952,996073267,186745041,872470911,138616301,804981197,909775629,806373424,808160398,853559766,710883151,584877901,387383882,846374568,990462237,151666067,653618683,212835195,345332009,100835767,365661789,417604316,827886663,763083887,969747749,275096707,219826699,829495666,138493776,276903808,956714450,864017684,273249956,65364838,237219098,72789585,47437275,946343005,93476504,49527424,867480885,161322829,861483426,59062333,495530781,483866119,329038863,544215178,315819375,887519338,380648403,4945147,759843512,563146992,827835997,122205949,908986290,943863119,586031376,524491102,913358807,335361540,554284456,133015849,44784916,30139729,147315341,63592070,199286511,783523230,199446244,756470669,605292575,364569499,328776344,538360478,582624782,662158907,32065227,158667712,699285971,538165056,193692408,305349096,970281569,426153797,431441626,638541503,806527979,733334854,49114713,424947964,962295433,590399319,833619189,467963226,640427119,870548930,770179651,938811204,90850275,782282838,911839931,595454856,651132024,765535604,577479253,939820608,483712347,441795316,237354342,100794465,658608927,429297172,758478976,214372429,987327617,617840863,792368866,683497096,874848781,595538338,432164108,294223243,591335543,848724041,958081569,326426388,45427440,192999505,958681853,312783500};
const int db10[]={0,547160626,859676593,633859033,687495918,297033762,366728069,8150003,2328985,40143857,475151343,981326357,291426624,92813800,391380838,424693144,198705853,84944378,191100370,247380204,959150905,608942083,477143708,910218009,307253157,126931643,369884575,816444113,386916376,749542076,478301666,545136632,148387781,148776992,641982444,450408128,849039623,982634935,745630597,511450623,238895653,434146440,584926785,629725383,173803557,328197061,231495813,982076555,315838143,171094769,860659646,346426160,675311085,240888651,874869915,257208886,311062093,369623715,308007868,479486219,251104287,656443067,951244816,203313158,885991454,75724057,54463295,827797248,356870744,483426547,578464440,234695134,580625921,180773450,201123940,579513830,98652880,146709835,912189472,714111501,348347999,621134562,63663246,132978224,853458753,111454902,148656497,765420331,228553676,259231131,794099533,580377164,942019056,495847595,360533565,304509745,558758625,406893086,860938195,258314662,25833641,748496646,168950196,204441326,858114719,342214996,597841217,859004396,840319350,584595706,936809150,410438785,353015980,455638754,449651630,93672730,700940347,640916757,851085479,17221204,922367443,402403949,844892797,169325967,958356029,709636147,856747232,452022282,259346844,430908863,399921637,76825299,695235209,6864874,52458051,871855168,207102546,445368894,202738307,773391157,173506914,234848459,90749962,720247691,474962643,141669229,243332977,422105174,497069244,634858883,109918177,564560261,435705839,104238551,784636066,516079962,194459824,976731999,316320676,307142528,838387589,305639305,815651929,365676964,487085995,562710209,180075922,536086555,178690552,835375071,460132439,760872548,908609132,377700434,15607390,269974056,274067354,725300522,175506840,435718563,566762498,36474402,169412480,823330500,380819394,937984034,469954969,804747464,218115318,279445745,562020703,493229862,998763188,802544858,674139241,845165514,765091649,569328708,807149076,783498554,365363672,39734839,67565434,774438243,951274385,318015634,726141777,881045901,653695284,137138615,727442978,933995673,864045528,620683276,173020645,218706855,392120484,553829823,597159141,538176998,125962853,282478787,762196498,832525433,732474229,614238248,933528418,346339854,936912106,103374369,953354630,220239005,846514084,876907699,401214116,387398918,482248214,682435585,183856282,567824994,131812017,113750119,153087236,199368538,538353440,599408252,860894120,39840534,655778033,424639464,684494991,8315046,134548385,922315098,843922645,672681165,227260966,546924665,215245613,559190338,829060938,938809717,226262509,970398152,437926747,16042267,598711973,249928996,795103539,457411964,420282482,689133742,912566929,994825404,533432084,859285154,64781095,999678566,208162362,12330591,54704298,462573284,570267804,482758951,953433264,943130087,115615589,459012360,417738054,899167850,649450857,314773358,849195131,155904278,491270058,614781947,617837832,539210410,663163390,895664207,928767043,703266570,62277402,399624252,585643950,184206773,466258471,804334320,226721178,539474513,588879757,353007156,309186269,13579690,175151200,918748225,641994785,451061127,959140269,242661143,207842389,11271309,171835863,480735119,259866892,747422518,61331783,638451847,273860529,319007593,494280147,718073457,357526303,673487044,382176840,514261755,398575518,830385282,338114319,730014904,35837128,505942430,581659528,752926714,255651780,914768829,963207770,850435857,684853990,253922058,859930728,103408733,931842646,820289547,458295234,65758726,70182966,870564442,111354964,979022774,291648889,180720578,344241711,978394161,175956661,258321130,281022551,433811442,180238788,747023871,448316138,205181578,23925538,450983806,993271984,705881137,558371426,396121253,881318082,400227681,451087071,226091854,474783645,426988097,667701384,227368336,692831838,712054048,314802475,951877378,709800145,801903733,425475192,824615492,944332757,609797633,657004037,55578017,105739392,358698623,891858056,976246313,957580530,131661115,399758655,509363988,89848053,671967587,89271246,383938474,72709366,919918319,556942475,801542425,384458483,407857189,541025280,981769772,470474958,659986800,310731142,447927828,692019336,808820850,174846765,562244933,804820123,22687643,283042151,942415478,395606397,943569991,794919782,947895860,546923428,854699797,205434466,42169701,6159528,544229387,710279365,532322116,151208980,560146703,447206672,222027744,743938088,248025059,368203539,822388818,163783484,290467157,73574812,537728253,11863577,349570510,471627316,114669478,317270000,691880042,67365355,185797043,593284135,825429858,154416818,562338607,280945209,224141683,502285353,617216266,285192027,291894808,695861331,724699293,808072523,341991090,62896615,451985972,46671689,718805362,472439749,622081792,48039419,389078488,529149388,734427874,361119449,17875218,161609489,792917846,400515211,668436964,935555389,381591136,696566866,498722248,379575368,756199206,83741882,567782965,845790406,602378496,971206730,478293060,103161857,657500966,216306849,813802043,913111954,531575814,964086279,68703751,532458799,42031372,295821641,20660177,756040878,61582685,110008078,877731764,234463263,742700920,363565465,496058152,208533202,196679263,188355668,688630988,952687674,432081468,327908149,373448724,716061824,964597507,515541903,234794281,512504387,509780039,21484240,483126866,656608026,502506030,404169495,327554890,85834787,577259881,475531128,116852127,115840491,745565404,423650357,395888465,943442043,120738354,284451033,227181945,451833522,114436051,867695588,800475237,194306615,400675791,618354641,228567815,463614016,444139760,201147048,639352225,121896456,961249812,128300446,970534147,251628505,26339770,618193512,878235309,433441215,782407911,408607124,757893055,22389668,587608833,444013374,723655264,495335320,538819134,952577124,146961299,493057102,970033415,40443043,739624791,821367263,856346362,258178591,884920325,659785035,28459357,911677949,327074587,849459871,66964742,364024591,387321982,977126269,706496943,534648426,97743619,316399288,663349963,663588725,545133540,825560461,16327332,105619444,528698779,926291760,856706834,467032536,220900079,390703006,148592482,419152480,763464741,494505790,877609944,720961913,957682,406670929,387711036,845951779,934154326,522347249,84521544,425656132,616513063,861432553,784387479,935282318,334478334,88818768,917385486,447138124,449362831,451893479,551872881,523552495,777825058,572213935,992637572,711733168,894570938,188042069,676377749,273180337,700718394,112995687,589926244,489809054,381515664,159591420,652447374,643329826,600476747,360219436,401826739,930680585,102261625,342516545,118637342,579993491,812439791,965417666,350347149,545225625,839468046,268678416,168443891,484526618,974519596,23913931,408112771,718832515,771287437,767521252,240030684,451914281,911969363,917061376,90916559,706755946,522042053,371246916,852941223,179467651,370516371,142642584,387254366,634461725,762737074,221204347,754972738,900485329,710073681,625422280,832357405,111852429,923498800,950369227,537059223,595588384,610019773,852969572,724339215,377268208,279935962,86942028,685530990,160552814,214651856,955290025,299637337,361299031,395993317,371329032,475788564,742654849,471946007,705721092,841812864,1405203,628332325,77464360,222441897,574053717,521092509,989023074,837737772,844567381,913170129,429415792,938600719,603686382,273318226,8736603,990770498,755356093,667233293,588931262,680169034,301567446,963580125,426581183,351487549,634102955,437668690,5166436,646714865,834186524,406057832,575454626,80825626,276384295,282766800,358229307,322435687,744321245,126084204,411726490,613123397,673846548,773755760,845080625,220500083,499113615,95875919,443534775,195034361,604079672,254412970,858068088,250954720,627332085,819708146,538881863,233103694,196780856,352877391,911142212,450674108,243608711,960638802,351043554,845572304,215722711,704600936,538873584,663761645,834394932,329485717,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
const int db11[]={0,973584757,166608608,328876555,623343406,607767141,236948006,420646635,652873254,982940061,568075894,950670231,838463458,512545701,612473537,173837685,859320792,846121752,950866880,763234863,595707700,662771614,41505391,630054301,669114434,865014028,806389993,722158282,174345163,506213675,271442686,914588348,905691325,504625148,538076788,761016141,994044286,331811237,491239029,331680524,577286726,319421947,682719242,98894599,922098876,593882699,63894845,310848334,934769082,583484215,453515716,999446942,251606674,366433578,335298999,271217939,576861266,405903681,147529246,813690445,78178871,826330098,841027483,125345370,863150059,16084806,884319382,803613437,597211873,661643890,659213725,188419275,192320686,882650255,114524703,810801120,123694740,958375331,264871581,482417076,348808843,828554363,4412569,120662446,466323869,412538111,69058531,930496624,413885060,575009221,945862281,247807420,937272321,191356367,50310932,56265193,891876139,303468879,105716101,490877026,806673300,97716095,831684590,681348482,78343533,649936931,683783063,793187204,505508480,678178774,896322526,775432842,508612123,175083150,621901580,935150476,836837437,755744302,693770950,860973640,814631725,939784650,284322659,526306850,468378289,71062454,112517073,183819842,365473870,607164665,604031030,936328733,767520396,590664649,902286955,690936521,26061005,657271712,296322105,131066347,187481248,506119621,670423987,960563605,635266295,614041492,744597157,267028626,660779091,702071701,42213628,774603649,629765835,100808414,651442005,399137315,202705852,960657872,691850675,360150258,305184758,676193404,632365467,897411541,511846821,550606774,597461,665459851,157007812,622996661,847213157,206603719,540456578,266050283,63374924,627643070,900191139,19641716,608657794,716102826,603144487,366750910,647919125,230760652,639198315,846237417,852741518,781264192,450885308,876527923,52272471,965443678,512156207,664162265,384056813,455946174,941073434,363871464,945727707,955789767,600814634,847885492,250796313,198523863,67990153,270011377,842823552,502215765,464985221,554018222,578026625,334552682,171119524,549967218,26058024,810539999,782196088,671468086,605349373,137205178,723383073,45931993,351298274,827935065,612441997,456701946,191941341,247867809,502212863,593684448,949031557,313299151,54018354,46338142,576614645,842915180,156378646,751136293,210733249,104241705,269538006,852405035,920208469,141652169,221834792,220617352,403341193,864843987,436051341,816248395,195304954,513228145,628884767,635741548,897029733,654937625,528595424,23741991,518762762,686098749,5467625,826246870,136133538,107237572,557112139,602269407,469925805,951127397,73198776,361357370,484178020,440510385,176149902,197316166,257107113,497733702,120419660,636963619,390122148,782800724,953769494,581152984,701741140,537216453,355049120,300746825,556930316,98275061,797177471,956251566,132618547,78437406,761610616,771321352,316170727,50095926,753163776,748967748,897242274,102608085,580625305,306553533,327204871,446034519,214179127,565479725,666547602,403304996,747923665,549320277,773057182,545231831,847100667,43191563,401048519,43091343,440358323,425172925,141035896,439625392,176276848,859938401,35934099,804284079,623312504,795436399,895635551,381367043,909855820,63532659,923707333,807035655,89493716,245183152,289345997,653049499,63098563,701698612,655157716,445760114,718298333,888618322,967895430,363800063,314911398,590535044,445960261,964237384,278175592,338389764,703104488,319857211,138119152,782293398,510557624,828898062,710420348,54095275,308401820,103751359,767516364,674416099,419306997,759172430,313657486,954898702,746564896,654833566,179076140,479829164,519008291,201098292,304103722,780910628,207462553,172180546,225209647,550565629,354066955,827009392,544148504,452443929,658548788,187272552,778081272,520117670,560505665,740236473,385855991,991547347,356158238,374980161,774752682,865914058,117917452,330671182,559424165,314472658,569355904,828724112,830471983,878298016,11168467,124472800,767381320,274116796,831879268,831454527,890534422,355566544,319052431,98268530,224492975,249183410,938913164,579468870,9926971,927151844,295144281,116997862,591215759,474256042,73403328,337585393,331857388,174292692,954649972,192894037,209721329,85300535,77808547,448323645,832319567,826262278,76331113,491119463,75602429,328544872,19371799,515025615,303308642,913154902,31585214,10811159,614314272,69657679,790556273,372113392,441760419,713812481,412600669,961490465,787093623,799805206,69994359,527761681,285044062,708526013,993603040,326718524,202056694,20446807,649910008,263800550,155406270,677449325,449116813,483627179,332564044,543313365,562835571,719966134,212850376,353222554,318132360,363988807,874648858,587090267,957732038,927763849,327953642,914053795,457360314,407703986,586730872,476620965,192481162,246168882,292693113,433969478,218379229,959319860,322144306,442869717,250433608,655332467,753281381,557079044,103238432,505512111,474686121,203178850,885727845,88734115,833686111,789359762,696767926,344509164,420625969,564314748,188914115,238834505,491371786,728421354,411458373,240302379,178678056,604901593,888231810,962453608,733808525,147887510,939374840,632009673,94579074,135807257,610644714,829085227,696514125,661637297,315591156,753372156,38533154,448455217,168523674,224682303,634196160,80994096,428643747,545179419,927108785,55596944,442538558,407701999,968215910,290886854,583392770,201457258,287844149,889192003,318431209,892703863,177434863,701136776,957260018,667265201,958649802,257650497,563901736,272601102,460820648,564385521,643461644,354372872,359076459,967543728,921472969,565703787,57179101,970454441,348776640,453469677,821370626,472727511,86157580,803691495,596837957,710349813,133230193,480733582,218619033,20200740,650822627,296428802,713759807,233913246,649520417,390546373,369704438,288291396,589657027,717793036,516474088,776423571,787234627,529874388,975617033,818069632,103729187,835643877,248513385,388674994,810879306,99388390,401006499,685244635,549442832,639153459,505304286,350385162,313772012,681460833,799143166,749833734,14628343,701302420,794389061,407297262,863308440,457377672,817901667,264100572,814422858,879005404,573484541,824725141,512497053,345413117,327985039,480056389,936540088,328588424,885328166,625264379,871002765,125009451,478136948,50073974,950810499,546313629,151452722,988038623,467483459,369552242,336979923,464524699,68239223,173323623,158653588,396249691,176445876,288409451,972743821,372709590,734616757,210740970,963820854,670044054,486494335,482791371,235926596,966331642,983462676,477818206,515212637,306503705,337055234,32346520,324627691,578269669,438590056,153777840,157570382,290264096,473285647,178944321,105711727,942857721,278502102,964352635,539869972,172747926,402167476,132018264,650605957,994912035,441666878,482860848,310000855,528854665,269382859,577797537,519155200,295463728,804038598,252210655,823957134,413084871,650145097,630214386,462632416,913709908,272334287,953720858,582661088,877518534,264514082,757936609,501406658,990041755,641488115,78035950,328294966,508894353,618641194,115633806,550988818,961629587,54589441,648518008,488386750,103997289,932184193,792155004,398537500,824937291,3382073,176178927,440702067,394916618,887120601,962536070,202439027,726562418,895908835,43803931,159174877,549505670,730447532,631069250,149765510,985026592,75538431,660314864,719886570,833052852,927840557,313951174,29416492,142806989,879023876,900027384,492275546,994375645,177258684,745519778,945665495,515588467,472744530,892922214,863191487,127949480,476648530,264076146,933790549,389926791,924826026,173792172,233055942,480343094,698991944,997533132,704575133,51771484,136087697,350630716,105967182,852232323,590054972,439888096,302877431,742354799,717057140,115644442,810664343,787925315,484437622,53154483,612544434,933474009,963172436,822187361,886663105,18782674,814465550,991052566,938989768,597150851,916768027,811632499,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
const int db20[]={0,898575502,852320671,877046626,658089204,105197078,205078650,408195987,775332662,312612975,646487827,80558703,666369914,213805553,310209691,483123607,432281695,515174507,506045891,167516627,589139723,618228177,16129225,479817400,259986115,939158707,293593553,641910324,109097144,203912783,870187701,986019624,95317961,951769626,236851045,841774256,629041883,973948615,749207359,685757164,763073160,838168414,469614494,449167318,641433924,280461828,971932313,531028067,492728834,132264484,315406228,309547232,752730990,193691914,130869731,897452247,801859697,168007252,236588305,570204465,214746956,676074346,613112537,464319630,90065669,421263310,493944715,403647582,531953086,635565453,721125734,25757886,753582068,305798931,859830846,444559701,394830952,889161764,859116498,12432225,972231721,279872210,932618523,738901020,569616359,920308681,565206240,365057923,295227796,336741341,270244505,273884830,333951633,675000743,538075581,788273919,826120552,644642367,447257889,390203744,750590488,129399860,129265218,455191999,785165761,663679944,723222455,923585882,181109245,754820996,54474703,369782554,378392625,789132156,610375204,154229746,854941336,352571871,725853023,616540104,351787804,854024737,616753895,900422474,662587339,26630219,492915354,223689926,825195485,100184221,557881350,914602829,517152926,361920718,169950651,706694810,174325172,51749364,328905613,833967093,571024937,253763503,247379406,588779221,996991277,694504986,594616431,545480019,560812063,432088387,717545893,524904095,1062675,13686450,117915734,365164027,65515799,167818317,550022012,57142412,842566437,221288197,874966672,548325912,378107529,278247263,337921603,143231576,809838454,447620426,224903186,170240694,839031092,19145934,237992115,428335338,207909463,249589574,482846152,920776742,244027720,687438380,673163101,608777511,14513077,708910758,700577847,871426073,172040378,720680382,791780704,476121853,757257104,956945214,219677130,224762598,551870809,242304449,823585387,584701790,77687436,304527244,745899272,744438839,837684348,74379438,554061756,152897158,998460830,356790626,994810770,645059949,381408601,308089245,428263594,533400664,223202732,475565398,375773350,938407509,383328714,838405463,741948118,401032680,197435800,238365421,134311698,286541684,766436674,361767926,537287120,734664625,787271299,486482284,491017474,137585305,931300905,920732501,584894095,56037902,542794210,479051599,220625474,946146591,319695897,108010743,226694969,75568797,46260023,445034433,327666166,990152729,980776502,397476664,411446820,453354654,867108038,649584121,968741950,717101158,463419456,343261917,419361485,888138707,596327505,893070080,365439458,736173679,907916543,364076052,558794384,354930820,138244244,801252900,797661926,661142760,90357828,793018904,367368461,930212959,675694212,149607904,669717576,843320877,227907691,330421415,450008310,159443242,505075430,24435950,570454632,856404092,94560571,792985300,766474556,569402583,379161579,639196587,723764479,979897463,559803117,921602754,117136697,337261799,246073389,377967952,5531702,696153753,639455696,738678150,969805999,150735554,903549740,116524353,161182050,112679383,442445557,618138683,693222385,607148862,369686184,707536339,709087997,934961291,464557499,893245128,838926460,512235153,300500112,20214730,49774601,921885295,681911142,836568483,5052277,448255055,351123691,456962752,971250507,452100367,319427821,972245320,366047849,22503796,866172661,709470573,322057225,501381913,111333883,970643407,869865479,394341198,974022060,538518393,268508434,328067216,59499258,306200237,586812322,677058343,754120445,653817572,253857193,780666129,333951714,423230308,81567210,989106593,839610045,757415676,68463211,501136424,254331359,771413139,785120569,355999650,77214650,611050858,571352660,190041095,215127169,907522754,12903882,608015728,784563958,243661,657369111,805244918,255661978,493386796,453712760,768694392,103731784,603046744,408719929,591559255,385643373,775501985,953685241,612267977,819532571,81867697,603380586,282549917,677657439,87527674,659075483,508857748,866764343,972720862,540437676,555791830,687657535,842984967,475532316,737151182,646417855,850707552,698228955,512725930,175496446,654227167,17647762,991324761,665649348,884216289,761443677,722395047,712757759,795789671,954190193,117644269,207076742,267230458,532807902,253380115,732022883,162711685,780416444,838671894,601248432,932755374,490634776,878972777,83439263,903301844,609069048,23208850,492650245,838969330,292302121,361962423,69459132,433669730,161560383,940714257,166105755,744023147,328040645,963609124,186338489,982810908,791875018,510448554,259368908,815200081,252505283,479488016,276336197,432850612,96309354,406238112,975837528,888401187,905389493,93100258,407116988,904257387,818567195,658723565,867790936,678684959,709484732,408256829,116638366,814431450,568128967,158980716,374360611,247045084,602661603,601174645,91752423,93331848,551728676,122127284,922742415,562095263,242904512,521560954,280742919,422098713,809754992,71097023,372802992,941126622,85233622,245494630,948764005,663895170,304788379,792291574,844162905,85387376,297646267,180442492,617538563,744352013,993129175,512984838,61718052,279218661,901408501,448136701,220012054,980282810,124525941,382075903,298335407,121716422,890038530,70929769,53209186,780965992,409161194,3781156,637616989,564037287,411037633,77143930,25695120,231093293,90127100,710293016,252909557,925393165,988403855,296736175,780048762,703965227,23135423,600534121,30336926,527253292,62812140,302048991,937019375,411272707,716816261,722335916,16809183,787515130,452423419,638726439,629038595,768256221,751564612,167644967,655735865,732362218,768995863,366228774,220519651,394716096,300252602,541823889,937914137,5903243,523061728,465367161,891910756,24614675,235746467,61321170,354025894,589196716,845568870,628371645,916184557,822772549,427129834,36245555,45587255,521463648,64919784,725487835,528025206,836460640,329690998,921142195,65704681,795360405,926903510,975596449,33422594,868756106,196069858,419209709,64298928,374595992,560884569,618130502,29404605,320221643,958200159,421049420,554850853,386120879,102723703,734437786,184255699,736624570,498565217,328939847,267991600,541878554,854714043,736574067,110381354,930859104,743139178,682902374,350539620,732300881,497720791,476923057,466667193,209045192,179063607,950913540,118179566,495732745,316060293,508497158,350009187,263103614,189296080,947918343,446429911,670439715,926564935,621540120,31009878,43810000,860416666,54253171,923692730,665041070,700363873,48238774,932830374,423652985,795982888,604107512,45731993,143833896,996568673,737067672,208751585,454485677,768752998,21247295,112312709,14096647,340885747,934898855,429776398,702557202,58592027,886763830,597614213,475334261,322706387,119830905,725018932,845889837,297673516,399490839,955629784,907261786,649769997,1956974,816722163,747022791,61360084,580289157,197554376,587753273,334586781,399023929,867738056,35333833,639804487,415067089,170164334,292559693,55141208,651830930,445805733,85525872,557150741,121124107,168464847,553410559,369495887,966649251,25684282,257840581,570080694,479512644,258338458,938904258,737488509,1270475,483762050,815352796,146208833,960858148,766777815,676500492,705706389,231044869,156830763,589353677,141450519,130917376,779644789,745132572,760049966,937068418,723555089,13149192,370771856,437161169,142123396,980691454,249666129,599147328,725991820,923102243,263820395,54148177,548380057,801554047,88157006,546267473,362172705,784245374,541124713,968365289,740064696,253333212,437266641,657100414,659830171,884005570,990197753,508822463,538224025,100909706,44871350,987248693,616471416,306397507,329398856,741633493,558782837,611058562,667952510,451614979,205997239,45278956,308405026,110172898,714929844,511933794,947906741,633033408,493547044,661221192,863937306,719883164,415892102,486126801,695175077,496757674,616466934,899038684,676093008,100931810,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
const int db21[]={0,872295353,219589436,957686661,290828728,124249012,198014121,292837632,627342851,449871985,861763488,855892013,247463130,261765361,2359376,996297342,369836897,742843836,760874607,979916785,181305173,800969225,57217350,415356819,561197412,361194367,117087538,872867246,684087982,514258383,728902852,321746731,818165772,693985486,34595039,693389223,567550460,409405515,982620886,109214111,877132716,37677639,701913155,189316356,513808383,235700115,191229831,519668865,105902432,437645490,981512428,52068464,244956665,766336028,686123236,439314810,157608794,775587634,535845396,299256536,887272593,240540266,478883512,90522053,280783103,483346947,710224017,51025940,40469148,337661678,110396270,853423086,990296215,307022777,293460599,765801978,177788573,442252581,82970286,43646794,193890331,228636281,825830038,133737272,204526270,495454097,823535228,246425516,350530599,592614161,320494620,333383001,811163245,440326456,97078991,914463718,990799237,250238095,499085913,891884979,330988826,609637705,884129781,255802661,247074043,167962019,170937028,696040244,485833587,846791055,662696429,571142539,51638411,358708251,636440340,565358964,972664563,956417125,777406266,143567296,867470099,319021398,529219454,331313923,127256828,499686321,363929841,90897850,84541644,523177773,855920528,224063639,670430033,194488196,127615096,77335235,75942722,165934787,696403285,374054948,267841375,369215452,844780559,930444002,30317217,819935027,531137123,890524546,92769373,387134806,869086455,355075433,778436148,342121837,326260286,660313844,375789599,853618324,61958176,122211925,507712673,129865417,145640114,606641222,755655007,296661305,850291217,374880855,259114842,342139594,981887105,285919798,217228294,603699112,745281128,623866151,380573789,863605572,119306172,375705682,341976417,711269651,465957516,1221508,153255535,3306899,727689087,335798589,926352357,757787230,158056830,326322031,920469447,773957750,321876768,410266606,657033894,829800868,644646790,245240712,906963404,881224644,723871773,203920146,235982239,826927025,953758431,46975636,112448400,854109064,962769814,396838188,567297444,104489819,630171079,807861603,279506262,240538147,338367711,548906126,585690547,911900617,550223306,665150903,457221910,81464367,156814283,871091217,603797090,423342896,580864567,774974410,557796046,979282334,915682212,229756572,209727804,391660921,381293317,483940321,399274457,916903099,509017692,49208852,646086425,812765277,101314540,399773185,421509117,148218360,760019876,203219120,618814590,923102335,813501085,974911823,631888294,574496332,208607758,893526940,66597415,532158024,677874960,128738453,176781420,246686727,622548318,679887239,69269079,712020639,99428122,143308974,113065869,714860774,323123947,535515172,392882786,964235656,12859747,907609581,653199248,504370261,741055250,904209673,700643467,553589421,854023186,357788250,784908142,362175897,547822572,834398760,256701820,564557091,159301657,981100008,199740874,713298059,403252896,167788769,235636428,921449203,907414494,180215486,919870921,907385640,885858084,752089056,10675231,112577768,761750049,861913915,389184406,179511163,262030169,733700233,665587542,790285740,361557370,968522696,842939926,468045161,792991565,927570276,950324557,665857764,881972096,944788546,263702967,566659658,817144798,335263915,618916782,444288726,845213706,523862075,920500073,475619249,929581932,747528070,456242909,201422041,160300391,87900003,527587712,948116730,891977121,727971535,349481747,640485071,163756946,891512874,173689528,546444053,399880029,41653353,671579301,608490228,721779144,913556964,22904553,62935411,347235328,51563739,495535904,65235580,93541304,60346362,969265512,764922386,899332082,37668963,207104796,651026414,188077579,49840974,403801514,50704641,446253941,736106306,737034225,860046595,879992949,849420333,147370295,235551568,548201302,908463612,216468904,325070870,931600492,761292419,183567213,43610215,503476007,473234591,801054157,529645296,694436135,816154863,700575413,303327592,722575600,788635147,773286627,612396325,12162882,7393384,730916045,766373171,153866277,53681250,482936688,414434516,509726277,597955750,574811565,381698156,213854853,120857772,751205213,170464069,384896119,90626882,170393543,65159410,487611278,887762482,31498310,827207165,754993127,645208671,384937731,604174499,552130591,657044583,315213928,185273016,470247788,16668047,99466059,807130652,300751407,945472282,965870679,171772405,414723247,381287024,732989093,308821663,672649825,794199343,83649364,830774677,816588327,991449524,817704317,778921244,4066579,690349583,779231881,863331828,705444754,131692672,617402762,135487081,471498545,869243074,251600409,502250848,879176650,143106042,903174061,482494743,596007121,979961665,711423727,94863870,96565101,635812973,951082232,574980275,253802404,737253930,677438915,615614235,171014376,43066556,120365730,221731684,902096494,251034688,733316078,506943490,417003884,450187924,834626396,510829784,478384425,333241402,508546317,844115884,559538679,609949674,88598785,38200048,166588698,956091510,805650517,767887831,65405026,598697530,243255096,988964376,130786254,667387705,601811074,614828796,195017028,66128367,440453529,814087855,721851609,394451186,340353032,601565994,230434960,649127917,228417965,455416800,640333992,122114104,867275324,212212940,374938429,506196540,87019106,478544424,52999750,899660090,932794510,361326921,483638138,198518804,697117469,94465667,771380696,456063493,927166464,853454361,26368982,120680194,477149773,490494120,706456826,324350367,865732247,214549189,958917684,579369990,793096709,828909704,803481563,386013511,806142313,542195502,787836426,555152560,887816498,24365454,880992116,478696326,597146242,963070252,990127137,733141722,690080247,80658613,63118318,652038611,49056638,168886952,884857031,427075486,277085634,250351516,235538615,982643229,6444027,854261565,479040412,183769386,523629493,955733244,904030535,244943227,775404750,386662391,92853191,863183272,328096119,4279682,689912138,679121182,297572190,877493232,961776313,449139340,296800521,828967448,328789534,585404839,494059665,220511738,751009558,208391847,749461434,890703946,291391415,412491384,567561032,335957807,728938833,957498593,7473641,42440875,7262317,761870801,68045239,612468361,680467875,373698611,425022343,403081446,836805114,588173106,328798802,440547499,648920992,522587208,339538487,943725936,136834182,963035751,265731484,524526856,759128965,458449449,749063415,61042516,95400707,238165209,627214757,723187238,670420394,878540218,783798271,510078278,712425254,748793910,504874240,590642288,314190843,304528716,52243527,429530126,570107840,293422016,777182972,331382710,909553824,312989264,899235731,501044042,219357841,126361673,268572334,511591347,574587197,539778303,280730581,235652850,316182842,886513855,439111488,971674224,469986920,190908800,196503505,280901339,977144571,699451288,701253588,502776576,932561152,241024629,849449943,709126513,809575437,406885007,272525174,995501119,725971897,336997548,353594886,264182449,710241354,263693108,943879013,90938553,299110982,983947357,967822075,634869855,720276648,819244530,288557632,525744990,794006843,528901864,53876279,431347868,952139168,951652288,968410254,802957885,504089899,130783006,77350417,325738466,145989899,974484786,860057534,921595227,726332090,706964580,873285131,842085325,653240928,886709264,781261182,723831986,709734785,666769140,457436842,325233467,534798140,155658282,788523018,581773204,77957454,970300633,756263971,291750873,463654905,331158760,236225882,878484066,225252052,558254246,263430751,87128278,67865591,641567956,528909295,277393071,102102941,130271541,381011419,454127561,963773336,14097463,105895248,161123094,126139351,843484073,918587499,883986089,413368516,542558526,518951512,729277241,282077759,403542953,97389247,196291947,936489436,722106979,466972526,321561988,210490157,422632299,72290496,274595679,928857210,369112276,680108033,650899070,710518576,853328137,922801991,730700581,103560761,561701019,359036638,296278730,484681394,242348720,981121551,97121771,104814640,861534882,383165579,230709037,941844959,107560400,940937139,227052652,688964072,161397575,315102457,5844711,133125736,111341453,417024317,669662990,138945699,188589718,549705815,932487248,461989643,402328023,492413373,493932101,447614298,738344345,120054595,238728010,853636794,530477068,677254123,656918901,241274227,935788321,451387713,963197453,226974408,58228406,577767144,432754508,124885460,687130853,596055842,637013399,98516019,23197323,758083693,84815088,13282459,725131587,296404751,719791293,607765763,560314470,29453526,582432373,454945344,872746331,422052936,625075952,996073267,186745041,872470911,138616301,804981197,909775629,806373424,808160398,853559766,710883151,584877901,387383882,846374568,990462237,151666067,653618683,212835195,345332009,100835767,365661789,417604316,827886663,763083887,969747749,275096707,219826699,829495666,138493776,276903808,956714450,864017684,273249956,65364838,237219098,72789585,47437275,946343005,93476504,49527424,867480885,161322829,861483426,59062333,495530781,483866119,329038863,544215178,315819375,887519338,380648403,4945147,759843512,563146992,827835997,122205949,908986290,943863119,586031376,524491102,913358807,335361540,554284456,133015849,44784916,30139729,147315341,63592070,199286511,783523230,199446244,756470669,605292575,364569499,328776344,538360478,582624782,662158907,32065227,158667712,699285971,538165056,193692408,305349096,970281569,426153797,431441626,638541503,806527979,733334854,49114713,424947964,962295433,590399319,833619189,467963226,640427119,870548930,770179651,938811204,90850275,782282838,911839931,595454856,651132024,765535604,577479253,939820608,483712347,441795316,237354342,100794465,658608927,429297172,758478976,214372429,987327617,617840863,792368866,683497096,874848781,595538338,432164108,294223243,591335543,848724041,958081569,326426388,45427440,192999505,958681853,312783500};
int T;
ll n;
struct Mat{
	int a[3][3];
	void print(){
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++)printf("%d ",a[i][j]);
			puts("");
		}puts("");
	}
}A,d,t;
Mat operator*(Mat a,Mat b){
	Mat c;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			ll t=0;
			for(int k=0;k<3;k++)t+=1ll*a.a[i][k]*b.a[k][j];
			c.a[i][j]=t%p;
		}
	}
	return c;
}
int calc(int n){
	int i=n/1000000*1000000;
	if(n<1000000){
		++i,A=d*t;
	}else{
		A.a[0][0]=db00[n/1000000];
		A.a[0][1]=db01[n/1000000];
		A.a[0][2]=0;
		A.a[1][0]=db10[n/1000000];
		A.a[1][1]=db11[n/1000000];
		A.a[1][2]=0;
		A.a[2][0]=db20[n/1000000];
		A.a[2][1]=db21[n/1000000];
		A.a[2][2]=1;
	}
	for(++i;i<=n;i++){
		A=A*A,A=A*t;
	}
	return (A.a[2][0]+A.a[2][1]+1)%p;
}
int qpow(int x,int y=p-2){
	int m=1;
	for(;y;y>>=1,x=1ll*x*x%p)if(y&1)m=1ll*m*x%p;
	return m;
}
signed main(){
	d.a[0][0]=d.a[1][0]=d.a[2][0]=1;
	d.a[1][1]=d.a[2][2]=1;
	t.a[0][1]=t.a[1][1]=t.a[2][1]=1;
	t.a[0][0]=t.a[2][2]=1;
	scanf("%d",&T);
	for(;T--;){
		scanf("%lld",&n);
		if(n<=1e9)printf("%d ",calc(n));
		else{
			int y=qpow(2,(n-799039878+1)%(p-1))%p;
			printf("%d ",y);
		}
	}
}