#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

char*mmap();
#define rd(v) long v=0;{int _c;while(_c=*rp++-48,_c>=0)v=v*10+_c;}
#define wt(v) {long _z=v;do*--wp=_z%10+48;while(_z/=10);}

#define MD 1000000007
#define FAC_D 166

const tbl[]={1,68366839,609526889,243293343,850681817,752436308,627343983,190880063,644579365,950738051,254836633,403178049,744984158,498552403,936680318,76790020,765187669,832139566,46447535,674747968,706063598,894554119,527618896,628073133,695171571,301205808,498492116,8839635,557595304,465525125,856656534,701541959,380585769,586873324,813143186,174509787,803439101,732225480,823030319,20271058,856081717,573764774,884034168,708288815,267754258,587119459,959021374,167321805,181461318,138333864,523505981,603427170,619775485,253028327,154516160,944741134,824380570,917343858,183524564,922126153,789312383,780548400,147882005,388623483,497138987,527306637,174898109,611029984,576727190,481785303,516472990,399897561,38783943,987490815,196203915,594489106,372057568,549898621,570476898,102951782,630692890,893910436,778655091,430113260,176532575,409105684,638514831,791133143,477718669,499927385,650585733,418935906,378281099,166534132,979071684,73245686,295290464,807744779,860926658,732116934,337033639,176883427,794504901,331596885,621856749,152544773,587850130,191158880,708122528,98604424,782854771,132437521,536918894,128176375,479320588,217519450,519423500,248415441,826924473,618562191,229599108,269703157,703329349,146217256,824005047,810441034,335273216,574943534,370075285,323862226,633348622,389920154,294275752,94726934,965309466,992679742,339432232,877566242,127489781,595525651,356983515,241361500,506519068,120031047,606712360,649238414,350780972,424976811,33963566,812839593,150072577,377257290,729351044,60967982,788311873,703776505,257075671,319454336,984731276,215024281,619562099,103996240,805130601,68196481,669426822,511458517,795618020,272395087,517660191,150941460,634649985,241300027,395410716,337361469,311396547,814561133,815127434,115168444,921677199,226970048,357229919,112205714,925184865,782882591,868022151,656264328,979331547,505662263,934582796,140561103,82402864,851499158,754528285,446511467,571180855,682133312,507225879,591265686,827131332,741977343,19981188,160266042,972474224,498061606,952415806,744458964,986889973,155933482,252719286,150293916,265595241,557595366,740025372,747367815,289660824,489750393,171897179,975650481,226955158,774192313,204685824,431477108,476947133,408715699,749258033,997479967,96718575,668568363,859013401,806666944,533535352,699409496,954511743,558707931,372679583,156592755,381978292,57632117,409118405,14661383,587624097,481373430,372232759,495226857,366453916,806632990,969885413,877389448,159163082,633018975,104310832,604737408,534710823,113038291,811336044,341139738,991902974,755936568,749659553,603206166,606508671,750917867,103989789,141069798,231635929,802809859,477973972,882316366,868261846,607649209,814558589,270091009,287936902,21044399,766050426,4084182,917241473,375095027,270609794,306535613,209835126,412081637,320682170,612036349,538718903,910337291,860895463,793153770,993474710,327703201,852943921,389453599,382452432,237509740,287950649,493754395,42593459,460147454,761070162,332372587,819757880,771996375,347685708,329935613,776251350,550248457,340964200,490130150,775214565,508212034,921833637,77502549,417945923,37794756,84380731,264239841,812375424,788852222,510019096,465261944,399978241,553044426,796961649,93958473,973022868,553027780,1656647,684357627,647322879,373049885,298209407,142120574,168640613,318482232,245865675,490269040,349206173,857395453,394364860,611440095,311475516,187813915,153486050,48670662,573903765,530502765,23068320,834476258,409189701,279476993,698268536,641500618,512310729,645309967,473890339,976639989,273243572,972295162,455918568,282913941,872453833,203136026,871523252,979157516,83397923,654227353,955272267,304170032,934568648,119012845,387225741,867896534,503948842,252200163,956254033,296276994,310664588,231153478,326355975,660392510,426241232,556403653,27261911,63993593,476837363,551299243,166629235,308734049,252517689,705288584,215154331,449257259,643771827,782885836,36350007,27870515,536677999,461348259,664962190,91098413,223530088,664442500,410123131,677468034,297543615,999009280,31127299,662280609,308960957,712158567,106607223,122826855,929192366,286663121,738914211,908382414,974718120,97991955,599212288,143530065,402874610,41483211,521363316,701046708,325054713,363234707,57639089,557417303,719589501,980318197,411336341,434944733,533947771,178085570,590035974,426317509,860797663,283339489,222021471,136640683,385478408,555925775,391004236,88861762,9606628,244965546,965261595,315532209,720252138,420478339,225908460,171665589,387734060,726877617,867350273,161226077,424769893,104164269,550997066,129288135,17051304,62905880,105243875,551221720,265038966,566674004,478614705,120517873,278034492,798848246,916535327,817021630,884792830,612965923,336034775,436392689,734755535,12932837,146161890,988885181,837855463,630334941,395223137,620431180,500227668,567221770,226479634,163958028,199766598,204011730,469272984,733733323,305326145,521192468,232295053,297929528,168654739,858107200,257610174,287350607,429183481,647481333,794696645,724475421,995974088,335887180,284438073,519818932,665811382,459613371,855586171,821496387,843054228,397900322,515776741,742017110,533798589,298535637,281838970,165549398,7358995,740681196,199801822,978628009,97336742,867776004,165726783,996063229,247052621,656819284,622570968,94839224,603795417,512702992,20633309,469577360,980118995,373942175,959801426,524394624,151902691,972597843,781875281,653257054,317879345,156690350,760690624,259747026,756216972,604760709,138042435,731121081,674056776,465752633,401879174,87144532,408084418,592368046,553227022,756614143,211967453,46727919,820062972,612773111,937116341,495250997,805538360,728938302,594014009,966442163,256842104,654736978,838263935,344152408,534561613,912417832,741804884,909369285,89370295,397866997,819969895,252086898,96268356,778389565,236874188,560032997,198551570,212873810,215011883,406565542,161764783,110470909,540702542,860543278,995804933,872115933,254554778,898985714,227132870,614133420,127550549,107603133,807355144,720349630,984156538,562227111,990448214,511900822,811966333,74266830,130928408,699245190,371692477,284961604,294537262,303266664,407852543,999739158,439820316,435687114,968153809,304849762,986512358,100804661,515926947,225888301,939893722,290915364,516413173,22207238,705974915,561459992,12983590,737179540,655470722,459408144,665813037,799935836,452060060,884919414,98481776,11674065,561445827,763731132,313371486,10323547,468185786,775952658,133270242,46028492,155522062,142833308,841424455,978533846,69221747,322892149,553531774,688996692,876350519,675017412,133973193,295253811,282215267,985803988,667122454,692087270,940064856,346135480,920253629,61040070,288680300,196702923,127311588,46079852,367761792,450092763,18106754,249367423,617540329,462141949,301380130,426143351,462186935,673737582,240255186,479629952,610748934,609838886,423365047,455431767,684646612,351665755,572014739,512649164,702755842,526346998,660558190,700186282,788522958,934829421,170875874,263307488,904416196,537465089,470543202,252534448,574117304,824546335,42959423,553648068,39522346,579350942,317732048,476612397,30007347,71703746,299417660,299534037,7017592,912602657,93888469,949987062,167112967,349253611,215411494,486890135,1907117,946857012,273074700,949537456,691239159,641709213,817502122,115015972,543608205,581456125,778264292,504504258,486819637,737644486,852754269,519037289,255222971,84585421,38853178,921293563,649053965,389694413,128946502,999189738,795449122,160314095,231834016,155188659,698373427,817856018,285214468,765504357,698261585,381236966,760542779,814877930,964119387,208232154,956675199,156773150,26735275,535342558,158971199,23355474,827736199,722526932,860150408,918867034,912422589,883127363,400818228,516912388,640953833,243080698,521019858,209497846,896607395,139560175,885979619,119238931,376200097,42888211,847318991,281262115,545932644,904332841,325351412,674529986,898000759,937212754,634349121,470353590,730233044,449914822,3274189,386342680,261880125,239742599,253344751,528293121,552282236,28590267,149771094,712415277,113081859,561628992,830694952,115101310,249281626,625773886,342501789,320841959,32142855,190092535,950484266,748497040,471610529,446737052,219132640,252744847,88834576,375793955,6432566,220013201,205179817,770970704,755581108,898154965,172462820,580985658,625002051,877535921,691263616,605961187,864225740,369360215,239542044,477333569,781945624,787610344,5679483,646630739,520318022,952633170,849956279,220630190,337338670,483127086,281983641,519914793,512655240,775639607,11050638,329058988,799449823,22157199,878286521,824331121,166323653,644580785,580174896,791850878,924536629,222662120,64498715,821517067,935684972,702075474,908053075,181444624,642179736,216690752,677650514,805439397,120701126,714708258,789911046,990324979,519357736,343899064,162478666,440323715,358273853,698103577,828212934,966536684,806482205,882330414,697098707,300698549,158918416,13424979,628847171,147264867,156954972,853681541,672539939,531871194,855095887,562462131,903205846,127668377,832610484,806255413,739278724,176566332,404223659,919424706,687471794,448686212,928015418,4953801,221507183,21904809,729410473,394430200,822806268,675176760,70893277,681298484,768482685,145544132,627005896,397885563,680051790,158702451,757487104,549126510,17609442,929302581,63198366,372249057,737392311,681722011,752312792,158003689,37113526,208998742,626845656,757150191,532912955,546655294,462839004,155818375,414051598,886666206,318567531,904002538,182181929,791821913,807714237,535893852,242402738,923489548,690588042,933764045,896463835,906922740,51201064,306859127,692825394,520026802,370331430,918418096,125452170,591978747,853925391,498174303,557305413,330392628,279427591,420364063,9185388,137477889,262631331,550789374,603083991,473007826,290316574,429937662,609831054,910665744,889496838,725406440,383215597,506808347,540983935,750865770,511778682,53233608,144864213,895576636,733978883,983365689,59996720,617220895,951880867,459284000,835719469,413448922,846610618,350921672,959036106,936413660,786104220,381188385,709826282,209401961,617275138,587314341,719227389,407057999,631650293,517503751,280095057,840917812,844666900,562377676,919999283,931861580,393639185,342622800,697038463,934780500,533618141,7236103,477541626,496949884,675256625,660705468,129139191,30029844,958623722,295543508,987011962,811608680,242439741,643548318,816325760,967594819,906648203,76481722,120402485,727991017,785702358,217632973,485126038,987321743,221946845,102869216,393460222,203376114,53345156,475293756,105983414,710502664,454512744,830944745,389618649,449063895,850029741,149746021,927799552,238105523,923891196,778496761,718544360,112440778,808810112,514979378,446382291,451040608,223956825,336257911,58315556,820547562,201985833,178296715,14626429,762481536,408188887,879273389,220503528,104498701,508463660,377040148,145804688,859630342,249054724,964890399,361758007,625062512,107703793,837219019,352749330,310360141,577210314,167984015,539432005,707104791,341245820,537088363,750473010,904634024,923623670,445658766,978471766,73714898,749723445,27073327,948653497,967363979,186952104,87472568,706656409,964163025,996308987,198753891,248362481,482753580,883270346,110256078,414424386,472522452,401241576,369999033,342497832,925995028,997431921,630243935,961867214,931245114,98063108,284242374,926109571,963806642,139017495,447006468,398429696,758478268,632490621,792725543,835112618,512518509,870078596,864255797,751063172,380099498,29477996,388314800,773327707,762702297,795583202,677754763,586500813,327008862,20286536,660996492,286992823,149418422,695678302,271838469,103333184,195607607,951729209,717037735,743286170,674668512,648766391,271391204,901480835,353181193,553556106,358475134,648897709,696884384,860722681,582092294,443506612,631438074,662309509,934913657,505145417,309795988,966569459,443384050,800972930,568211245,661410549,60538168,925203996,243079834,107510068,812573666,311455590,332203492,416741474,357982091,987530273,848724233,509847375,807549928,818071722,166067637,967822276,410762830,421955965,51761838,668178005,711721384,477909872,491743447,877944189,936379580,288302612,346056620,173383863,830161486,188208089,343975827,564659567,316615962,429618365,51340645,598680199,599092337,650858797,77443452,241291990,24109369,807296856,39541206,251502478,547564473,189306722,161262518,393044850,210662731,224448902,608792544,455201405,565849654,382451348,13480305,736781108,459869614,971106020,231532405,726781055,396771235,107832311,978564851,358918118,787405411,428416072,529265907,820185266,592838375,463560056,625085558,854290936,848849716,922339124,474554783,746702825,954141559,689600041,373804723,98278887,774283152,82912066,617215133,321176963,499575382,226499129,81915716,810387405,847471688,283883207,949368557,888889074,484428626,657526227,9824567,352500855,102747981,155743396,638214408,81700710,907430868,472855733,754548520,461814317,952397599,20988477,456893286,363277628,96666763,926392324,92032504,700196647,636324363,765802771,553861685,350325875,907745486,122502670,775040091,411039112,316055009,834859558,481815182,481992230,597797642,604445604,416253460,405199716,183063308,365417924,637508935,317857673,960314042,807090932,858809993,9143283,602792092,93321390,496342001,456066485,541743106,114500884,584249259,931504578,581300238,398882553,49572864,25713889,609860859,291980990,941740392,294277648,377459137,105609430,544157394,375999968,232307472,82948754,682353314,996957212,569826161,328884291,409673690,790836953,888046669,117001160,781750447,111089433,774452441,183431494,541809394,240378031,726850809,383834203,69492651,872842300,990404411,623841994,411473705,77157027,796918999,901452785,306031795,364989616,828221777,721088405,670957913,353344639,363226090,810763730,296971222,247010154,946799263,591576805,842254350,704993000,618199097,152573644,511205888,631348961,38072405,680461868,226211858,820417234,269613444,91042008,839211715,42469020,832704357,23240210,895708943,778015734,915627442,753088025,321955250,39371020,571467204,216105377,931407084,938320262,525155070,290598646,44710142,369970294,128777469,646841999,940103047,118347730,620060392,718733846,890712614,457360526,488774732,899593065,323132948,440577692,474784297,539184603,969738120,596275147,686232920,14077113,237391298,744562727,61209532,496850404,904738161,502916330,319805152,421339089,376687668,239722882,692101227,183859651,653479791,707382145,114184174,109279408,128969037,714033479,61870268,200377577,237085339,757610963,465755728,167596317,606445837,133250201,378878215,861654194,735091697,665242086,740371141,973784215,274741527,259224245,501941552,643130262,672608327,831493412,790985788,73521079,473230152,387885613,739236924,996939292,138569072,789294764,109980066,29854155,329276491,252407841,187758831,184720385,434396888,552428563,845215344,311816097,399309163,208956252,483816251,93907627,523255273,663519003,271666452,289369921,915899816,375865413,243021344,725955358,138668642,354455433,832023761,59012501,949556712,244394795,552392127,770317516,138374044,244013238,914403468,806467798,383337956,694249869,712348112,381003727,416468290,929262092,786004337,161102232,300474794,43406452,129977198,768596543,384941761,978640513,451549251,255217845,261342790,313429913,263760963,939661526,126764173,146940037,878071156,339778147,97673728,931460516,228697497,695987491,52961651,121600473,167868196,63494630,466938377,621272252,292631834,735727187,781190882,295254494,761897812,448593810,144346617,628029459,296700394,841328253,990458935,150294730,780579277,629273622,522874971,920914464,994669662,639449450,16435821,378549912,946062489,945683512,111492257,754556708,896402228,70325859,531187238,712519861,294996209,686128584,139124565,759787701,709922562,173921675,71701583,319130805,274436658,339474395,693360217,213944722,959140488,813971000,158292443,975697960,575910358,32880508,960206714,779833936,988520660,281513216,285282181,905334839,184702366,179506444,544631018,8304186,938200435,76414651,739864732,655192545,600702161,684019314,961150613,283197972,99193639,480318419,888307995,214334295,704407437,818155719,585387311,811034779,455074098,270800652,455615313,678297543,590615769,854406215,664517823,739979423,367924926,241289954,214782148,234481360,687143710,16321573,572902226,130384826,677184468,958765201,105041727,929628906,386009307,418540875,949488518,54245094,597738863,463230401,41444633,946249217,228927762,518183352,700159418,88517394,605880891,953787814,895520406,426876904,88222560,202038069,100719292,772099315,743745046,656502552,736503560,60657586,669382196,560075137,454230994,859675823,302040825,676239760,443340656,524305873,574500850,600701479,539968015,708921588,457649637,856673619,552010646,648519913,802330555,284568372,698767496,747207836,338844749,772341341,211734743,75050404,912371326,614240756,612590650,246654818,484059395,815059765,545157444,267149427,760116669,455597265,200923228,659561279,601647609,908305360,686120774,362257094,546020465,510098282,817325708,300274186,965234640,823838496,697377069,782805931,266635561,278008962,603471541,9002540,981689922,346653651,749562569,404052411,259740055,610938052,279541938,102793476,453095704,660770381,642042948,120307115,110362490,78315380,456479043,231505459,255586240,381593727,754714542,831191744,650808027,883367950,398844738,938313913,69716208,368016774,352588198,13527379,242587919,305278295,293456925,653304512,84933955,99487666,401189206,349498614,522486525,128052303,314740703,163395782,283904414,331735531,924269267,479196919,458495084,899856159,62044155,157936285,744619002,534700752,491457458,780906667,836879853,426322193,643887416,209830969,10426442,675243283,297684779,214972432,684869013,416052655,637782244,161511456,767937620,895924497,276214380,107297560,376038933,259574150,949336519,90716160,281882900,60410653,306354466,973338248,428220014,16896447,59512550,284954402,608667900,375930404,21718326,121487425,221362403,969415942,774750521,580754233,757289554,771292252,175264525,59339233,217986411,502111344,651862984,693870057,641479995,960675401,559927494,12704208,321918332,908407088,41517557,343552495,134903160,428425464,541538809,513078696,925375428,224330969,595098854,3016318,2442900,501451897,664855418,211665489,258511421,544025223,897005798,8299556,92927362,840954175,194441477,758050171,164929444,380820743,210798236,708754510,863213673,946038768,44033378,50783589,45410107,979420451,722697541,573955185,797971988,207276665,999432664,404439197,765433548,587488081,781405974,214701675,996004531,515632048,966645547,868174779,789968367,723041062,443308897,829243779,117945005,303303695,437293533,161323204,814830863,607180591,881863590,491014609,307274982,763667681,909971857,553497781,462507929,931869795,319061838,978566906,662486146,539712756,508212163,675572431,24684101,118129623,515042415,379462411,692000303,60046961,651696308,16766829,621505243,728686510,752657612,349812982,514146514,525412828,522327402,124723900,449656118,730657052,172780285,651284766,217635290,171714661,469608775,206978591,372510641,523128105,504118564,319142145,82107787,742213896,245580308,635897713,299539138,925490114,178000757,122791661,330989951,441647056,456840120,206199988,883070876,864154951,359623037,168977479,341073288,926130058,641849336,540618256,738753793,806982224,788853408,58982352,934700632,982210783,928233159,715208645,977302243,801973820,938384624,917591301,754714838,541149119,292348466,674723719,373568309,964408640,316467922,852543984,599619892,57633340,487024539,743575870,516427547,63281976,480731508,78062135,11352709,885592027,603241949,228091477,69242846,58868868,256407369,411631162,867426669,7870237,541928710,583757584,670110613,542931576,502706830,439739809,316515759,997537967,679446632,905689674,329808788,144174250,620514187,749124886,739376128,106624934,148385806,915584968,857931697,487371061,835894569,823368326,316442559,896653343,170565062,864656902,60519592,827852736,532062614,604424172,968419141,452128908,400883476,136303781,849391457,87440935,744113140,246313731,455181278,284156463,340400761,224725442,545328490,366066980,17666209,117196878,846196046,983413247,265162709,471838396,139527458,430311892,389223294,391843291,646612958,645187951,143986102,505173297,979447391,837816233,594764850,258307521,361302994,419021315,746938622,207058621,18641575,88928773,34635897,538038843,682662238,506138560,971223993,415449022,351149301,688176361,476987155,707064847,357513480,183784272,846111503,335107164,457601773,402596504,520604242,336048704,397244026,466050880,115239549,624734003,180515227,813716540,969576174,911214280,64068217,387642646,839586802,259789254,821727281,731992685,810432898,421097057,504503759,751606467,691818400,342775247,591548082,4466471,688622880,78091680,514456441,746845389,64884676,451150432,84446542,553488867,651168561,330221424,399957920,735533880,831234616,90697162,607869576,365464546,448932158,85674336,614463354,715765584,416610256,489050794,828470407,138799976,120438101,105455885,560741523,109947049,186537953,734031887,746688902,355258282,979906686,970149373,604516751,743642119,368955649,79872453,626151245,169920838,234417236,581858410,342383035,293447813,579151013,269116104,163627751,691079659,892639488,475148301,176025836,912321439,135734236,191260935,150785558,303797058,111090145,617228891,907423851,82502167,626765080,828254374,377848398,826687201,627988435,473357278,959797478,460214374,314923475,192609479,212685792,52761897,931208713,713422930,767211325,597127954,623885468,917846580,763532548,893736101,663334544,157839461,316041832,672691179,172989415,269992057,780113515,123467656,704766988,977489540,825963379,533723460,303927929,752213204,241553413,49513328,498374320,777528649,407287448,99682316,658724447,595020906,827402800,831037981,157916095,38624729,909842723,162430070,941673423,2977635,553265759,264590940,59319659,135990691,704599931,667853849,585445146,201222651,2443587,852282212,841997294,111432138,706031882,881638449,155748194,32729045,715394366,370005557,930267399,252239633,997030061,136957280,592702635,342470053,962104723,748578781,987289422,23803235,991091851,713828161,634403433,701170287,62082388,247670838,741569890,841529552,182626445,93241968,308744200,52828873,102558647,749745413,231935685,195074824,750313791,119174893,447717948,871904392,547476373,884445837,216938847,707270080,732721558,876541683,568306657,835736056,867401117,826535905,388596513,163928322,2963605,114534565,783823207,131160979,534174586,756168767,969497910,531255681,212747921,654122599,267268113,35606718,783476344,468080594,686828519,973558360,219575330,188890005,80095932,389988106,760941082,449930605,508598369,806095072,562387724,775355499,299645717,215686773,193191736,292371558,43713723,473892245,250653271,980487990,431100488,247698872,371432300,749242328,184817436,262562158,506502761,317090584,11438737,422346002,747525193,876265969,231837933,616232202,750142136,548223305,970391694,416240782,243108180,332833506,925052380,354970058,143494028,728300381,383669595,46305371,254164366,37192820,499125016,861161046,982342360,103555678,535943294,518083278,944065551,164539884,310724970,958245486,346346284,441094489,143725390,248811190,609091122,408800263,535108023,125008524,220679310,871823906,212446037,626150921,933987733,485404189,293013405,144026868,156225770,547011690,732367788,170257045,187449278,6257930,21869953,973862217,819602710,227530963,98063748,627187815,367203227,138035632,432844145,82763023,227262669,745142901,455038757,505600755,569735937,775515678,684100426,189375234,58304458,114405338,710892016,87137597,961603992,329173321,7810302,879583532,696136677,386229768,956544286,757474077,853025769,617541784,957412298,329518446,192645831,169844741,283216443,343732207,943250046,147422072,79101696,500795035,304689130,839591280,332732670,920124204,333491757,712179495,313662015,61166508,955273412,919832562,812517201,739071078,148703987,404938956,316503926,582180795,581879307,217541452,505981237,729231013,853813582,804583026,580650073,550162346,247200462,591118808,556809659,350609194,375501248,58141541,533938416,730985994,927397726,52428554,121050841,922501614,288068102,520477915,348116891,794162330,783507533,99243845,620020937,276976777,907495586,256587845,121838311,209741125,788023014,573455082,459628988,3035244,922943692,847357048,948739675,637711652,158974570,500923589,488476408,26549684,911588730,746558966,907364602,325231488,222783988,304234773,561413218,563187038,27557105,857993494,839060599,722850599,117308367,202948026,863041561,471005786,839622973,78333100,910875369,394933621,49301985,599935577,723495510,340157957,863308579,35464997,824428193,567387287,657049846,881376018,887444354,624937840,757245990,808836358,174603144,89892276,198895983,801920185,602114812,56347498,236146649,493548228,704922219,687108756,203724950,214511643,521987332,541695875,983141041,359405516,419568044,546981494,286099831,834446341,693630551,36898702,639113382,390441709,204148797,531104077,609722302,293889256,819373016,490732135,772007185,979756959,262053871,239115849,340570412,966470874,9736353,226346273,608787867,386281418,114944649,278680580,923561285,520262294,590813559,719458978,71022630,951920225,205527346,553094217,512787810,140684175,831379865,659422059,609664486,669299344,604573565,440484952,705240712,831298774,499222426,473575566,272376212,628899990,940259769,31762488,369505082,998249146,821336085,640980472,198274762,518994771,943085265,978415341,337520394,881133800,924361416,531378928,281852941,298976123,169432343,114549374,971349672,505622337,271755449,539994724,427657744,846487232,847518677,235678815,49838183,532453902,810420891,709673752,266266224,359916625,893178302,876639111,977950665,325138340,748920641,357189623,772952599,434196691,280761494,375908725,628461218,805295532,17375550,19702062,109063988,853388933,222503363,289209742,805958093,445410513,871430893,996845338,978117159,112940495,462449058,924110595,478310784,7000197,58490847,829102106,417491061,197414001,381064600,334991257,964745578,880015591,333259057,557177143,728563371,791990126,600418347,658701853,860854324,833406863,972504014,963093758,545062909,107513316,848960171,870927728,951789467,580991778,847467942,59639571,590777417,155337202,421207152,450752339,740507458,8203733,202476498,514929271,4050153,819278011,311264317,482180230,305069857,809091804,666563017,783083075,311121442,31913090,988379729,647785218,141330863,591475837,401399207,729862097,593414890,348391290,460520175,398492043,101492234,434295681,812346504,886614087,968146797,229563548,509762066,519541036,340675811,496294071,78545971,315245334,677160242,128164223,543763780,383878685,302180085,537256246,689389283,343895731,36872851,433659387,83444771,637996402,882234298,289225601,435363530,44345544,535882083,316796368,3777234,48637863,266200261,636704379,166222857,710713638,135508409,489876815,618538976,863280857,130893730,330604514,454989935,958447898,507130443,926649966,248000748,658838634,535827739,198006106,469259748,304309846,460307100,194311682,322676080,595097346,651893221,989017068,245651438,357082973,769222629,259648724,872392706,891428530,273598989,53249439,656446192,686666748,428480729,961615677,788738277,941489767,634270740,284190073,831334756,73272170,353288,570026472,262742292,398807254,607790942,364362026,933359281,851911137,589989028,39985634,991807150,372321475,97625233,751936618,436843526,187412925,789429267,116452868,60901661,397197565,898034670,835117782,36246211,422623252,188585166,250636072,432886503,243714404,595666634,356183179,696567233,971914445,421343823,285450860,582793571,82949965,779695480,953468248,808286159,309107761,759812563,514943221,281520433,82421705,946727873,641494991,569828548,748084127,480111560,451172707,971747548,55295200,741850698,942876747,558365536,702670209,302819308,855493611,260756505,878736843,431983633,386192908,624155005,837962597,442643204,642721954,506774168,288225300,633332866,510304081,425038038,37629274,256529186,172374167,398569731,615710763,900236613,488091425,224137410,841116617,795403377,562965212,956920155,367454796,406168013,499129615,603034553,645143084,51082324,500150107,704081821,801797557,982466477,810740966,196142649,967679274,663274393,268710222,810476217,539511644,217356517,447398743,16379703,956030238,253418283,144387830,318511200,77318199,659461657,476569561,961514656,397515558,760789351,322106862,934381902,371934198,539944262,518715955,965917633,843892626,224229561,251020018,164657029,921935418,643457632,944140233,165189894,262226472,678101000,775634659,707806782,746381970,584199942,357525548,992869031,603777349,734043531,455538057,19161807,834468622,428401758,821821396,292122223,814561943,379812776,623579747,202480607,293993307,963863700,682863055,782300091,64718296,842924952,813014168,234448750,394734541,271943000,820280851,766060342,279334845,830594530,268742465,814157589,182751551,865935899,366408918,206078929,39319486,97019258,865937027,798187835,881842101,267922533,363885595,473418709,199560814,802831562,879575764,973237064,955043085,698703506,586803611,658872888,937326670,77563809,330596930,401493930,541123469,560131956,462593042,96401615,989706733,509392417,509277673,299455042,819003696,703943446,384085439,14172839,787376187,142193525,978802817,438862836,724314701,232968271,855054924,636972624,374229345,159005061,509508812,247773016,132411244,484128384,280289550,42041257,695030029,183755613,308646782,820518270,663478844,211689715,407831012,162568848,670656024,153654409,314507931,440536615,877976395,332216543,949159788,375034569,263371216,590309459,489988051,479007907,776260540,912792432,148343898,295898357,221612372,315209310,139094862,448357057,343751167,689975130,231682792,270828637,930988505,811509157,790508413,540390142,66576503,725915431,310564234,700234216,417792026,965047383,766311724,255695339,939660737,229944535,778924854,637998066,898626582,943916882,819814477,312800397,543125801,557244970,183488496,479560395,1254985,48753709,117876453,184398407,821300172,758371473,449739086,176962873,814795580,70419425,55535801,336497520,76941965,646001081,427657263,448599772,729985579,216358938,713381172,95478691,857663883,865785898,869372209,254201013,116695501,832502350,45575257,835713297,351031840,243592215,241274258,370402855,333211573,116383236,319713635,770827653,801399650,658846623,808985065,42142312,942414179,431639661,645663086,437464755,692351300,113447109,556278179,149216577,153914346,501525818,711571651,698833715,924541179,832540226,765996421,670855718,407961684,67066490,805188943,9284723,759652739,924033298,806121829,185787453,522626785,754381151,50270021,278458239,897907378,483335277,295126615,353298259,864232814,921641092,47810018,702947327,84686988,687127294,928853950,539502584,106514257,900942023,797203105,575352064,464411000,377103659,741597797,561921943,919717797,127485616,513273728,472882950,166763373,392059312,680312251,154601390,160748486,950266166,505507101,465047065,34559077,277695211,509006809,803248172,588960861,672936464,939741998,203897449,617147915,64887357,372292946,512637929,35883521,833799540,698751343,717771279,805476383,624432264,128392907,543551233,338340640,677142703,906181008,119795351,466318647,842814666,745097087,763645792,243619581,39538300,482272333,889660864,214550382,717868709,215767942,297922506,62725309,655531983,473927666,312288976,301039210,232697627,830100992,734102541,186177462,765966500,926139667,774036441,341847087,822296579,473154985,946142249,919000808,462631627,835156630,629245242,179108025,694744993,586873770,291433532,930974073,75787095,429198687,977071461,764349000,888348872,992746279,783328599,613419927,722238525,563841112,46753561,127596001,906794440,729874315,635762121,581236774,845946620,931565127,735628031,204702644,584358868,511203797,369862114,432283026,17013626,81168068,271053156,172921990,607827311,321575082,381760710,66013892,417619220,874367207,435595182,769199241,295162897,915371280,377947594,220165776,278727470,261392869,75770578,145195456,753865117,557544373,752721518,437008751,951343374,365670675,955104962,964442843,907845896,460763455,624171699,715416583,39501996,524842872,96480343,511291339,199243548,517118423,570471565,392413877,965572079,94710159,273628459,322507059,719734740,653886381,822772842,327477575,529086080,967621985,262241697,973141362,19266475,982358101,802454978,595809710,721171504,964194371,724249044,354599831,784971506,305169466,321791078,823323380,293262263,369525849,768679169,911953100,56181653,363510144,454663656,852065746,452326294,94016028,252358840,379219052,29437724,653165052,517710632,607702576,902273236,497349732,808718944,335222547,991008416,471106104,170229036,2334876,768923037,2243892,934609693,313625611,495277683,163338116,433141068,606747873,390362203,785124933,503427019,508622024,675886029,696576403,98556168,27997574,543576168,984356740,301835000,808473586,646605124,742564970,262649732,214505263,622427835,578761595,927095954,807086544,917940673,600739265,207053932,33382406,418040339,106425563,157797636,936309092,27743226,828899740,532366534,588306575,898281732,882379699,453110849,139706851,50480971,701901476,991653039,182656784,410721267,854893991,108536023,124731215,475881020,923833567,973649949,982047516,234779704,186124189,894503331,268413026,756988717,88185104,336505223,634656835,668718422,619027852,646184048,178372818,282705367,361751362,540928922,609131803,192698610,871452256,783057366,825467787,617277380,198202476,765082450,639239620,779298829,878822877,730674810,446862355,807823794,7837893,268460220,525765803,454989734,458110360,648376552,873973039,45363841,118099501,425029104,278780808,97088286,554341324,434683223,792823783,565708334,314205079,307256547,367882751,644954453,537485200,453350931,921076392,607340105,619872679,643392750,365543813,441916339,47100694,25484534,545407498,473392769,772426986,502158598,901379540,737644847,79026081,942926146,120401421,183195567,162323381,635095841,631471943,475770040,282642829,857425969,5533379,857168419,728258398,466149553,60401312,860863991,553662601,586825519,854550684,434841860,901241666,219156534,554082650,541457535,73806553,74754615,71370010,617081305,750122,443603632,135380414,251825092,157663044,74549780,658920810,854530964,483349052,928733970,543434864,551160487,734746897,882646696,574884184,628057521,485415893,151198171,3019297,856939993,949866713,187504976,336179626,19881698,16501601,951399632,276558597,95449215,480500545,698349141,132331402,400929884,370300223,557687234,156887041,345860450,384122477,936692975,127637626,981494080,700807416,483296622,976554506,507059774,203431699,525571443,493547217,174408544,501087563,622133596,525619663,515110688,534422162,901594654,40307067,53314704,571476810,128065357,715156416,429005252,375273022,986850194,898978311,13652477,312145576,523225709,897545310,323126781,61894919,962619028,412722299,123442555,744598438,688188018,687038171,359835898,175108074,884262576,849380324,192981952,109361510,959243061,498435871,210762962,2724634,702144335,566316526,280958412,943943624,180414872,65856589,57161323,461880334,63879106,411703860,313484997,628237762,986958306,285582999,782493866,180787155,72620586,410303953,94132913,679081609,808822742,737832617,928949064,165595916,570998443,892490823,243244038,185014834,330194712,655755193,233001652,295378522,53357848,958284277,718348409,988515946,603453656,135810271,526227066,177380617,967707938,910319144,389310020,12262604,609821012,636380056,425464726,184819637,137242792,136892737,409440095,560082557,729943636,945007661,976057329,555339703,420166680,914873222,715400452,964613642,108133948,385884879,53598304,202909656,384559551,838383407,620706735,67681986,214968041,628894875,81012579,265984388,875280506,464265295,889896288,828724801,557881066,649253173,464684324,799263209,590324192,908813318,325636416,328047294,278600493,82583905,268944271,867321753,478042516,713183347,282019423,875256227,251852196,854588406,308592270,434236699,638561982,187425365,699551627,97325811,467767504,629688698,459102320,580363114,822867435,382571053,446105757,757265309,370109626,310246537,194236372,105206987,79005156,699188658,370401588,434533737,964399803,62597493,834321882,944650474,416199554,98874271,303180680,333323086,787230429,531235202,409490955,849366867,31113355,10133931,70413049,598128322,969315828,602255678,207022329,365479637,518293794,398734439,1537470,349548882,482016056,42818045,559770423,116713276,643656357,196467276,778317480,394312749,806193434,298047582,131160765,479727878,995115507,898900258,264630910,247005765,293202917,40542073,643095473,380384549,376758871,68652548,874069181,492839078,518085211,785413072,697790493,789066029,447788498,364737657,629925284,943602793,205147015,366846229,674831624,406377589,889425168,594059540,412986461,387404116,881351768,498248359,819596510,96372047,603831428,282229305,135462524,961371748,486183072,605413260,624186788,971584196,861385430,550266087,626117335,109854092,99766600,227977259,452078142,599011626,918021403,678883736,597064923,130123105,238840225,735445109,534222805,433027989,2259113,583046256,380714726,327430657,25159058,206509059,691061661,951930267,448177957,473184251,451747913,997364777,435179611,863247900,334030283,113402551,257927503,376998069,767139794,65433783,636519280,183759333,128421881,133203257,325206620,62968757,565080312,112418584,810427402,272895102,639552361,695600093,509760251,600065366,780717729,949693240,113498186,75090643,152795254,22087858,502831146,877659518,506188183,571703615,156039848,480847726,50871179,646940140,964016749,776701082,717226255,510857942,932787960,172124746,159748676,611913120,923837615,992990449,992833655,209882018,673702082,299090911,234972368,296282343,568695140,659510202,778093934,379595405,621267725,505808781,635316516,912414465,577095062,297402802,119323459,29877233,471743445,457982708,688380558,854675761,402223230,39226082,614630161,140720476,250599063,33125407,700714751,490802806,480459803,974611045,330089330,295782823,370751811,536342565,317033397,603745013,932324488,72040751,869489137,267671815,122991257,15107005,552864544,270588971,142348344,807098036,381035114,558690208,80203263,411042798,998788689,128071455,400784477,175470706,762809554,322582452,317579179,136852672,488636899,856561017,380700322,946373048,397790765,902848404,984185018,479219465,696647964,380894019,239959296,395247715,138568790,189625806,111374168,625384821,87672057,808398330,993743169,37504668,627554852,36874979,238709261,600234835,163638803,915694415,406117680,285362496,87360794,555023972,980530938,418747892,168568305,625532501,720362914,162927431,936152164,798641496,660892030,586959073,515054539,24313683,193019899,610850204,364532089,938372364,326128443,725752575,83955238,178772514,16801949,501722778,725055881,384751946,205227465,480112155,683720699,939804956,416536342,354568869,322087421,251507517,363977082,322718498,580120418,487573195,969346766,742236394,734921431,139224052,724472491,828640506,881926176,463924661,2264858,548627579,12108672,958971682,719696535,128441289,648192007,857903797,358797313,151041024,275656866,589815527,506219410,723789073,532864925,563574675,511509995,49871870,930658169,911961437,290073218,811519340,957588452,607038225,566795020,471909310,217660430,249972472,760217141,198451810,680428071,610861991,798418649,24332934,23942316,556142388,98771122,933590234,686360090,424605831,374120681,373164991,791782763,285230376,294732480,177148106,298864384,169347246,723076145,67631378,242575519,319250700,789880051,667803295,22323041,988618030,207492459,480528563,784688372,633636642,645741198,985577649,968039295,209356447,555527194,943010195,452232484,134666759,92038748,619326804,447284079,115389073,785998255,933236801,687096539,614991617,38267905,54406067,570355855,474814373,459537048,273916360,565691945,597698852,629018712,324313319,760113402,755960643,663904502,938466356,39135151,717616407,493086376,920136392,800299391,957036498,899500936,368149087,353801280,202390845,377084349,525453871,495764232,78953457,674861696,850947657,272741609,574661434,475315701,730810245,154522001,694345898,522613289,522391600,174395109,62496584,154159156,360810471,738151381,446691283,409679120,517720474,472205887,953113390,624628614,118483103,637680106,184557207,693707224,5923280,324851048,561456461,469233297,204513797,729216201,929898666,625531691,590427330,835999788,15815553,988482541,125863048,278161428,477920732,605894400,491194646,672435440,613303775,762880395,833963857,752946498,602011326,558706645,319901216,552320761,517618085,664887850,779506517,454905253,558669361,505659929,49256406,212916908,182668486,295062918,981876340,595397924,439489776,203996192,448640085,310926939,202922744,364600743,856135266,279998759,486790968,475566498,236065261,528112929,946728985,944638982,258480060,94847335,117981410,515946115,777098872,97982711,763387738,319028514,145971376,628467884,994683338,466134270,824629117,716613317,511183845,652502463,96781748,194427297,233681082,669676863,205377795,457047319,418493495,251599245,164966974,263724968,830006162,288232255,558674460,767054563,971310878,259199488,447085901,715280757,30849544,572763082,552514090,500667968,67489749,285183389,688419632,929280378,121580567,143572873,506409027,134436603,365283956,795194380,137445877,608685922,701595916,738710718,431885733,602704161,610021737,83070143,484588061,828562233,63010209,617101974,227996929,375104371,570059961,904299593,37668238,5202539,772920420,708319924,428978344,722316152,759518379,345183204,464768768,962101701,603726258,558181004,382209230,511878963,523329580,529387124,629662080,828131062,624952832,246914937,472593996,598498418,417671563,827130399,170502727,987523978,415713139,338067465,821292710,236967165,635375078,885794051,226973521,289542805,351258936,529345039,859917487,348757837,907268594,122502384,823854429,583664330,730852626,280844326,755659367,749858331,453362558,862077334,706862447,254225526,498754828,881700070,481787356,399137468,657696242,105045529,374416266,823676136,819865696,47800117,332070968,557674508,876318577,716240419,551360163,577102149,470619315,393794447,900224379,144514945,732075244,366922313,936980124,484410250,965979031,167702765,676077763,387905114,950170765,596319795,555126970,286338589,216831189,130581030,943896312,534203944,311972709,716910703,369377730,977804250,402320182,467746703,181723479,109187273,691937563,691950004,445819249,853596251,83906644,749097271,867140379,746472276,491081482,494036609,153747342,682699198,229769437,344682049,848315176,887996331,748627991,179810089,851320176,228849150,778983991,739170182,47017857,297254839,685821308,511216194,517094553,957978066,71368406,856465807,5333399,878878170,303613652,160180785,217153416,291041821,661463585,297599838,145152654,880355203,706189634,22961615,701202307,226464529,814079361,990513716,518590855,160688695,555823532,732280967,449312823,819156207,221263657,626761996,863864896,246862206,373545671,862593456,157997384,432150598,345100901,831930445,370188194,186595272,532523681,999735822,936453730,931203608,811192637,804273697,565960035,554900358,803911583,322957621,936917279,807157400,114949396,501583702,293128764,78502421,728367281,393557449,223527390,701761213,975744923,885860276,99737068,487138082,787010015,170557981,506867043,613758271,945283079,753934834,986418734,566015410,875866296,909317967,375805974,997945907,470251893,314428683,379838950,336930128,172748842,609732977,105701975,991587644,45735803,326219530,333268790,82223580,983915702,675482523,960901491,95665877,994784426,811593424,87506593,923983325,17194754,982805363,674606073,609798062,804415606,997126030,117925329,818240496,411284861,280537550,485796757,734761008,552879784,645630257,903437394,263092628,621462321,754957395,36420211,998941835,17747011,520568440,636111065,230061440,498853346,374043702,512649709,270461562,996531356,102488816,402582264,452367794,176996283,399259141,823610175,190066774,95888031,674573168,163209982,746176442,625471486,631845618,106849975,689499326,345116003,999518093,231597520,668915928,17061910,661489737,158696674,104355849,861922396,233772402,17004426,383503439,275969497,102419122,990775519,381791119,764627016,275857842,306725612,493872654,706644884,203779614,24911738,618052287,486876522,289453593,585920133,25952423,214842142,553678100,284373810,573625632,960991279,438769463,666728747,392834644,407388543,779999973,880609514,983061618,826531581,325463576,192499129,817529046,705569505,397420229,121069375,946389645,93803743,708881443,128147676,676099807,603150229,530120846,411590127,30355880,34405852,986572249,763919057,386673451,267223931,177830576,419235874,840024677,747888976,633462000,981159975,881199508,335304024,510726355,145102246,438548827,791606837,427903471,962474294,13781178,31458243,915665392,496938015,842622174,494898815,859944399,167031073,117400000,769974290,426415887,380667094,503192901,713770944,261668837,441201238,904911601,306999600,579983565,948027420,359781219,506151200,456678322,512452745,55753293,78832659,45107565,26803765,900463880,478248372,81691492,128982176,169782506,545923260,332023456,925023026,639587372,998023963,391133468,165618384,865724949,19757808,933044757,124580522,702133839,381685095,667338401,939243007,374045346,693471255,149566132,565834325,812098238,336009496,214138038,740600852,285307687,663286758,223634017,192986843,910352121,811352893,925881854,591541872,146813791,599023330,655935943,914001360,1390612,703996569,509086466,557081422,542869104,55167172,193675644,790789365,381124567,430602082,725905204,8000519,191287967,3737286,113284915,23531254,57532782,202023008,322806117,81685197,534411085,225592736,124380796,757125946,62826868,383244605,961865032,181960099,463221688,374610658,524259156,541526811,227921409,817765049,957491316,208867575,758240420,964765062,662595536,332343351,689399936,521017676,587170938,721540757,383743559,128067164,72833134,449506905,647675969,660319044,926634667,92154538,839823057,94469734,638995247,518908124,523272090,72068338,791601092,353819087,603729003,364795969,610492586,639539939,825648691,274914884,938970423,328829540,578556474,517756736,329239590,493258694,868252923,83357673,804063851,626091024,186447410,386852540,427681496,997423782,335000824,852093099,741946914,97898918,175092443,657458084,597548417,636508381,539529100,144443319,28241061,332389610,407228089,746326503,786977412,481326206,920125523,966590999,808606750,199137767,679297361,557655432,704331665,572306851,936194611,517094052,684792529,940200706,220825383,399269051,522861439,855205057,576861572,279409170,973883875,256898987,934061945,705531964,235254556,63038652,312923549,128335737,903894163,325811343,67990449,321452918,828212589,504214446,918524886,824229595,231705020,533070882,164740136,644728943,517471,558463417,344650101,703717806,890877125,927748082,270697331,470744518,539253873,303509925,462753767,346479959,497629927,489564542,524013531,110015700,652709642,150724963,842801943,282939625,104952280,497062415,922639717,181083213,820717582,985630124,351026792,915441477,520669853,486222560,525510973,129729823,566307596,768286765,331604379,425518235,273079259,718793386,49858807,601700357,767009727,936626680,822694667,592506064,190309261,444716849,404327421,109366276,238223741,689044101,475820603,103780403,457018327,209116978,930490126,983984388,515014658,828286540,101718281,669307785,501246932,368806643,941119150,220900211,268440821,770916206,24329043,389091827,818839236,465670949,348630640,738853497,267936253,884780605,270526974,201112984,33711527,242462626,465651830,970893415,348006060,813225667,215906762,891361585,444540444,246984961,775182837,750834281,908651921,773565995,502034362,834967635,572920469,166255702,222430736,714526170,953137458,599913849,776862911,659128119,263304200,719673021,125055660,399574056,89880331,317479541,363432469,470213931,504523467,346080209,739495583,568610759,688778786,544910070,814919943,976096585,962249081,756476987,601698080,146952624,710469246,488393805,256111342,384495729,360083822,467691294,495531334,379645949,196982903,79019322,915483359,593910631,431427026,426207768,687602592,523451119,832563811,574948192,140759882,614636676,231644581,428604535,842740229,899208007,482669315,589371928,486817157,830246918,936142607,81249471,463062366,43454448,92183060,965162524,245250622,343790581,337777604,659487597,900993689,966685268,525669788,402637921,156479888,646857963,339058199,778046042,458743348,462608289,437247428,243437786,533429567,374032390,858157519,571597610,602424664,273068360,465005252,936972639,373850465,51195991,909832946,62369871,911712507,254102415,758808855,686725314,207845793,607875856,981101457,863279704,895672230,554356509,646121907,722999412,320174237,583352049,400419189,257354337,839901046,185197204,429834593,706137802,313837240,473910354,452327551,840833890,336153953,841932495,269523159,446948019,664422448,166933317,571434198,793154405,951024327,102793614,7248282,938914456,797751034,716069804,888283093,156997716,510874983,534778348,332916427,667673836,763758367,759745220,878950760,220861171,988182997,255367031,867007461,640580391,122800217,619620575,482107939,403154949,484110554,785229901,760276536,462446745,215531024,271617055,692070817,356143164,284410319,28541039,157713816,137215100,356367290,261168203,78772217,23005557,490069321,69710392,447647487,304302428,577225270,573880707,428497021,31269643,941726148,656091803,680490342,923715321,868633972,147144615,903636383,89497465,804917732,329194202,47834609,147353167,290429936,612029695,677510730,148696002,616223147,396114711,53043378,600964748,806573448,571843566,597167972,293848271,56192996,978752955,870340161,527501576,754169351,906924163,624902301,218172241,994568217,493606629,278668300,784440595,464316194,86988787,11127474,349877167,258197508,972816308,343194235,935770118,83115654,208374720,621721108,37348054,84829331,537965259,898622711,840550614,292205825,696243731,399938942,715088812,496965932,184606464,322104156,2927357,868454903,863898648,493371523,902130523,816580058,11907577,558736412,425805322,27091010,613540378,848097534,780778191,884584526,982947402,88642957,365825476,353034174,68152190,318933108,256469038,853582900,574118516,495117326,153601474,701220860,113828483,525315015,71419106,745618818,704604195,730181100,49579340,825698428,610394352,973967234,52129197,813280193,831015025,310930642,857578695,502866962,121692370,252582316,878320031,594342220,230749390,142470206,967063200,354485505,32020856,855882509,558254805,439363187,510960337,755970763,230536516,232744129,121640206,136088316,579585265,634938751,389196403,356857897,47831099,659664178,542184349,689467800,863108777,128547837,156591838,914748082,603352139,743933963,449836629,22987223,863173326,755535717,496802400,955820056,581024974,354786627,266083299,563028075,363403393,355727207,364514599,920339112,920372314,762383511,948741309,26917029,543418621,479074327,962933731,620637346,477349328,196238291,199990562,265426449,281059438,843624327,647821281,890950447,718811121,473603477,379724900,271911707,239415768,557173414,335852022,475506673,873406005,315378325,524553785,668618381,364295152,428268325,613535922,567612838,200097159,262094190,143493198,300986599,680923589,250217295,38796787,229242988,36102761,422582471,884862093,565113619,917626711,897892286,164941304,916311368,191328599,271053075,4891063,157517635,718489509,918256121,929627357,955448986,630053810,930428642,191760326,677552309,466150632,9935673,964513971,123955359,352691492,849740938,160498922,242744885,242167064,246879866,161213246,656692547,201510859,112716985,906042101,604913236,686469462,354197754,378277214,468885763,108680914,57232335,17850370,345150867,196990294,690556570,928201571,282714318,562174925,978001483,38130980,442853984,342354943,758259956,853740091,688376252,753972014,69710648,479942196,162316281,926965255,965821618,862190191,436230902,648753338,34983689,135991003,83492956,137172103,629058469,20705452,259786255,983128766,477260209,168477574,656769747,133779361,502433032,722407870,920359971,434629876,181605823,572646168,760390590,67241230,137495509,713083518,653397207,884722915,743739215,79165956,820401545,31222973,568218096,430178847,828205646,487633246,583270313,518642514,782173397,343293181,87901012,177085418,663803905,448384385,278911540,179252767,111149570,68316194,422707689,754865177,144053679,481922579,729517690,163368065,242248823,115499281,221837379,333524072,986641963,293033875,88864009,179329803,413865799,86047483,766497857,648932934,490451003,721840422,920622493,443417317,423194410,878740727,892663445,450421945,866886892,645942433,264656861,595016744,292229471,103081499,758670634,12212893,879108520,301190727,379438864,793727461,825068825,990990623,540865145,617643272,355069494,197553192,13843704,990014026,334122804,432094263,340302872,803579872,751738986,635431397,550153182,818716589,46111842,979968570,320013357,322385459,688901820,538157458,130360875,421776938,489354296,353211335,425295891,249232489,629796253,841778207,220566516,642759367,793051941,439163119,757604225,850582964,98093039,656553891,9254105,642437822,796920388,280715103,642661922,736177740,543692613,987314821,153548430,684330943,757257442,557161473,529066323,756370285,816070317,320970801,753644767,480163446,914438275,865535382,117703334,865782987,717904989,502941564,926583372,462964891,30237769,455485950,964205288,762938121,83933898,638654639,890742308,631788325,679078820,123393180,787054504,505787127,486532283,299423612,408425030,921314380,213326122,124543064,855786026,162018687,474937285,68752301,123403827,287092961,705094565,737966739,8112983,156848400,575575358,130341065,200819487,893922062,277918227,805828117,652640881,476251494,691831887,492377069,288226561,308943644,974145556,245821560,543945702,710865548,157973133,236650219,667505843,711649162,905650901,777920542,235020359,568181926,483576654,159812267,343726841,894400532,6017648,457440402,369289369,621195181,957945031,286297554,458284116,759564536,242211661,509341386,939195340,974250676,858589150,472226958,264602659,95687087,907111001,16718779,362023608,200862069,341191220,120517878,910531291,523566309,408534440,662273631,523543284,900409509,191391667,966988828,812278313,43790,82291753,935029804,895348052,529501121,311575027,123407112,177565703,713045852,419668818,202016120,98816535,502963693,327114098,59344150,623479070,747913147,967237892,874904902,705604865,105413949,466845407,803348455,623128716,303254183,377787171,68182893,711948948,39028397,702301316,939557171,484575404,392630725,645817695,136228597,382853744,76607037,415121070,332774248,678658022,640940153,910030716,458812227,389882008,409078077,224973156,981470320,428160619,894991734,644137618,335269936,496436216,691470467,496850822,296385979,314012696,420841465,794817789,16114982,753546966,905607747,77515463,776894679,100611245,564533045,970214277,923907510,159272482,885922309,67443144,827987203,443182718,80172841,91416738,1860278,139875434,40748896,315512061,312709339,376153024,721136311,386411019,898025206,739965312,412823304,874809859,285731829,193904647,611061843,48416652,620811742,350785835,19765564,62411791,93578276,928406004,515438380,758683242,933298734,432010634,5154709,900950464,164285525,297887814,716229476,337857171,989354138,387403113,190050587,98546412,184118861,492556210,515642781,989108263,250805055,831940608,116032304,963708642,601235483,566490759,339006782,397939847,4571184,9143273,184928931,860155974,782018369,719005309,501807219,883609781,499648518,796957085,810453961,208351873,613039446,748722720,966328656,314991349,417334075,753499256,447727391,540447753,55786792,660042645,921713723,132172779,955098881,673129633,164169140,642868183,715892638,103855876,83985061,601949816,914874388,138743675,171582884,803338783,966898470,52359350,211937064,535959050,692230523,703967796,72178570,984327477,493871006,271620703,694664630,714414638,30442372,499022167,45440050,395544246,181433316,763606030,717317405,314963686,619284583,666615989,163956014,141458943,3921888,745582169,10430943,620193122,606694372,310812484,929191479,150637993,863089597,5329267,551608544,754138511,257454398,694808310,229086799,692167212,276133855,673603121,844268124,508139044,233307804,375263424,919102633,225170410,545806801,703671181,156343245,120604557,138658775,647846812,195830851,612825792,627206916,106887735,434309887,439814358,644582028,518256170,313276289,567817632,434999617,806859863,565204039,320653640,483168279,723389653,872578583,908534203,315154227,551328470,877888438,407466482,716928639,881614663,302260909,387892900,193768117,617208336,556799757,54846270,618769416,379623424,978339743,167393762,682462235,723398863,725086264,623159940,242537706,358758858,418212012,305127561,486364694,427607058,656703296,204210111,969225699,968942684,219103934,394930505,557769194,483453955,702896828,195142081,227534398,214289477,251719821,484868650,8250576,218156806,221971210,644153544,360237508,233170993,307384681,623890174,504098968,550460556,42443925,625743579,942512300,12389563,567098343,53327347,577851103,91190241,491346097,193170933,381973651,608230931,486680959,975375161,785040330,10650062,141809884,514411020,394795466,641894299,918064926,171724744,610804524,382592838,557093033,966635262,164264752,411340758,565597628,684131680,287502148,628507121,302132764,771136012,608162515,11923443,428487630,492777399,864173642,904651162,372414501,176141211,714144333,977893413,535437308,838397025,120489964,172113180,891855415,218749940,84814677,610113924,557869854,155411006,78084767,356430049,109955611,742697602,405815180,443456122,841199140,531689751,398512659,334649007,793449444,427183102,356453398,139479915,827361190,199125007,718488771,985488326,551856078,64829488,219908685,691850905,851466858,637638017,895162596,532851854,931202078,949153903,980955945,789129480,869369936,516931874,133453635,943277754,182753400,444718225,102458706,169479833,56412447,473810669,38470475,207946135,938009211,485335401,188577179,979688047,537919627,130159631,857328843,801970518,549849524,364076119,302420306,842122363,433851596,794956330,702164243,7376711,695366028,272962968,134803105,550257533,111379330,808011668,338558266,545400534,57323086,206024659,856242533,548803802,654095359,781323118,781013335,370634139,227930661,880811955,387369299,252882329,934378601,346665152,568316500,372810853,288287980,60104113,400587244,679287298,56301623,809370580,197987142,65352988,11762284,107918137,263534982,45707618,153881582,966630873,911463797,123199218,118960031,770759238,129390079,608677335,804350896,132188978,943010359,800626668,967879012,777838419,471690102,742184452,654543910,749481829,199191515,72703987,198899778,602325879,429741780,322060493,203135943,573777934,915834986,618700266,206442657,734547209,806700468,119933444,449144386,852455891,687084255,964300272,994036924,449133140,617941661,522026674,190027031,392634388,709715397,183345979,454412677,303653915,862490448,348513951,419648030,587553115,116306451,384580555,42960696,484152377,462732525,17782436,759501267,777484249,832046037,386838354,833515808,637584813,385279353,137508347,801226755,380017967,807976559,275463888,548302545,527315870,617364289,928994997,943413283,352997095,528157984,839471580,651142189,582053659,907649623,72413477,273426915,744227021,333005458,459401523,285893307,755278754,521827882,3796996,934347448,551095519,574493986,542731865,271475634,976543863,924086035,642200387,833929388,84982876,749634301,571220644,846812409,564920689,658845911,15655728,585154671,189123863,585211723,79028771,24475252,194188356,741420602,53429646,229515756,778373858,135559239,118146556,237177653,789019785,982661013,813567649,904700653,417533207,529626446,573628965,431818677,356261003,510922183,414489775,381450047,663467220,626516983,685614937,544361131,428745255,869975383,351665305,335458764,650255603,453529143,79525230,657378814,996347967,298372117,614851957,964351023,802411149,349455466,919167241,54632223,797383154,957799205,58276111,807493325,};

long inverse(long a){
	long b=MD;
	long u=1;
	long v=0;
	long s,t;
	while(b){
		t=a/b;
		s=b; b=a-t*b; a=s;
		s=v; v=u-t*v; u=s;
	}
	if(u<0){
		u+=MD;
	}
	return u;
}

long fac(long n){
	long z;
	if(n%FAC_D<=FAC_D/2){
		z=tbl[n/FAC_D];
		for(long i=n/FAC_D*FAC_D;i<n;){
			z=z*++i%MD;
		}
	}else{
		z=1;
		for(long i=(n/FAC_D+1)*FAC_D;i>n;){
			z=z*i--%MD;
		}
		z=inverse(z)*tbl[n/FAC_D+1]%MD;
		
	}
	return z;
}

long ifac(long n){
	return inverse(fac(n));
}

main(){
	char*rp=mmap(0l,1l<<25,1,2,0,0ll);
	rd(m);
	long x=0;
	while(*rp){
		rd(h);
		m+=~h;
		x+=!!h;
	}
	if(++m<0){
		write(1,"NA",2);
	}else{
		long r=fac(m+x)*ifac(m)%MD*ifac(x)%MD;
		char wbuf[64],*wp=wbuf+sizeof wbuf;
		wt(r);
		write(1,wp,wbuf+sizeof wbuf-wp);
	}
	_exit(0);
}