#include <bits/stdc++.h>
 
using namespace std;
 
const int MaxN = (int)1e5 + 10;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;

int PW20[] = {1,479110773,197827612,442594703,795672203,565437072,752427726,907018616,195213459,586791717,153899624,302904583,890498730,899285573,11776108,167317064,307986623,986271630,729536477,980465247,101545718,105258485,760145594,584526582,580697026,58133705,144936577,956359303,718656932,802114511,709615103,150914953,282953816,558096228,333734853,278599635,548007260,110318720,845586358,783728024,771954800,360097394,586939789,43782679,32863596,772902594,672903470,409315217,644781445,367554847,633370336,152047885,205430652,788645737,32284039,772578737,296378150,552824209,253055333,356711664,880825479,167694456,879564955,543896921,428521829,302397856,527528205,307641357,327278952,581729806,78808933,544627753,910523922,50718987,897246867,11033732,830590183,837728552,303337299,786296965,71640537,819938837,257900312,974321464,499876330,194230159,966998587,264381692,934491111,418765518,630279931,833979349,768447368,915095601,694984474,230316580,906086269,706466114,607517461,313230247,716647043,336421027,171143312,932123955,485732840,814846482,134538511,552267060,166857708,901285016,686369869,198568365,182542451,191718245,917173460,319690806,111481882,286629596,342946426,108282016,24604808,497877588,376285926,612902325,648710497,495254886,602513235,742886602,644088549,431710057,673285502,54864701,122519990,705947748,874299028,206026084,672437727,922127879,819930688,984238470,877122560,795666832,261493300,220331108,730885442,639841064,624299264,864611572,705952151,399017777,240995623,416901393,266813160,439341274,923492857,480060850,320520789,905405170,840370841,419755053,505721807,178649463,714814732,402979784,464109354,794952119,565987140,255265482,545134499,376599064,401087803,991043324,714392749,803072164,575499118,355703439,425098911,424981941,838256425,942642765,640595245,863661825,689812958,219318815,252547953,134408561,107751530,468858264,720032771,84313798,651576318,200233197,123394114,928353986,736600434,855483082,836344287,33792966,948888707,719380925,645562989,514907237,615480987,384187968,37299113,736551507,402856598,724839716,202910870,95285029,579952836,614470685,815392851,406639351,426051279,190448375,524122806,971798878,379917538,33278786,773352010,718554798,302767460,784432530,183835179,98741469,208588830,880905512,839921557,616725320,725514166,461498768,927264461,575301630,728027548,845933738,282887726,127330306,906949298,194883122,572479092,374491830,897523114,923816199,114539797,295792331,360860826,80032342,972209874,989799062,389931196,424632863,809009860,675984428,567942911,204327248,48975009,255420779,10328245,411044774,30198456,496287653,394748456,570818836,844522071,420033550,417735971,574722969,10953289,722947531,991247834,657893098,527719078,617576043,276799908,959884172,418149048,214116120,46863387,413798880,875545747,705648659,113316303,143794792,466238785,120270644,812687092,129672150,588180689,597836683,314876008,536010782,302694720,267048460,203439029,760270614,12947749,988576142,247515434,83059312,898605906,232302969,268693059,296088441,850860773,813811616,688797805,484180143,960149099,797019116,89513574,332924283,462047496,421670891,124419288,832515284,459485266,434360245,285672688,414585797,285063441,615511145,406778959,122380047,507511145,284986700,175937721,918112741,962514886,827408149,78948092,120220949,402989520,86562627,844569069,667985385,919779668,640428956,12888118,134271362,589266841,718509470,169800935,654498563,251278029,869376354,77168624,837180126,500383300,981117711,630752176,499390928,868422347,49150738,911859945,58514045,135063822,709780689,186817593,765685149,44074170,510218547,740948431,44572552,693816373,461182057,276299031,394916076,118026933,708613391,143631094,991469241,136068156,945502562,182297206,671016360,684808132,182513379,483423092,672877653,206575259,329358190,900187485,764249279,263262247,778964492,289200377,206448316,570926991,69813153,465259638,247503853,501236042,857047371,543083408,588974621,969403452,985426965,631293248,921744953,849353138,648616029,859067949,223793635,706776275,82941700,722766273,331363294,820848208,697604272,666414223,284720762,416079545,39000948,213212386,354567928,875947160,997024661,687976189,410066490,630025873,910064569,81349685,190827935,807849729,419683982,624212281,372535431,66898004,184236214,286246544,4411898,846380645,239618011,671307520,576498326,669620106,356246510,589881457,863306355,184526811,438573429,114573846,538388017,193174662,986969306,814860177,556528819,801394437,501272866,632028822,347016701,696203807,802401624,640020539,29681516,975026737,389717031,666651581,58782449,382079949,431780251,374650047,366164227,614884903,120174166,163853159,117455216,936723562,735573004,77425456,814369905,961272828,463082896,712562594,832450278,384793643,452704593,974610874,947719647,483018308,299097173,755039997,76353123,525422858,886098991,560753060,158075570,4965654,309736856,465961847,141946358,829858538,838670740,721168739,587087284,486751652,616291290,278164612,343663449,549666064,971450962,77385300,642303990,995740964,630313639,699802583,141545981,897239892,213415451,983006143,739696736,489760224,862747373,888288430,365136519,644033321,102124033,50006441,434778525,738400314,747553928,796138385,382252287,423599542,589408252,251555909,170045642,413606380,52388843,890605233,633585203,245789461,830640714,784029545,730329299,539077703,183448888,920424065,183056671,531685729,831104011,366274329,668844492,335758123,725501755,217736687,688789114,532481148,640385240,206482265,902445713,119365929,112726603,522934416,524258998,25738530,917862448,890647823,961264438,723725566,938909534,462918099,695057205,435703721,106033918,61584670,642108764,116626004,537203674,706919547,241130455,880194336,759207633,367918438,997216779,490819081,654962664,38581610,861290482,719987771,99679718,409098632,438737616,874509756,260292094,489167447,18048787,230750775,406712808,465857182,13241335,202993493,664405513,690624697,116360671,639361133,513512181,261621401,789033563,645632860,463493188,28462278,918464813,449405768,389932663,280131933,22114627,962409186,819056543,700506069,860441330,851721141,388470596,234487586,800945289,857307806,756376224,822745194,120072381,874164723,234108748,435194050,240957558,65454807,958815097,72089508,661297671,118065831,159331086,242028805,40106016,193203800,316575253,115778278,880894561,97883156,206561470,870955542,55264706,825932333,739331884,967233263,63359188,326839841,772559684,798884084,343359156,496238105,414334025,608368074,162331330,453995274,141888627,286016088,52882308,286548703,635457436,239376521,211545650,186810857,475540810,477289069,192320006,93026536,260482223,340689513,783827451,318448412,765938035,450166928,343356583,744227807,403891912,812205228,897767347,584419203,145363181,527133458,768655822,471471432,651727656,865889922,958329404,325047726,175615136,970486414,742744578,416140312,163140041,603626643,506696864,488368404,911338365,463281970,209919143,166205885,482081902,99735829,793494254,743796848,305715944,222962105,728492350,489886840,951956900,29034079,935659294,474983154,481931234,438294774,503058080,885552039,967073521,950794367,948664951,810007965,530722172,295236000,187272771,447591176,820218784,880530468,220430354,558329750,238884178,377885720,147517734,73207037,840589648,209929033,571717689,997150890,361317860,991526841,916399784,815873997,637011555,389588343,859927349,19227599,755338984,968037345,409237866,947638542,204046149,490738228,111904454,82780539,752019318,235808936,816417328,370594206,263091513,280819710,389929601,242955276,273970925,737438085,470788009,332203722,926760446,560738388,644863324,478262711,560299898,363481149,49284046,210339939,61629937,549318339,179075723,471484130,400280622,880889514,25828751,770610699,95505132,297684277,65049920,236625341,244310350,821038517,789064876,41162788,39464379,996300311,801982947,980317369,159151974,753855934,741113510,171314982,877949122,551647153,46978625,180671370,133737817,433675945,786003780,980641815,731920617,130809591,821117862,833082456,672927056,715928095,606805415,406146732,357818925,550734725,965651866,729572962,336895785,841919019,172884404,860268839,555954092,906087972,632106821,507938338,52004178,746399267,275747902,555551723,584816188,934251193,121133533,225596349,398768297,686184286,384605111,741081653,139526362,683757752,812292382,317785090,51994757,43838425,541828298,870883950,557044197,951633170,499576510,203274828,292783931,521457125,496257557,77025181,751049762,514433823,869579691,23736178,510039788,378877239,578726592,907856622,894841618,311452922,167985563,378384355,546140282,843826156,48775195,216094688,284140780,793678591,585741123,253973919,802157914,554350057,462698487,220713655,118481292,998799082,898962614,876721939,960020393,366301026,489061736,739478720,676205034,278391484,162194626,95341554,316207087,820160711,480804800,777599101,756322352,167362808,751033323,412491608,781488787,209464493,454786231,158915696,419425461,428932568,780811580,42484681,212084337,929979278,637620285,488395090,461337141,690898849,292080724,474466512,735679671,385891312,492111395,210127252,429366193,188299420,40137700,338829272,286589985,286249969,958797943,405946999,126465174,848583720,198456367,734563617,894984568,195973849,624923010,290735322,886762945,72702746,591453982,526344282,47909488,669036567,536837923,463810669,594720335,426110536,857325306,194845029,805930960,527320666,137619748,382799483,920306881,66626447,300963395,813790714,315490657,491463064,845731750,656748427,323917363,88705520,959068577,69979433,4036409,22596948,147935717,230036076,418757421,270378103,23816192,79162258,357313004,351044536,823061809,776403925,63099651,355018169,187983441,98255656,968254694,655909705,580978144,719475117,47177502,293206303,495454140,339808322,685612124,408422788,299736832,270841128,287931637,208567365,768235055,470259699,321491925,621796324,354833247,66238921,420845473,471159443,361816498,827481694,280501725,351843646,30193798,798322643,913738214,964706696,603426439,614170612,609412798,682039216,706667637,447148876,126804254,728355361,584663774,745406332,423689229,597005513,816469159,160895738,865977314,406710323,875594614,411628959,355164238,418994897,579510612 };
int PW10[] = {1,148946603,389943979,625787527,693958306,578795401,207505547,112956119,95342747,186931595,873722010,444866562,734359352,96018946,730228573,600532071,341874336,643633468,964640085,772622221,414709085,11601692,600356052,909944405,94874326,470696122,926413457,427733619,92979974,177384965,775077686,582684349,797294476,959584914,229858758,934242314,75093816,721212272,204357197,78683621,977651864,40092531,256320671,956883969,650035002,701254678,394812327,517533503,670946317,12964933,714955025,526099228,302997640,879103644,542144832,495151286,504523751,318238167,587793250,240981101,129896691,729956983,192906465,457359061,10365237,829632849,730764996,983593854,259457228,463879580,158413731,935839491,161968289,271399885,642372025,316227165,673363768,124813389,170333857,198443228,492052376,390252025,30734084,376072493,921988246,286339226,719804500,348626462,867321504,825358782,974576851,302767783,460017525,189591246,852564541,331298086,144681790,985610350,486517866,932252924,194625837,74259712,764733219,373974159,202916617,582835871,484316259,50757350,806861112,883947996,311230238,376484712,541300510,602293433,226591179,145565035,327056186,553838809,632668971,394318262,214637431,310281,300601938,206901155,978305904,75636732,214560558,28178012,137314103,42674826,321822188,337087117,640757691,752502913,854375282,50272981,690217620,110105877,234686559,488118722,993675998,348702153,784570259,74866659,457951439,700539547,62407946,491839281,614107920,919110751,183939892,877806329,881226504,325576061,964616654,804791758,637401095,184159196,463401986,154998501,32436603,795890362,950524138,433561834,912706975,509043711,1221416,762776373,811720283,892727810,772348019,958559173,593420402,410078742,155854581,239440273,35095914,132888223,256003726,76126583,856475984,474898043,781056786,210447680,825812778,136079085,308218636,492136682,482476644,647597540,18954449,770524347,211074360,682327424,227128215,832893820,280296532,981836291,222881220,359113860,162796057,502208938,787721416,202250852,148383717,432954601,620760591,658501113,166498618,381698833,146445091,677788387,89819422,696675387,560988344,576494283,500702601,10168746,162867638,248923647,367486824,698907481,377537785,186263565,75216420,170398650,895623857,132106861,41205107,670940001,266226972,828800902,52106360,262367625,207376513,937119157,64308673,319737913,658292414,159616716,463795179,916261932,274298289,69271681,496825176,732074181,640677416,64030780,101680171,956894708,187593419,309615843,727017740,935729473,354714144,415018570,750708475,411852093,761382296,779703353,964120711,780177212,651977628,242828720,701658576,629449708,109661159,999757285,382879705,18191698,600934757,53230141,623661887,838973635,65076001,217924660,589716021,447773284,99094089,830611578,89552130,461544995,655683079,577998275,998473679,630927610,590587169,982175250,14134088,379366496,475675638,914005831,696675659,74464073,641255829,714908755,766826662,595215611,690432039,91550975,632134483,222931268,838648626,78920437,916141001,12776980,754277331,385927278,660758742,334529043,210902181,205349002,63237954,363036716,233964153,569185104,125554403,687636702,144075256,807338735,206814678,523008433,890400803,986966998,596170134,647772197,585612522,215587801,382412513,357330031,894773042,128962498,857034619,259882499,134240592,23146216,221371398,502653375,168655541,733232540,277574155,178439376,710594162,800647591,44807207,225850654,463150553,64028552,248651011,161715572,932993028,170520897,170873335,613373991,688482776,991379745,267117727,759227442,598689097,627078549,33910514,830927957,666532806,546813446,686301910,411355371,707364825,27922366,534310111,424917208,244814606,673233297,912709414,789805887,74579540,58544037,376016766,574700965,878373610,458531482,134378704,336235755,163822054,268977396,137542905,323095879,283480806,773837504,687975650,296915505,538207630,636031511,301264009,432605677,576619216,846524944,880956141,675431062,541360259,12813780,989229364,324254028,641591139,11077,881509888,409425150,848388062,976101760,316612000,538928033,214921406,111601127,641263325,218637024,786872785,498485166,601857401,741846505,93703903,941993370,527875133,318146750,336282111,732502394,511941388,143941454,454103632,922901752,900906903,881791362,5264497,939164795,893243557,535467727,394488695,630848835,322017975,145444544,602039742,814194015,868281028,664655328,578463720,449621725,104962779,264052794,403650420,437666754,798013837,336115568,718572607,72301385,612561840,556756492,601107767,304834788,830996429,338262029,790756634,609550711,124151184,985784680,347637094,865636141,733444096,824897853,166283235,815729451,843004050,683804034,269044493,7694438,394071694,748886009,293969245,122724695,296505103,554871120,848282191,850405930,557900279,788120787,155621170,464130802,821650671,441446088,754975806,863729458,779584205,274390689,735292547,320232559,499164220,387702962,758708820,614088760,102217242,857354556,788872939,640176616,605770531,158363959,565566866,870381364,574824070,949807573,511730249,707350780,72897875,771163395,239162016,600475065,491883155,497322197,321125634,985707305,604310644,950472220,423881411,801346968,872444355,74142711,863357605,538806548,436982616,767643923,844077898,694422756,828074505,687284334,127836740,28308284,709044298,824351528,913968878,672893528,474708956,914932473,873806645,540523225,642790996,622995850,891045752,948952804,573721747,684698113,297975940,728054299,876507806,292813005,103677501,473382226,989717567,502169425,460638272,345916481,406002455,58601563,678240968,491879895,931399819,103762991,918383565,300248918,77478162,955802930,564401604,55091305,677147281,529624941,273824578,425511854,745882154,298946578,959885002,317746943,442193340,401181655,279885457,757436662,2835867,753253057,254153990,184408359,445585491,765957965,128935043,528077877,348013996,137807074,397988357,393748180,437900369,958430110,98131974,70669354,140822742,899219950,964779565,844663236,800519282,855256664,904199381,291910768,968367292,590063957,332671924,646421708,838081712,165018375,216777643,305178678,77943545,172261653,861910250,929730536,73207780,67842990,827128096,282672455,639198658,84813498,327218520,651520958,798112850,986015178,241495064,172278509,505832841,825394549,347689056,428967047,2339053,996148208,627527194,182145681,246161783,109618422,468829429,347165837,736837514,905018841,74350756,459161824,433349721,402125987,322405068,332436031,185646174,783687360,268945097,311246285,522606323,972287724,614668908,175449609,75299866,168545585,160667711,597719370,85602227,831633761,773980729,565040994,22916830,956134809,813712617,271991948,414366712,716649745,311368427,158462598,509437339,554256697,630267734,302673943,310889844,846858037,951441929,284318893,984632155,665216174,684385106,968937073,533873831,1415242,486847361,92864863,785087054,934025226,555168097,563291684,242646778,59005243,442519119,76220724,838530853,190768112,44223702,138875516,203276896,915642474,110142977,153619177,409638353,710765179,201674531,93797041,530606473,129937002,916428488,224533901,578183376,163442585,650879236,486811558,357674985,620904644,863352880,766112301,951694742,921599547,891105001,886172176,364371790,969625797,633360322,776528097,372575944,829860792,66054961,983376856,144725681,400916857,517580350,372408212,718421277,983027182,390632840,130958482,891395906,197414581,16788726,688893417,572954120,251477377,773303431,329428467,747676851,318639671,244265541,307229569,323378507,763698818,859962853,763918551,343650749,323656370,513358498,863041273,962316171,679081052,149038651,626760953,188915261,183840381,52498943,166203856,583412675,480111680,296046019,553058121,807880074,811371685,405178670,82108108,679749063,117558798,492293313,137687827,962544750,744409867,153190561,512893792,483432067,656879460,462594639,562748024,933026637,116866082,797971811,706221710,933025869,725875783,320998032,101404334,973050592,211010923,956739056,351105551,749821407,647546971,938240073,693588329,761843019,904996961,122699929,484961028,202354805,594496995,279119836,111099451,705779758,684397602,205675127,273801304,842297901,189778433,720145135,774384215,433678366,958126272,460486452,272807312,111525082,996917479,928961547,774715186,439474800,105896454,982635350,345694678,602848505,314832863,128361394,458811631,375970462,751243932,912496386,993084113,89202611,794175458,827041029,948879837,387016722,642581591,459812965,672694849,912778670,235671043,34600122,599210576,152120675,628712026,882436045,347454185,191618715,470688453,654923044,947379605,928469011,211173505,993178490,222655543,536823927,776063288,651466741,360194524,393453722,919381208,835065482,955796491,497231600,205828101,231289131,132123883,410263628,297304073,421437002,387002943,307353218,421763935,946420677,861347230,13896489,815688029,176857767,424418960,898282553,866944528,531139297,454178340,425640780,835486111,216031214,242026237,585680016,217540312,261146906,260381710,916350340,345484137,236325795,120124917,197561565,784130834,214301541,326178821,18412474,435928497,324535215,489755726,176866621,197632689,462248448,589669799,837937613,108622919,679741059,948956737,380707244,334356782,520302404,66052687,278804000,412123644,360090420,456403552,191675550,850810703,120814368,581227681,48514427,47559068,570859677,83633968,341811739,33190738,641557485,351068806,706932483,156138912,375721416,195812852,924982150,113725814,550136331,115747034,400944613,679464280,657413575,76899099,489633684,435670541,654880701,101412918,530681791,490103230,716833220,289162556,129508808,875149952,553558779,115722844,382643264,934678301,857241411,225594468,428981501,876523751,246381215,760379137,655430395,154829275,394773767,136562024,431221329,646092730,682862978,175592894,889161334,291185489,125846244,412898542,784053988,263727525,691378349,750449262,516318917,213461315,518602586,951006714,488948016,516999633,548559333,622353463,530254158,7868389,804428784,893502221,659316430,863166703,334599680,352024645,678000817,816473232,495554505,604418402,138405937,6876353,413209396,431058843,908527086,245934704,464192546,380641924,142316925,379772421,625075186,922573390,496794973,97855258,162762118,403485106 };
int PW00[] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,999999937,999999307,999993007,999930007,999300007,993000007,930000007,300000007,49,490,4900,49000,490000,4900000,49000000,490000000,899999972,999999664,999996577,999965707,999657007,996570007,965700007,657000007,570000028,700000245,2401,24010,240100,2401000,24010000,240100000,400999986,9999832,99998320,999983200,999831937,998319307,983193007,831930007,319300014,193000119,930001183,300011767,117649,1176490,11764900,117649000,176489993,764899923,648999181,489991768,899917652,999176464,991764577,917645707,176457007,764570063,645700581,457005768,570057652,700576485,5764801,57648010,576480100,764800965,648009601,480095968,800959652,9596464,95964640,959646400,596463937,964639335,646393287,463932828,639328252,393282478,932824759,328247527,282475249,824752476,247524704,475247026,752470232,524702271,247022675,470226736,702267332,22673271,226732710,267327086,673270846,732708418,327084131,270841289,708412876,84128711,841287110,412871044,128710412,287104113,871041116,710411104,104110991,41109903,411099030,110990272,109902713,99027123,990271230,902712237,27122307,271223070,712230686,122306811,223068103,230681016,306810146,68101439,681014390,810143858,101438524,14385233,143852330,438523293,385232902,852328999,523289934,232899305,328993036,289930339,899303376,993033704,930336977,303369707,33697049,336970490,369704879,697048769,970487648,704876417,48764121,487641210,876412072,764120664,641206591,412065868,120658652,206586513,65865116,658651160,586511558,865115545,651155394,511553898,115538945,155389443,553894423,538944195,389441915,894419129,944191234,441912277,419122742,191227392,912273913,122739067,227390663,273906616,739066146,390661411,906614089,66140827,661408270,614082658,140826538,408265373,82653702,826537020,265370144,653701426,537014218,370142145,701421429,14214241,142142410,421424093,214240902,142409006,424090053,240900502,409005006,90050032,900500320,5003137,50031370,500313700,3136965,31369650,313696500,136964979,369649783,696497809,964978048,649780417,497804128,978041252,780412457,804124521,41245154,412451540,124515372,245153713,451537116,515371132,153711285,537112843,371128395,711283929,112839241,128392403,283924023,839240216,392402104,924021019,240210127,402101256,21012532,210125320,101253186,12531853,125318530,253185293,531852916,318529125,185291229,852912283,529122774,291227705,912277036,122770297,227702963,277029616,770296146,702961411,29614061,296140610,961406086,614060797,140607928,406079273,60792702,607927020,79270158,792701580,927015751,270157447,701574456,15744511,157445110,574451093,744510895,445108901,451088982,510889792,108897885,88978843,889788430,897884244,978842384,788423777,884237721,842377154,423771484,237714812,377148106,771481039,714810341,148103361,481033603,810336002,103359964,33599633,335996330,359963279,599632769,996327655,963276487,632764807,327648028,276480259,764802576,648025711,480257068,802570652,25706464,257064640,570646386,706463825,64638201,646382010,463820058,638200552,382005478,820054759,200547534,5475326,54753260,547532600,475325965,753259622,532596171,325961675,259616729,596167276,961672725,616727187,167271828,672718273,727182688,271826831,718268296,182682911,826829103,268290974,682909726,829097218,290972124,909721226,97212197,972121970,721219637,212196321,121963196,219631953,196319516,963195153,631951467,319514628,195146259,951462583,514625767,146257635,462576343,625763402,257633978,576339766,763397625,633976201,339761968,397619659,976196569,761965627,619656221,196562168,965621673,656216667,562166628,621666245,216662408,166624066,666240653,662406488,624064838,240648338,406483366,64833632,648336320,483363158,833631552,336315464,363154619,631546169,315461648,154616459,546164583,461645795,616457922,164579178,645791773,457917688,579176852,791768485,917684801,176847947,768479463,684794581,847945768,479457624,794576212,945762071,457620647,576206442,762064385,620643801,206437968,64379666,643796660,437966558,379665552,796655499,966554941,665549347,655493428,554934238,549342345,493423415,934234122,342341157,423411549,234115462,341154606,411546039,115460362,154603613,546036123,460361195,603611922,36119178,361191780,611917779,119177748,191777473,917774723,177747167,777471663,774716581,747165761,471657561,716575582,165755771,657557703,575576988,755769845,557698401,576983975,769839715,698397101,983970968,839709617,397096114,970961119,709611127,96111221,961112210,611122037,111220328,112203273,122032723,220327223,203272216,32722146,327221460,272214579,722145776,221457711,214577096,145770946,457709453,577094502,770944985,709449801,94497961,944979610,449796037,497960342,979603392,796033857,960338521,603385147,33851428,338514280,385142779,851427769,514277634,142776305,427763043,277630402,776304006,763040011,630400061,304000568,40005659,400056590,565872,5658720,56587200,565872000,658719965,587199608,871996045,719960394,199603891,996038903,960388967,603889607,38896028,388960280,889602779,896027734,960277284,602772777,27727728,277277280,772772786,727727811,277278061,772780596,727805911,278059061,780590596,805905911,59059054,590590540,905905365,59053587,590535870,905358665,53586587,535865870,358658665,586586629,865866255,658662494,586624898,866248945,662489394,624893898,248938938,489389366,893893632,938936264,389362577,893625749,936257434,362574277,625742749,257427448,574274466,742744625,427446201,274461982,744619806,446198011,461980082,619800792,198007878,980078773,800787667,7876614,78766140,787661400,876613951,766139454,661394491,613944868,139448638,394486373,944863709,448637027,486370242,863702392,637023864,370238598,702385959,23859541,238595410,385954086,859540839,595408334,954083305,540832987,408329835,83298322,832983220,329832144,298321419,983214176,832141697,321416914,214169119,141691176,416911753,169117502,691175013,911750088,117500817,175008163,750081623,500816181,8161775,81617750,816177500,161774944,617749433,177494288,774942873,749428681,494286761,942867582,428675757,286757542,867575406,675754004,757539998,575399931,753999275,539992701,399926975,999269729,992697227,926972207,269722007,697220056,972200518,722005117,220051121,200511196,5111946,51119460,511194600,111945965,119459643,194596423,945964223,459642167,596421642,964216385,642163787,421637828,216378252,163782506,637825053,378250488,782504859,825048541,250485354,504853526,48535225,485352250,853522472,535224664,352246605,522466029,224660255,246602536,466025346,660253432,602534278,25342738,253427380,534273786,342737825,427378229,273782262,737822606,378226011,782260089,822600841,226008354,260083526,600835246,8352418,83524180,835241800,352417944,524179419,241794155,417941536,179415332,794153313,941533081,415330747,153307442,533074413,330744095,307440929,74409269,744092690,440926851,409268482,92684792,926847920,268479137,684791356,847913518,479135124,791351212,913512071,135120647,351206463,512064609,120646055,206460543,64605416,646054160,460541558,605415552,54155478,541554780,415547765,155477622,554776213,547762095,477620915,776209122,762091171,620911661,209116568,91165666,911656660,116566537,165665363,656653623,566536188,665361845,653618408,536184038,361840345,618403429,184034248,840342473,403424674,34246712,342467120,424671179,246711762,467117606,671176032,711760278,117602731,176027303,760273023,602730181,27301768,273017680,730176786,301767811,17678089,176780890,767808893,678088881,780888768,808887631,88876254,888762540,887625344,876253384,762533784,625337791,253377868,533778666,337786625,377866229,778662269,786622641,866226361,662263554,622635498,226354938,263549366,635493646,354936418,549364159,493641555,936415522,364155157,641551549,415515448,155154452,551544513,515445095,154450915,544509143,445091395,450913922,509139192,91391885,913918850,139188437,391884363,918843609,188436027,884360263,843602574,436025684,360256812,602568099,25680948,256809480,568094786,680947825,809478208,94782024,947820240,478202337,782023342,820233371,202333654,23336526,233365260,333652586,336525839,365258369,652583669,525836648,258366445,583664436,836644325,366443194,664431919,644319148,443191438,431914352,319143492,191434899,914348983,143489767,434897663,348976602,489765999,897659962,976599564,765995577,659955721,599557168,995571645,955716387,557163807,571638035,716380315,163803101,638031003,380309988,803099859,30998534,309985340,99853379,998533790,985337837,853378307,533783014,337830105,378301029,783010269,830102641,301026354,10263519,102635190,26351893,263518930,635189286,351892818,518928159,189281555,892815543,928155374,281553677,815536756,155367504,553675033,536750295,367502915,675029129,750291248,502912431,29124275,291242750,912427486,124274797,242747963,427479616,274796132,747961306,479613011,796130082,961300771,613007647,130076428,300764273,7642709,76427090,764270900,642708951,427089468,270894652,708946506,89465011,894650110,946501044,465010377,650103742,501037378,10373745,103737450,37374493,373744930,737449279,374492741,744927389,449273841,492738382,927383792,273837857,738378556,383785511,837855089,378550834,785508319,855083141,550831354,508313505,83135015,831350150,313501444,135014419,350144183,501441809,14418055,144180550,441805493,418054902,180548992,805489913,54899074,548990740,489907365,899073622,990736164,907361577,73615707,736157070,361570651,615706489,157064848,570648473,706484695,64846901,648469010,484690058,846900552,469005464,690054612,900546078,5460717,54607170,546071700,460716965,607169622,71696178,716961780,169617751,696177503,961774988,617749817,177498128,774981273,749812681,498126761,981267582,812675757,126757514,267575133,675751316,757513118,575131131,751311275,513112701,131126975,311269743,112697409,126974083,269740823,697408216,974082118,740821117,408211121,82111182,821111820,211118144,111181426,111814253,118142523,181425223,814252223,142522174,425221733,252217302,522173006,221730025,217300236,173002346,730023453,300234481,2344789,23447890,234478900,344788986,447889839,478898362,788983592,889835871,898358654,983586484,835864777,358647714,586477119,864771155,647711494,477114898,771148952,711489471,114894661 };

int getPower(int x) {
	int highest = x >> 20;	//highest 10 bits
	int middle = (x >> 10) & 1023;	//middle 10 bits
	int lowest = x & 1023;	//lowst 10 bits
	return 1LL * PW20[highest] * PW10[middle] % MOD * PW00[lowest] % MOD;
}

void solve() {
	long long n;
	int w;
	scanf("%lld%d", &n, &w);
	assert (n >= 2 && n <= 1e18);
	assert (-300 <= w && w <= 300);
	int mul = w >= 0 ? max(9 - w, 0) : max(0, 10 + w);
	printf("%lld\n", 1LL * mul * getPower((n - 2) % (MOD - 1)) % MOD);
}
 
int main() {
//	freopen("input.txt", "r", stdin);
	int t;
	scanf("%d", &t);
	while (t --> 0) {
		solve();
	}
	return 0;
}