結果
| 問題 | No.2083 OR Subset |
| ユーザー |
 maspy
|
| 提出日時 | 2022-09-25 22:45:56 |
| 言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
| 結果 |
AC
|
| 実行時間 | 44 ms / 3,000 ms |
| コード長 | 49,464 bytes |
| コンパイル時間 | 135 ms |
| コンパイル使用メモリ | 17,536 KB |
| 実行使用メモリ | 15,744 KB |
| 最終ジャッジ日時 | 2024-06-01 23:44:11 |
| 合計ジャッジ時間 | 1,671 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 38 ms
15,488 KB |
| testcase_01 | AC | 40 ms
15,616 KB |
| testcase_02 | AC | 44 ms
15,616 KB |
| testcase_03 | AC | 43 ms
15,616 KB |
| testcase_04 | AC | 40 ms
15,616 KB |
| testcase_05 | AC | 43 ms
15,744 KB |
| testcase_06 | AC | 38 ms
15,616 KB |
| testcase_07 | AC | 39 ms
15,616 KB |
| testcase_08 | AC | 42 ms
15,616 KB |
| testcase_09 | AC | 39 ms
15,616 KB |
| testcase_10 | AC | 38 ms
15,488 KB |
| testcase_11 | AC | 39 ms
15,616 KB |
| testcase_12 | AC | 39 ms
15,744 KB |
| testcase_13 | AC | 39 ms
15,616 KB |
| testcase_14 | AC | 39 ms
15,616 KB |
| testcase_15 | AC | 39 ms
15,616 KB |
| testcase_16 | AC | 38 ms
15,616 KB |
| testcase_17 | AC | 39 ms
15,616 KB |
| testcase_18 | AC | 39 ms
15,744 KB |
| testcase_19 | AC | 40 ms
15,744 KB |
ソースコード
A=[
1,2,5,18,98,813,10128,186140,4976595,191272048,507509052,456945526,106198010,616130923,220849686,593196999,265174966,123615107,335308613,846381206,319100614,774506940,128583267,163986684,404237398,10596204,579883569,953745996,487710857,133058987,501741996,63872954,762159387,978298664,198025174,261451349,218648730,210141226,878155856,569379140,533471982,971575215,774296781,207983882,697030314,93743589,413025197,927229555,971931695,909695276,412426408,946206296,452115816,399343576,725372809,734574207,413033652,779499449,931678297,345420320,990033670,406799633,495098893,877396730,524310149,374182924,147505800,717639008,954195578,305043881,839251637,537874131,516979886,761140681,673516864,360924368,521970186,857680601,262503219,594346375,891853688,351889075,696700836,536923690,858358786,153708269,965283207,998179039,339220240,666323421,956127676,353360437,658086961,735839113,429458574,302433857,484745337,152312996,25213666,954003029,457732232,168324317,62015205,308511982,61940757,621284768,167844139,202900120,450618551,311211136,867779493,493669778,753932886,435615119,99398749,223089439,829684636,153343979,484958355,703489335,790195993,946499678,397705902,314880784,607044700,509042857,127527342,915460571,406636666,478777004,617765018,4914601,165936015,601294712,90639375,801589763,460507178,336212251,477027544,202223365,141862246,130255346,590931443,673982836,640922767,923419271,364113550,158351649,22645693,985085412,244274001,600768303,14902203,339336979,386910041,225457966,349750592,697828481,717290828,881550959,574862475,833789112,158814750,277685181,10981096,489326723,21474638,427374553,665250909,524256471,794274115,966758119,99454200,897616106,110301024,995394256,512154934,675998507,760656293,972029623,175237220,826792808,925335890,523296306,523035412,909218692,685883266,196225101,325115605,220629149,810730873,855308180,436812434,996463708,16118336,428437672,982810518,931316786,101008441,283881225,281806607,459863619,609791132,198581735,469888964,542615681,831832973,375152122,711598964,344753450,591422372,831828745,727258863,840693080,134092151,181424825,436689372,534406144,873050775,884211081,608388407,709739679,732015996,186385458,800546490,260370690,666820340,693144240,76418111,798139142,996359008,841062772,194418290,765982598,357293273,976838417,19418909,87509515,192729660,804021874,395530087,98345116,670680441,85861854,447939530,793095192,437235980,336005367,680780767,219365138,744905028,373581530,585233347,1444072,753496368,351594473,93446530,253108246,231494823,33934453,203788470,659938809,782645527,937004348,423996148,82555954,568755766,908924806,628160606,497203558,376375391,391703332,439803175,78625145,302960759,559719881,857715812,146669633,916570884,617306937,568031062,447294931,218539489,416583493,328016668,484119921,802873333,189255027,302331118,461253792,741768203,876532055,485758206,740844620,800996439,254598921,679201829,959766952,765559284,175929084,762439734,245291614,100052328,201573583,843822561,348973886,260061221,334820606,29580068,79279816,236438790,354965423,802386635,409738088,438731399,820126387,436756492,690884565,363073311,276362635,422424480,637257519,374235478,285407753,162101348,818396954,35044834,749450616,538063431,944936830,150078750,42201186,253083313,220451318,402241724,109557227,597620491,498147199,767490376,252736932,789687664,515505039,525523665,311263973,338724450,43850191,63122663,863790908,785576100,721326672,604166967,942074475,989094762,454441656,537496968,435660349,527244222,955398883,678384240,260737721,293034987,104425364,673986098,590635309,637874283,379770168,570131122,318935568,751949988,468547025,765079373,142988318,624612365,651417476,838726991,831272186,394788924,542914998,259117914,727902432,754391561,436631099,773148067,425247504,475079920,325219889,607058778,323189417,357062874,505397320,67918069,374602010,771287113,888148210,223555597,808042661,564400599,602397613,202539721,378746244,885894091,311984394,792079182,800269830,18240153,516885720,819419879,227360796,33609976,831559063,179679380,415089772,115052430,608438323,619553001,511158664,981148422,36123673,368091208,863634102,531486346,138371587,667833577,684160677,152246764,467150861,930238294,170947806,352481341,899028379,597146097,880063704,800234353,465226258,229468195,258333564,570594434,702643990,559849229,338212983,965633111,216915296,151649677,368157297,194154104,698237840,40132116,504831837,814050990,968755862,608712822,531836789,683513992,167156464,196165412,703237824,199220231,383982253,496404780,213935390,836384608,298892019,892549491,190326405,257129180,258842827,341074492,818898982,793490213,268086657,54345283,158963467,774677852,117540211,372943083,887021207,179991771,815145563,588809764,806353309,440820447,945532411,121707240,392705332,278312663,432182426,166614634,275786472,945995659,273059316,898076668,972376541,333548249,826059571,461909099,73967959,797088716,741822792,291868429,315675773,618609709,242256306,527972738,424354438,281877461,914334941,698617343,779090337,724892873,54582728,665659336,260165404,781902770,463848224,678346953,627814477,841147197,408916340,664376658,277234249,543096645,612584270,86607432,988282354,310267284,945883609,774539173,222309563,886224390,763460930,309735845,976402353,263113974,660488509,252984199,819401737,893549640,973825634,464675017,877148601,346824460,520173809,351931329,760405322,158462521,782051769,887347212,140408372,391982802,367820099,529099098,146993141,699667502,557710680,73994298,626446369,403245539,249744816,158891536,42201517,104698169,237842933,295125878,673879932,556824340,12424885,624825527,834251053,271042773,647660412,947294408,785924347,947272631,896248302,774026715,74374704,469635195,718029864,409382263,809119297,868818401,505747050,818117016,945633278,264934316,991727452,105123569,782545260,748906847,961125071,263979466,253179699,398428488,887290572,564201493,293537827,820431948,466483203,676081641,269960627,422304605,99089909,815016152,151070108,262507054,820082994,3242211,109886992,345379380,793138780,707334266,98989724,822125619,522106863,917130252,448188675,865090721,118518307,948689000,898005680,218303765,376139985,85318231,551207642,758846498,356165153,701269595,963802619,12469529,321675387,521487108,559248310,648200512,895741881,557959430,423241708,557572445,734744609,390835491,504960098,835045798,680607715,558538882,476496554,30808012,721833155,857300351,565859133,369162938,247643418,487144990,53490926,88332329,135976747,191413481,807959171,772849579,82143822,979496831,230170374,710798974,171003966,51122920,214743362,814788191,193390388,696506020,179435369,603265917,876484519,71326248,669669711,960170241,503326468,796415144,465579429,107899471,932584078,205988097,269324843,539968006,282286506,479721777,828378412,984314443,424882516,911807905,637056258,156040721,983349241,182629380,956828804,725400194,770484848,163004965,259111272,852246704,982345887,501864557,814287239,991670311,396821923,943034535,13297880,243114909,426270426,634313045,855412009,36284527,948949291,380802777,847933582,993897800,621994254,486274862,370743802,344750224,901834132,934054657,758097861,600483064,129779406,807691272,311128410,294831463,701415187,62335668,963486507,137260638,173702953,500543183,764276028,569813128,935679457,542804533,234823927,200286390,777011097,404493963,688137463,978758336,610865614,906906171,743688244,174342515,225595330,367206865,195997810,221791730,291088268,637173479,46877511,885554981,959904377,492042324,238078182,400154448,395441176,762050306,861071140,321396276,690794822,900341973,135394607,12370900,387024599,362027955,275069158,734168816,321583811,777269111,929420765,508681543,905162812,827511182,297656931,78875039,383305458,81527800,356202693,775529659,527420392,573659093,235842675,773267432,371772440,313200109,950327663,140104504,78426878,939963669,688627792,966780393,817274722,912713264,860149821,566171191,838480710,345610578,159353519,383557233,731039282,159364375,874573328,896341450,677728025,282597475,194284015,814379760,199890494,846401143,700785138,520172130,893941062,37820869,843695612,443606951,108344704,731117873,890061662,703326095,393728272,171308136,697409732,939070232,72864588,491804984,774734619,168486963,217483887,956315195,356622145,499576143,694817226,839543825,885558889,274299852,937252473,779446402,450414781,137462774,431707224,820562894,167504868,687761530,924423887,604368349,354505336,563510413,803650991,916036242,763716201,231143015,521926776,994180584,536494318,27825120,701123160,673344617,901752198,224945248,25845784,997455481,800357785,550593850,578022601,975467361,219283009,757075849,865340597,528478922,149700683,512939732,226672687,44678485,833465849,282224076,917526466,59481397,980067635,372452717,839197978,728822342,950472411,261179898,951780480,381202237,706809656,850161431,875314697,837038042,129188964,473205722,122827481,658008942,226292018,36951710,489626575,63521474,901875162,961709943,176052854,468689469,729895049,482952878,914163130,144465123,527658894,31594985,270680201,793178615,486729884,331527268,407354936,135979326,822436140,456186459,377895951,543991948,648750241,747519513,802248918,312871504,282681374,372188924,556247691,350258894,592368643,660360873,166204699,425278544,479583622,853270876,613341805,377669241,809913858,962245511,724383801,300619316,788832964,637029671,21046797,391033545,572019657,276656521,373588063,110495796,380028505,257406406,229456092,462229937,120546978,74106781,522136204,359784136,424072605,688309674,337434595,290300767,884243097,481825423,396836054,984306186,555564301,411185789,266888865,365656255,846035414,520348058,214037777,236473251,779243599,42533817,870346481,390044458,898515407,441174315,437207345,895886362,343301492,888139478,218262682,330005300,406025771,254099955,809818664,542084413,807673388,450574963,480766132,404535283,306117532,878895589,581068691,310015607,212437298,691708942,949339657,123501911,1255508,344927173,558453614,131060380,862583170,713559167,758221859,920917447,912180881,449967560,987497299,766958067,535963711,371809232,819465309,24027859,92724526,29817648,192989530,314960251,614769882,433743397,514889270,539081205,71066386,627246394,135071439,863562869,484006003,979316212,385318014,789806660,84027375,991193907,971305425,483641182,169837705,953884307,338697497,487111574,168120485,550549471,198933702,220333335,689592182,380431804,557734555,689728919,33802567,902468163,87766978,569978723,415899679,272725237,967868525,59262369,552925965,950924230,428926536,765297372,307982231,456602176,950649608,649408026,729079623,737857162,57791827,835470409,83581961,485364310,604592220,357426391,321847921,277645415,63829984,163898702,40271990,837702117,536128632,361159386,210828964,680539806,435046790,633217818,547750957,698142267,359188919,606437131,519703004,719171499,139182745,897458090,890946845,901900539,786934610,303873155,111470230,886742935,699804619,260507103,65520932,398352176,556303012,480975298,711910782,517594485,909080120,189526821,193593027,485658536,468251659,229225823,389985909,109023442,54429686,805096436,300913982,576370460,582567389,774274154,98669174,79374063,446093413,745217512,36660372,497061334,288487655,894034642,907081816,992477792,146827471,725864952,395440591,438431098,555305162,842122651,464880441,480452730,222010319,95037275,116634023,190786535,859115649,196960597,805586297,714659719,588531509,886516044,227361533,583641753,919871017,365715209,878700339,596980817,381466553,125108193,565838899,63821237,26699880,147497502,385791191,963689048,978157438,860276510,185056211,135679042,737087048,585082616,447465233,797514655,518984190,425114593,130147488,827061223,669240793,704468092,422783590,977692535,237417972,185836681,255653350,365812546,20059267,226366318,807658991,528040874,297233316,382240754,237189949,741223732,331713773,882201811,882596246,152544658,407987577,714499014,563146379,593363918,8378842,50685921,155583331,715002930,357112460,420142149,461897,710179037,845892751,1350788,577491805,614047517,695549090,268774412,608828826,521924110,136731950,659601686,707736212,175384770,171947273,254385198,906472108,876017510,202182235,394675163,523212284,461455058,805279078,521336558,877221612,982265655,337124891,382706421,620126820,338964239,245688099,430899610,380778316,259217481,563853732,762028839,51055792,610897928,964661312,838280088,285369426,859724425,449563260,180485304,485641800,485488622,723588284,471068023,2794765,42997727,354768555,354110168,890899255,9351287,583100817,821205072,523199047,821485130,527874217,491935034,792824918,207628920,287532899,177665683,909607883,89085236,538809304,35288911,533458662,985728393,222402331,309280338,876776807,963587947,833142356,210586218,758442374,96773725,20986449,423516106,276193466,106661937,102951048,443889462,760239591,148037690,108515866,149324240,367940447,538885613,327841355,291385226,141539205,620886903,510770878,461058717,551399853,78641164,703184257,768426985,348274882,139119009,397030559,790852187,878264055,468577359,475587099,668801494,831346774,862339482,358986728,158626708,306229199,579903857,348678022,586658625,136635289,525231692,516319734,265434275,528857775,954376237,969426553,976698826,601441914,540524491,264342496,64889621,195086076,76017449,819762316,887039287,150725808,756211325,243574480,440103835,909688149,215212811,434781420,760217826,434754960,200885003,820237765,757798297,428913030,976561359,809018233,195009846,180334627,697711313,463067872,440588692,631832234,822354060,784376126,462741479,15394166,79228473,135642772,719166534,352512461,830368782,240194091,909960593,866607685,199614226,662251925,848260185,561260590,820726903,637069195,927998042,10558367,428910568,992442722,458904267,861659550,253019957,809912230,966774633,438115977,356348615,908755657,509544056,472969497,622474203,983494249,945707146,166950485,54150992,872741283,44220712,760415468,439306444,352211739,118150105,184464425,774643743,394778899,611842484,150618885,791133374,89042774,196793852,747653124,102206782,559003355,473205240,355107453,459771789,462656007,513327818,748887083,367049913,580424167,390027039,668237101,910143013,195376877,357642059,240135232,380279361,670288933,629617438,133532824,80399798,427868624,306229326,539792982,126634121,267641342,766149284,362193414,152790685,355313597,784654779,439404201,950718955,906864689,744967166,318112336,654693757,969917917,861967013,862175348,537379948,590759276,729184142,156007320,539707651,772687371,42501447,448338923,108565713,838230075,195650432,284702872,535326726,644202344,713044266,547918130,807586761,402859708,116158621,204032555,106902033,866333460,373489902,959950790,882769261,864321301,195423494,522185110,594726733,793970364,859980810,177284933,117789067,228013746,159106676,812598926,992153102,417853286,588265507,697439023,948898978,53892127,665860913,723388031,947217657,522730942,320497391,482329326,187709069,502150295,373796797,586181473,918263235,54562679,269201667,40609636,381122440,573860271,114116936,36919939,780837681,501264838,234206105,840451508,93687167,525779030,924593137,156623189,741425716,9207606,233223384,992461126,570579894,173840778,897364387,603098474,31201594,513972055,207926313,475493750,390170791,119311582,17007570,550196356,710693394,932144456,958861302,697989639,944231608,540319152,551505065,752432408,835979389,281492602,501084615,823434507,429771668,672324528,988429367,973719849,462070575,119458378,821958735,774306519,938430517,822414260,970077923,674000945,242008863,410012521,961019317,488015117,441528701,740485641,285336233,371746292,429921764,756273243,190720941,479852439,530240286,931726607,306227177,779744216,649198149,201558678,847493298,655142077,117520654,856794436,883606684,46361923,18532663,327177736,520448467,851370121,715925320,148166525,463029421,685686239,655989918,558066731,622610872,674642285,89688937,211281557,210365834,17028758,983008506,776855004,491352468,92945304,375332241,137040546,52373503,270306897,276859110,461468621,93856111,101904642,849286988,487844915,827308759,572886204,91901998,584786820,354551379,386276139,392835206,26167068,236971363,27258271,912304618,707602938,582091355,861464574,866487489,853857935,463982169,736067898,12999095,38944431,581704156,470153000,472903579,710120746,541063034,829320125,166207640,386706061,487401769,534121695,678288320,605002591,370090588,220128963,822892453,61641790,583098601,552004807,251029178,793542096,217307469,261364084,509860790,732413395,608749343,539558819,940674927,452856470,817128824,133531965,864355809,618639572,295827507,536008901,645877546,798921113,803295048,20882727,7379345,391797240,469161991,960546937,290019986,915710428,872011127,207558701,903918095,104764007,544247433,795635739,910134682,365375271,77626697,931885666,76773337,628968608,40110171,820321489,143951923,417291482,4855566,632372894,835518853,232507361,810487787,352494350,917919780,118140879,419857850,696238108,313969469,218318669,118865863,19431894,658767245,892916492,283370847,872317377,806145935,874032635,367852570,726152018,468705809,496484266,840427915,295964767,645586207,6769905,911797852,993694281,151728733,935455314,675917056,517318559,812727791,396970190,775429079,445471362,352376395,93646832,586501545,539086589,542547555,833123261,70759123,449888078,814139807,454914925,362017015,578172374,108983981,201247291,660636092,240311807,516480783,310338,882512382,699200007,171945456,494747902,245029521,868287844,70953974,786841655,115911268,431007773,811071731,572824327,208583142,797573219,882491754,812588450,936758752,785468772,325613901,268953371,930414999,30033396,489763514,13727408,186992856,469180260,550418277,209526658,344949990,418812299,830285631,283103819,818486175,80798489,684124352,129984999,872940112,273359064,749842115,780770474,336144024,701533075,703151525,784708098,13833785,675229421,666954883,142706231,719855288,989427655,595238675,285479605,171406012,948011225,751511120,212260855,606299720,65407,778395642,471317490,80214190,819086825,989267078,817155747,366400651,936646902,734147665,357617857,565660107,358042271,909034250,488595096,850623318,426451821,199688534,88872053,962086662,22532199,334101039,63639865,576410342,495764854,227795129,374824568,503617112,580128288,309426240,268575804,971508397,261783941,429287482,397444835,116748034,204262291,842732588,451583788,904260378,26387987,889333555,807981049,600759595,896626803,564925562,297532050,443815970,50362460,315039274,86823304,579996693,33916448,869238688,772798254,571639261,37340730,273851959,412907364,480177779,687126553,673240032,598351643,271218533,766744807,478952847,982748562,10084885,565082116,465013973,471704786,189154320,480898365,8356639,148108049,20037936,640267602,230653254,48110438,575342432,959795660,455455702,918688565,218158734,316816827,263814337,543811708,981314689,739740276,602679913,990669585,22293960,332784979,347876300,739590902,725301750,297609849,737258606,370190543,458617775,121856435,725648288,809873997,307865519,936592277,334713814,831173263,507107535,307844451,893239474,566548778,688061160,763967556,623192173,613217006,719517624,866895149,370133794,468367962,953344518,816477142,549642201,282192441,915993988,285896104,775837719,418787629,684054937,921213377,251670190,973417459,650292831,682419819,704573046,521083980,837407896,398937725,48179999,584524419,44725981,141713189,888393732,753325358,407569940,129128638,88809358,599390184,99421040,71894435,411473883,299390192,987186817,344439425,699072520,80165366,780076741,744816042,59278438,443071532,911715882,386416446,377517746,232941679,314670054,980534127,839136352,807696659,677247659,322999420,932726712,229928006,397431638,324006573,201716485,404417802,678876013,623543056,341064276,415712035,747925051,866385461,4784276,905765744,299919758,472409117,630483557,819194024,33378506,729694620,693920476,866709223,723346249,417568858,517486206,830993336,831350034,447930359,852907768,167255894,410312357,745260228,911175499,391390652,20153183,233381511,276194379,234289550,819641620,463821699,839412289,99227707,399862498,682595415,153560083,892832294,495115244,643188782,776987628,445827348,762751217,220331975,338609227,139093420,685943037,125635627,929420074,241586381,540235092,91796441,297619263,431601975,757666295,955560725,459282460,252025164,766632816,468959613,230385655,947750080,302273398,68128160,578588085,956770168,492148935,559307820,185688820,619130524,631873459,260160915,966043231,735735676,939545752,298114320,883420735,467596307,816843324,568644710,293610259,793144876,619068483,223011491,954650173,717274753,654097637,518779618,179447344,798220083,516919899,256388049,873214854,179106073,356092822,1390285,720558961,317200878,363065559,12099725,332677148,533792943,982537193,679681423,53234511,727171430,809459798,303195202,60175329,840862472,738173364,390434780,872255929,813480638,572906259,873918672,960120535,603103314,910361302,917216063,345973116,902160214,674421940,990625355,403931894,29492406,72862015,434993235,981428316,797324311,441296533,367522185,946300130,453218143,99890545,957816061,19252442,530021739,64328978,623373691,955827361,91504689,749704485,744377208,410067515,42532166,697887194,334406321,396259068,156278670,234790055,598539143,377857524,52963643,705517826,673561138,652057431,508978719,214050158,723713857,222551006,82974097,371630163,144132543,925033683,122791858,335223951,636371347,175569951,659737067,956904694,590768099,486996811,81311931,690342103,37711131,369327673,889923181,365539143,168463968,775219263,509382024,250675148,377139534,808829140,172244589,155993536,742500384,430943787,641343837,877240716,284004828,724527268,725020975,414492064,311810044,43508859,782203504,268014689,540606882,229418521,501778178,109248883,244307275,768483520,307965691,91189542,713547098,182549364,790343756,851159632,628446568,749891178,881822918,984846857,452715240,505797259,207364950,6399924,283040768,424263052,581224902,277102698,371290083,169476899,340089364,933103126,77223977,677423130,343855678,958537540,927961711,3479895,191199300,791624372,487603253,120697421,225034245,578692260,465293339,937113650,651525434,171950163,635098666,586457110,814728825,96482817,947034368,880518517,695838402,900355037,149248478,887562571,562771051,444928425,21785085,291818222,504928041,203373550,664890683,376335479,214732491,734380667,842516937,375207397,835936334,978626433,991223988,688050081,900817463,765197940,841626059,415521845,689282669,444881461,423599835,860867097,874742313,349856270,512882717,268768377,334889253,367412416,798905768,992984434,292258869,186860429,429342941,900902648,520261153,904048952,931838025,940191464,566889232,619520650,250895034,498429526,243294370,158269809,982807986,18569731,677759794,873882905,410707807,895208856,906319616,266966150,639957601,69517584,265188323,366953280,891138903,291602685,187830948,807394615,445764840,52289018,854379003,696005908,467227525,244036073,798881466,33265504,574929094,718244545,259689803,814767387,584466188,732268797,129699470,213146264,466051548,842235067,190490586,879960006,371544096,752377772,76298855,839733760,384213094,899333751,708076805,68071678,693554365,573602472,471306601,471665213,734438365,834065211,645846867,920966314,461656037,907638405,727402489,466294128,840446211,594053261,230998914,905785469,779033140,138691722,806061867,768453897,393772673,456630692,970305385,5996838,66709639,77644862,947774094,992445963,375665591,285990317,661858763,668587169,568097702,14169622,214626591,659109716,990651056,521246997,873461310,305445860,807546991,787062032,944837069,340372436,167449267,406131735,339826899,485298092,966143519,92335007,154189708,564119307,358817173,909171913,230533842,634828168,429480228,617015772,866975863,712465273,672387659,583131491,507564206,35609083,620582603,20037128,615315849,596703474,150614843,400040505,303921751,584859115,541416072,967938016,215990898,820985931,215120881,381067808,559447703,900207577,983827554,801004246,484779643,679022635,682633690,662430704,480307,691213582,317070100,991230879,95610604,239376853,510377093,242068898,916594832,885591377,770260062,895308293,345550629,225229685,409854878,375969145,415491682,768825353,365773733,784152230,445235814,20168134,640180277,482705875,104996423,417909172,897259435,532571226,127305221,976826168,713505782,342205670,85298950,132111616,290718454,818388965,44924577,44816586,625586505,346676357,197072585,669314881,475631615,915235751,652168141,522490253,120995393,857552141,316402169,65969816,981577778,581075225,900672483,87367540,96128950,708444988,992059427,783772904,782896416,681091089,150545436,760078820,246590581,397946056,150530815,846349811,864391051,766868669,105669408,689191996,748648443,169447697,5531777,715790041,672342943,140730948,869788636,309727992,419798455,227813342,722615934,934840891,909404078,669743589,239922777,302870850,884897425,123690677,381369376,137536644,918579392,970425783,261913752,518882686,636119579,564942454,697587412,171035650,748320967,179087889,964344247,300214779,784079999,341680637,721160247,926391242,578023276,628429378,878229958,66551533,822276295,174852620,890992583,606906254,916662921,38313786,954680423,735862944,895868546,695091922,8264739,538215502,48549915,73027032,694857287,34528107,289538952,569682959,108060456,202402063,245511595,833859958,388617287,406295360,662498755,299463297,497078214,429912555,886443239,539531477,152171573,108724729,70900701,133941897,298103764,412680989,445157990,510013202,469145718,443539455,778404115,699783267,51179187,40220443,399863833,170830961,970330433,989145307,222475373,952861035,129001711,694380979,360658778,735972041,856450153,879975422,856742672,928210368,278894213,817661013,365619045,651235217,726664565,307230951,436775779,260773558,249769993,4995504,870619763,472104902,717468976,378118265,193836624,331478670,527673472,112104254,591186173,93410886,962137998,32087917,354411410,951999659,635000988,427544829,128832484,915408499,73633091,460458174,246824898,840024616,841576469,567382731,671823687,498540490,34866859,759930828,172033345,227129996,960411272,540426552,229665811,523737973,897728500,784118771,84932878,668746278,883510941,122007460,548420277,589703345,898980097,8124282,875685838,120222732,121738470,272889394,856049337,971739900,81477439,214972444,401023396,190978655,326804746,223028861,879547100,489945956,183854456,11013202,998090729,852733551,12221224,569956195,262426216,313396741,167620458,708537560,378227848,701451799,960434798,862246564,401783013,177768079,446367120,195946905,261158549,283646052,600880932,775867800,854750740,228281452,462197054,888936151,340224830,182021286,766610480,833427081,864360733,320604811,50098539,159541374,431227352,195060592,264037635,312935215,114375445,734182702,803337615,871140763,955370742,362898153,775944059,114306760,543445925,579929721,931729383,909855945,859803704,300012274,426659225,775851336,300097254,995053146,382619080,37800483,712402640,1441439,841743263,218154257,506533753,655667780,213517646,579649877,340475778,695368412,733851846,575750524,284273468,388003166,342823977,690176466,134259380,794360511,895943457,244749163,279848950,978876447,796638500,487384133,943096641,465979931,859511534,633385852,677421272,315392254,237798650,734917770,217243304,420146556,437543712,235781646,741773522,255929125,410920122,46299275,409847255,807162159,314857563,453963876,218791538,957299879,868910896,237074705,320184808,417712153,100985418,883340535,508476964,641790689,484416898,255591396,771824624,53165039,234237120,339309321,299285638,829101260,801229317,416922104,446400986,27978343,383640329,881359152,39519021,71144412,858803932,280809176,744473978,623614460,158392281,865296149,108466781,708791827,551495868,674671608,942806950,587240739,112127546,31465642,539771760,577418875,714176778,217772950,831394310,639559834,899475789,237302021,47387656,563741482,161125891,763295911,413474408,943544999,196709414,561716048,87105541,964966008,311754420,737375342,7874239,806020963,293288249,719141975,439727897,271013240,321461431,812913513,885171769,47458111,729226950,231167210,569794954,546317181,403610373,534754367,9976746,405297291,996320973,695985959,509980089,308510086,451880863,507739566,510699620,147513105,357523848,217207224,393978884,567251063,28685860,150493334,360386627,170893324,817343896,829835255,610654591,609199777,448239422,799624600,555697194,202435962,618120284,728853263,450545543,821808428,701766933,787824055,376504329,50447180,607309632,498757386,717014555,565466401,192773864,613710530,30283762,880210943,893970653,259650490,26566837,930913259,247429304,903879288,965375045,310139636,622657645,913378140,636790094,709193634,507377832,680108276,89712031,2359024,485455402,329848925,537264128,270723216,911474292,899400085,936054700,779639328,221349853,181194841,81322923,99558892,18572251,381134947,65275211,811136527,587689233,227655493,568172563,335022828,684430993,427186451,498980297,448978038,507683867,261934911,729057723,915901674,92197464,167548962,496110744,544472574,241637274,132395573,801660648,218534204,219679341,213443544,192928932,743372050,928213649,339400111,268027017,376192316,579987843,934894241,104601662,643244225,645933158,827120864,214351601,709709965,902766818,382421142,444146377,133858115,731686313,115384156,823037377,942738026,231559098,789804594,832928804,61201426,879794850,577152522,972011333,123038198,449024496,138590307,713138212,362522170,33850765,224063989,909619331,112376951,494984972,865572631,123141595,337142489,499751522,25379770,250515869,692161549,460191747,217025505,327994848,96553393,141892170,601679775,155584902,158566907,330132245,918371847,121016698,113323058,233999107,163603161,722072291,652671166,284986320,736860882,365198818,455283009,959566273,705099733,486402675,51085336,686073340,531271875,305778133,952028061,953153845,484015858,248179254,674428930,619231040,36818051,444321980,513191669,219884613,579776954,276505555,864983176,697774571,795876182,810534761,690830005,468925974,725014946,417100134,664971889,619377631,942701017,839421184,639737609,436902412,879211565,511524307,409266908,633081238,321535347,801815052,635642327,740812294,13303148,898489760,288237462,814485872,228208740,886538661,683264556,357514092,75907244,814291134,890712798,122267972,674306378,268722253,81305475,621816888,966637536,92564319,824783763,312549747,598792460,595719018,509151427,743140184,404085672,293377173,865575869,802788367,762982814,199585263,846836841,359728569,680447451,290094830,716959965,588936376,666066749,835991840,916537950,151028131,109718098,20606459,796875273,890358143,572482757,163953799,402964052,715120097,77333911,960454798,189156995,303121337,848801169,663225988,908075173,223463425,792001554,772346776,977065793,191082061,446929744,128549941,248948676,235902185,517405809,490785725,234555305,412757734,670560711,358296386,688834911,910894125,978004458,543781349,332464127,206171371,437439356,190539291,803554936,905902581,385231288,44037332,474139328,675712210,692238585,637766901,9591516,685019083,182246316,721810646,85779819,6389333,28002410,585115945,588024994,188893589,696534928,718195381,695642202,535739260,395763343,219889427,882176310,410356312,700824115,199450989,396364434,734168158,955337438,621491735,162428809,113303721,901504510,180836191,177812628,944808654,384373241,753987022,109695910,707278571,122242246,905507336,404714081,651788839,805448580,940714234,247681893,814690512,310066480,410049219,147324585,476640458,434409733,122678009,671317387,959125078,618905474,644307891,526003660,682840044,67127770,653536749,503651954,42969319,895264480,206399078,647345223,181638441,337446317,987905067,258073178,319591558,590821171,822883831,272732035,326471396,698497464,783365631,712549207,236197221,818070632,611176992,332426764,830837097,559828028,835717435,850406899,626073564,401618916,913031702,455646483,337400794,556908646,877150110,763920639,538026416,200081055,493190131,366192589,164346613,558677292,8903493,867605151,59534549,578905405,723481628,981448012,189660257,80345767,754740636,153719766,151077161,253874338,222005004,485550664,181143993,372876277,415709386,246887549,586041481,428435965,314487063,113840904,361163101,109889184,295582343,667347488,200054184,26011809,491557602,20092317,60090793,580581713,900394348,495618659,594798027,202915896,766594583,236820287,231566199,867697611,564447511,635160758,38458981,859935055,893796052,214459137,649378055,622551440,939963653,675015812,474545392,746790505,132568630,708317771,628166074,836881545,938024340,874927898,224669529,766489564,838365223,645407986,825912581,795798323,344363036,975709718,588665207,667789670,595690014,142369905,455803574,864425438,331619249,266108135,114609808,791756248,437601159,223335466,226411017,178192038,732106348,420939150,598719847,662591293,386670305,112161742,195473694,472631240,296113034,171875545,724487404,245956894,821233461,183392261,277920490,619644130,395388413,417737278,962946618,776948989,731673605,832096660,650856733,659867554,783827631,723386404,182580174,523405498,265763922,246153855,155353079,739149127,360669272,335284792,93502716,252173311,696219162,733261028,956385551,443534845,558328166,526173045,173625281,11661052,504912035,277250334,365445331,738534974,199991650,689213385,790301278,89597362,129187484,376973552,87625851,677239983,535294314,267785497,139201626,299941980,555608959,119059184,350729755,731326321,446157869,410225457,279835481,802555009,108799397,123126207,65209861,95606058,961707281,263925756,644541865,689144718,58749,233407453,361539700,539689743,296182083,270870756,676842706,60851535,350242208,107544935,892270627,289360235,605700391,233447604,692693126,2558564,990905395,222901705,493794168,584681192,873008075,730529670,221562604,20817689,714651930,452553680,615774913,811684449,778570757,832772857,341425110,721617187,225201966,274198429,638504790,497568510,642624628,216113176,920572389,302879998,742143919,988031906,800896001,673242477,409932015,949301669,764009660,505909057,596347137,970394683,675112749,702482797,222750858,439155799,838304577,80719067,17899816,407349424,716518943,190245840,457724477,589093236,591881803,94839650,17178098,165252155,974977002,148063981,160619304,637395446,151701418,28492155,986937346,550951824,550157139,361345444,649419163,617216061,535130222,114842893,818058324,379281601,391454037,587188560,201505021,381151494,409744538,140886789,510792247,339216536,88636006,362329600,28921415,145579262,601197200,64279705,493113553,428157516,233797501,969116079,194392430,660415098,555631478,472373902,429731154,101981893,801961004,598782680,902633664,686752949,588648902,201019881,415860006,372912192,159133099,442365508,755380469,874143695,86850419,710677185,102388133,382567264,290867550,432258401,304138353,41892733,418534608,98874267,106625739,667355825,451435324,544022383,712169491,489698251,693988411,444230457,575331875,913534052,377170325,622953219,313289438,121097026,368739866,29225742,322096290,326882671,776654506,7356211,457289949,713937999,6404366,659425903,828890700,870630606,652240968,334201882,493249118,956257442,399458898,819623627,449104727,60293426,326923107,564894829,887389771,695944057,356118163,171625216,119202949,633395334,572428538,422460447,76040888,307789364,680562005,60649326,65902373,225691289,651718269,859954292,608361099,517010186,72278224,207397658,865857703,716252897,376983018,991385740,979380167,670761029,417363105,896539266,191723356,342773148,380180738,14093590,328808951,855411208,777567972,480983366,528151591,362935142,156072076,975085207,242682850,79583550,35666007,134668918,753994149,583698796,993964404,983549436,228154599,334850413,523228721,638255880,779985421,708218095,640931490,538289834,956658238,685670548,223636847,669585428,8997547,219280215,124778063,559064082,386976213,46792889,231498637,18627973,620897549,604283329,38216522,639811643,237752985,468407522,770459827,581973390,481411860,757543751,654087386,515789384,914806405,77509068,654884377,346351247,530815889,794859144,954454822,836902248,306963207,499362779,309737232,214826167,651777539,444744022,578647642,434191359,766767475,664752504,687808634,947838934,79089006,32066878,818989229,120585796,830967819,344621244,269116171,304677688,639367125,604920512,55279768,643040634,833465018,458769977,608211605,189736062,336320399,623737371,67733346,640680829,610443989,50671396,209706294,113563449,9180654,77230651,281543821,716360584,598422823,368666860,41059786,703875045,375971292,92400050,919823591,387300432,85525302,216720295,430461147,675209512,549321020,395167480,830505216,867275882,80483154,678336926,48801586,450982559,336390459,660359347,629999958,911169732,226871149,757583844,916988153,179698604,60519513,57107867,913502653,509919147,384107844,552764493,707663937,550814324,607277950,682758036,379854438,476134295,25133045,107652927,424566297,480177172,437751682,614029054,329493544,105839644,760343896,128613717,703641970,727524644,960973668,952410963,412112180,747651195,835812196,476248071,206010488,104147801,64044754,120665163,349604411,320793158,830602063,769986686,516909445,93338439,401779032,609921362,557201723,844078482,916100432,52150501,248197808,513101876,574308056,479400365,583125319,902427044,771647802,259236417,738591477,706739264,262131050,498245215,383575705,425638197,333795659,125346197,8884567,960626205,690277339,108136170,93208951,219509922,379683539,739781174,720059567,582382672,70466445,786219901,847992133,695542079,62935306,130959484,257539838,611285375,944874650,576522459,623703371,601157920,983913441,856114432,125942542,36137237,604374210,708462825,218891629,922516957,962575645,646661640,220710128,802193791,111845662,670879788,868375838,860017166,285495310,106139225,829154733,660163127,331165972,644561618,185582657,843856295,394289696,847591777,452761346,256948107,762849832,923359099,769787172,446995984,951166354,285302339,403276264,208126784,502739265,263907498,579471673,492084506,819280304,589125263,668436792,972290634,366259693,162576660,316839966,248431790,77436529,606357818,307440039,26237226,921453842,308179624,339211174,696572716,306702215,358545046,876452876,725193063,655877188,354472597,588572166,264016990,9647014,913303979,586351634,952773109,576377092,984359487,144458528,797234211,440547268,751798481,339069997,961234278,603316481,804420694,63780643,106977066,35968263,178998698,854236120,870111086,134567729,310520492,789864875,978151589,451078905,801365084,15961374,324662825,142517588,56924354,429894500,994558351,391185184,526000552,219127300,871810757,102920738,464031144,891892612,496828924,137603421,983722389,136699650,234534344,97014140,54428794,235545806,715901019,513264202,27020325,992224769,415613720,123575932,816932660,102115948,588956891,376818493,762845688,96967361,184259834,823431485,432715768,180336710,103329481,689486638,90601778,254976165,319346708,767322146,786220781,150919836,481156716,362816428,365082491,721465909,342790196,525241690,91843968,306619484,561603528,146654514,364489883,595811457,974580340,397112261,812329036,133660949,906363637,914861594,442976494,436518728,79331522,279901034,669867536,714134847,973958735,799982959,657152558,232734438,597714885,273813864,679058118,517188418,524925719,18650350,112919843,607512121,961517791,637682553,760847942,871072543,553426702,357322684,528456467,249342277,292601556,48004610,342088923,867033396,637672735,299733152,274415670,637270486,915745137,744014561,733060941,230478922,318333997,515822431,328516999,906676552,594794472,263908071,757536025,957504302,977135385,972362653,950070552,745784297,993164495,43523707,807968704,563464558,855274451,817706496,379796132,639946447,926283618,475062755,314570835,145158965,685419097,585459134,656771124,643466488,429092697,657632783,62715391,613266120,564034911,976323252,293123790,345929970,733533902,241856975,78740219,426656836,438737250,914365144,337353134,570650987,410638569,231055574,114095295,61405668,744737704,862411098,162082433,651583959,902289154,694719191,709164999,100737610,713392556,474024861,820013103,156819789,495799294,364003705,963140629,499072005,178573438,752769609,853502516,238346951,105491236,621247815,178163078,693965465,785570203,859119619,260100820,115143032,587240177,84239793,242961960,288426537,353090629,600307412,589268142,419999345,836028065,27002919,329281747,948695055,563058906,533757374,827894478,916463444,461406294,232833278,380757485,761612371,484836106,968817904,912335064,727424801,949484242,844427737,653499982,529468143,781329480,814314472,42046054,60073897,240047057,243668363,698698433,149594042,209012013,278341088,180313522,586554851,222273672,199163418,239861892,983120323,430872836,227883318,723621662,73855064,127585745,294077943,421441582,308198538,982629715,433351210,184479483,945135887,361588781,83994773,235803920,967460858,491838734,237426090,790480051,970454082,238946848,666827719,505817756,652624139,165757207,775718783,571575729,549519579,611946793,935102488,139923258,251627309,223521768,812721317,754133747,160294878,236555347,17464395,88401460,479228434,139508534,782188874,916104884,823517975,302244555,656869462,931190103,917092275,359754780,17418435,739046541,284248386,337683064,955944948,989926834,789303045,626413789,777248569,55784377,284836856,901274287,433300025,105775076,322643175,19140897,533535548,300840286,256626351,683210988,280538796,7251224,581025627,716956305,408176084,249564678,517538120,317831524,199438045,81728509,702804405,771780460,429043035,118159856,563089847,10665580,105009074,126343061,566712964,68341731,669849219,421618247,668701006,814548826,170188513,297904087,157346734,599255573,163223621,232906830,563280093,885347422,345416238,533115703,337227470,779876292,197601143,452995251,574043201,745268459,487079507,716093419,550488950,374537531,433101190,995130236,884060796,375549870,884547641,604571218,139086446,783640556,650921476,960225665,520341885,933820001,584048621,982098263,651233691,340439535,995552291,351024993,91477428,686187672,842845954,553396612,208118886,672219570,331496008,366146619,989217122,566382196,262017163,152770677,694665029,125148283,109037205,661218919,786886918,189884823,988689924,384634690,122382106,249722874,681366152,607052034,983398634,643395333,736170893,369732272,129059006,430095980,819400321,891826072,663327916,680156570,238667896,838777343,315602920,399376513,589876895,830717294,206130604,639999045,179696622,742687510,26015272,129218189,856247718,47883902,594602578,752728909,564272223,847222458,93372864,249859201,861268545,673939865,547446550,891510202,919714362,712125270,430090959,760196295,365797752,943167238,901837291,299381547,309264176,26775792,465995677,102782523,95800852,818336105,450806029,943016465,565732532,976203436,189001021,326745407,12421705,778808924,215103202,778415270,217837731,181171145,91078179,150724284,490578033,869639481,645973495,544859715,219046067,393547948,598322803,990949804,289622262,497046031,450227101,920051394,320131320,527550384,711036350,228774166,847097764,950259610,445504431,291265117,57545383,389032068,30837645,442070100,147253517,506914034,774867085,526897275,601491962,131613481,705345461,653575967,466049984,828963578,73563500,640901343,701209080,750144480,566371881,10094302,930283553,473819886,513530366,958105895,800222824,530236916,181697707,676527385,969318287,251631872,501886682,627959598,927509820,56713924,291211967,233786275,919860243,398099850,286033957,818531172,330583979,925259788,605898020,983060170,633025693,285742578,347275610,414010559,725864517,737842115,235009309,213957063,838531133,508082120,992606149,90059144,224286386,777220020,260652609,778091741,835874078,239863617,141977181,997670954,616044526,994715985,545031479,648195513,619115918,671963832,448287330,912833601,31541215,610979785,771079857,285830087,248343304,71966214,616768169,328542111,608902408,856443951,144755585,312637984,963147622,258976770,735908110,387793938,701783815,205203129,800874103,741735081,276626349,909827473,309378501,21489427,797488621,955444037,728882238,803291804,151387711,376739065,19105660,616516891,462308947,744180603,15920744,824978807,824097001,629888322,343913344,335692299,919798667,100282924,591893146,939459249,376211398,76826530,567915761,46519407,902219900,743791668,658992384,405453174,652292264,414496089,822019712,467392143,308777505,820316956,776687554,853725233,854687510,131180968,967025714,89103016,621169336,181077756,432744631,976680734,656279958,410641335,796231016,592686722,555690750,749585545,65353008,587098760,415837784,250264014,803879073,960320687,557090927,898055542,787224071,419274354,227420104,124798604,311728085,480710886,57868760,237674565,965413817,55496387,670859636,608300242,274413004,82528058,537368786,312026379,604619939,369237968,807566231,949487681,617385402,22364676,393655318,928728497,290193365,812586980,116700379,866435326,200389887,567941565,255518086,753989595,907659174,910576073,980781825,838327454,11360727,618087353,601736177,542503072,731795309,48419625,912260526,240291035,596135021,926364642,413597699,359729724,285107123,215517767,196457440,871579557,476546890,255311824,680834969,176225200,313776169,751062986,939995697,984892277,986635725,409930520,447806459,69518145,509625602,182805597,162908693,329625111,955667362,251575189,710723266,371893517,24563842,878436414,960673630,882229744,347935511,805168045,148227544,467425944,118012111,309456981,417220278,506147859,95014548,552971353,181777426,121682330,954724126,965002685,637941417,982988920,721560173,691739994,498428287,762556920,106534342,418337781,432908941,157300442,756630629,464986134,17637864,338425570,651935203,111708307,742684510,85574417,187601779,164216383,14073949,302676261,262126561,388213337,151148803,805379184,760902354,515850865,138362984,731573270,296186566,712800299,222198175,275642593,426561932,299020603,591757961,955457468,810764752,627549407,198585980,209793530,670791058,361176369,192091925,112233040,627397759,788510216,230977511,422330511,572472876,40389302,375638539,217704520,572779679,471994320,332535632,613784509,710915820,981858186,539517658,955814369,614504810,204298573,289435670,101737927,251096279,547540470,711676990,834644513,933680482,778353239,626768805,305752047,264621559,555764126,801031421,687372649,59719419,931476028,539299551,510073168,399433812,672444657,92059470,987883386,781769086,263920906,312699986,883288140,475195216,846218697,563758590,986226807,291604989,4911487,136369088,968350729,787380764,939264293,282852253,435193926,279146540,542226911,849278540,36125977,834245833,153397352,174728525,291399545,547506292,376638233,631257855,138112945,99565409,897693010,245611686,436528660,27183750,627048167,47698174,58577288,296752800,776321947,132078221,953846375,100962417,565657877,490674023,892393341,230029090,931525310,822826746,978093862,891034893,530176129,712126326,8923807,214866263,641215625,542083916,370393266,71519111,327294449,484909115,844669348,510045117,733000023,721206116,37668690,564711874,681305097,156949434,586846617,563317330,121682923,521554729,846629875,209934525,926699009,687330259,704509324,754481830,719426704,721833954,629027889,20437779,195764158,375268279,864159988,213531963,603859832,532236432,44215564,993055006,503714427,881697464,554996008,797029675,246134220,847788517,677555959,203955216,990196192,818466681,260043361,848064423,861716613,269053980,709863647,40329370,913337470,176771415,43397631,654825246,819702093,356785552,632004551,517135388,12309244,736158344,591290736,966890067,606689962,958997523,343421324,543940928,771864786,267937076,266514802,854928251,288979340,960996111,296266788,380161171,914540562,747645579,321565529,432999677,653438947,169502265,55351567,488992014,592235063,534469474,806030668,328377675,197200354,267737704,137737717,266544558,63219883,522942530,791640391,296740880,279785885,394489166,67363647,964953321,108527196,881894102,949120791,665456807,290713157,494508457,827023613,695556861,133813510,726381282,367916901,464344067,681254066,979321855,743816300,821813703,664938671,964675055,618043628,965933390,719589027,622350421,23808359,716423803,863475922,93671725,759301213,955878084,427195409,898192347,901216819,954634063,296839299,682012459,854343303,870437250,54626230,347641024,765852515,424636018,164387870,184349597,925079382,929293501,327250545,832451545,543145832,155725095,255044234,940133815,925999238,558744126,729394573,101597135,253545339,388444222,302355667,15407253,157397583,989144233,286233912,541940758,746108794,78012908,79388577,773236940,110589,975851325,995097858,656996580,266665091,229771921,499795889,205764219,63921395,859485458,620614180,743422631,368122507,259377133,886397006,656247333,903089295,930532055,856520380,802971562,913823121,697162103,524062522,834095789,507755590,375100816,735997458,142578700,487477777,467326029,319499922,258077968,470899904,812148477,363382675,743191027,761818256,59987933,661851829,897162004,276038673,731983423,262479203,966232535,62716323,731549998,284353419,85059813,865844333,7426393,123528437,811598087,642394510,355785150,574554919,900075340,447962676,485851470,114688818,265663521,833297796,417248475,597567029,788027863,884970448,191882150,844734922,848884447,800563515,925148460,86826054,453414503,597638643,630212020,304868250,2415747,211365819,946423851,405677649,379259842,703698963,894756766,534284005,300317036,269559931,307197085,472493383,537475027,675653410,613712131,378160963,260196627,8648714,67773616,36252366,337304558,588446736,385787308,53525041,291507068,455603029,468283507,774626781,241874949,599044902,78024159,481659852,744897610,416097455,202300698,743541007,680128909,868018692,792689991,944560517,366624646,328194435,432975623,592283643,381344793,95001822,892161541,131369886,544286368,692121682,148240494,914809331,102317046,913279444,618908214,910627823,902193015,590458156,855954579,794158685,480684008,897169599,
]
print(A[int(input())])