#607326 (C) No.1348 Split Tile

• 問題: No.1348 Split Tile
• ユーザー: tails
• 提出日時: 2021-01-19 11:06:54
• 言語: C (gcc 12.3.0)
• 結果: AC
• 実行時間: 1 ms / 2,000 ms
• コード長: 49,741 bytes
• コンパイル時間: 496 ms
• コンパイル使用メモリ: 30,720 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-05-09 14:11:26
• 合計ジャッジ時間: 1,558 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	1 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	1 ms; 5,376 KB
testcase_12	AC	1 ms; 5,376 KB
testcase_13	AC	1 ms; 5,376 KB
testcase_14	AC	1 ms; 5,376 KB
testcase_15	AC	1 ms; 5,376 KB
testcase_16	AC	1 ms; 5,376 KB
testcase_17	AC	1 ms; 5,376 KB
testcase_18	AC	1 ms; 5,376 KB
testcase_19	AC	1 ms; 5,376 KB
testcase_20	AC	1 ms; 5,376 KB
testcase_21	AC	1 ms; 5,376 KB
testcase_22	AC	1 ms; 5,376 KB
testcase_23	AC	1 ms; 5,376 KB
testcase_24	AC	1 ms; 5,376 KB
testcase_25	AC	1 ms; 5,376 KB
testcase_26	AC	1 ms; 5,376 KB
testcase_27	AC	1 ms; 5,376 KB

コンパイルメッセージ

main.c:6:7: warning: type defaults to 'int' in declaration of 'tbl' [-Wimplicit-int]
    6 | const tbl[]={
      |       ^~~
main.c:10:1: warning: return type defaults to 'int' [-Wimplicit-int]
   10 | main(){
      | ^~~~
main.c: In function 'main':
main.c:12:9: warning: implicit declaration of function 'scanf' [-Wimplicit-function-declaration]
   12 |         scanf("%d",&n);
      |         ^~~~~
main.c:1:1: note: include '<stdio.h>' or provide a declaration of 'scanf'
  +++ |+#include <stdio.h>
    1 | #pragma GCC optimize("Ofast")
main.c:12:9: warning: incompatible implicit declaration of built-in function 'scanf' [-Wbuiltin-declaration-mismatch]
   12 |         scanf("%d",&n);
      |         ^~~~~
main.c:12:9: note: include '<stdio.h>' or provide a declaration of 'scanf'
main.c:20:9: warning: implicit declaration of function 'printf' [-Wimplicit-function-declaration]
   20 |         printf("%d",z);
      |         ^~~~~~
main.c:20:9: note: include '<stdio.h>' or provide a declaration of 'printf'
main.c:20:9: warning: incompatible implicit declaration of built-in function 'printf' [-Wbuiltin-declaration-mismatch]
main.c:20:9: note: include '<stdio.h>' or provide a declaration of 'printf'

ソースコード

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

#define MD 998244353

const tbl[]={
1,245648024,728580680,330648209,191674863,421678599,763055415,246782240,756394555,536345187,421897391,360152987,572487995,259048065,347713633,201761277,743270971,801357509,444220190,43772996,975751463,104038365,621494557,268827826,700958286,779957103,33641544,140333252,4696413,140760728,811023346,695753612,890142251,724770477,252152121,77283583,193553412,925752181,203768372,522927509,230436398,954961390,616350076,641771338,687230644,202725520,288141849,875448307,143778807,98059376,777990065,747854144,389851610,259742539,997843728,658971441,125755877,769111521,643579748,308019939,535841686,231483566,255825586,325156542,903339290,899997958,521694491,616226274,98205940,375123259,561691914,493246229,384743125,192195384,255201742,335637931,95847745,318853869,367556641,268695319,311994785,121631498,181832028,915944106,2249566,171957212,315790946,604845686,689147432,315866561,872342036,739349508,653962172,900850434,947432720,183347899,837461266,479815340,177701054,413448778,766786010,155819560,930564948,85555013,791707887,299387596,598091348,953151784,426028944,638625198,700950120,674756472,978561833,373751656,87572339,557992731,540540808,12840573,529859845,107277026,841841596,409676252,791626308,110802462,618303351,663187109,6967372,100154431,557094195,867945465,900860030,196101822,841086873,525122959,291453527,168379707,837326830,336205365,900049166,119413590,378353235,126718386,126993947,319097580,305789340,712393996,281107569,810645563,134094597,82518231,512513096,798181600,214149090,563754292,141717884,254006230,33622250,83130922,364229147,6058010,89776222,871978950,430705416,911883205,689415312,254335821,872262626,267655194,829081565,653895773,480253064,849179615,335831204,161521716,882795497,250423118,929755976,619185072,218229821,122483914,724424295,208414008,45528742,957108691,821611357,343641911,953175703,855275981,800064096,985186593,693419952,264448284,594112456,646575573,393808799,763338707,169782795,109081351,665180909,550759923,705983787,112588059,838531977,655084354,313373919,832815587,154488607,822899996,959561671,714388791,784917336,109057469,172042469,559845497,97382557,291493057,703525335,386754947,865948121,813506483,684317176,849770786,769872565,652880688,854237285,166434408,682995601,684515827,743752568,110845375,769590242,719285190,188781537,74204455,251144865,158584196,147358705,755700711,688840271,605951879,249454012,665407746,351141112,38273133,778869484,573153214,660956606,718798233,331714831,341629239,734256002,65175445,203290760,474933080,938158169,352559112,883115987,368135702,214533014,644858030,53220578,690747571,185637984,368987475,115056660,485942388,837823377,371851340,299578616,8096126,949917099,381789989,54560148,526777455,9074571,989270228,587626785,734979004,978524553,716383826,60396366,883774956,408897926,313278252,931850257,282045022,903728901,24998056,362237232,721433339,979110144,109123781,368619011,758742211,971340984,689558463,408399344,15036290,817684384,142553961,244148993,130729259,293003556,921438060,761707589,857321500,572323962,791472974,543587085,976672667,443477891,138300102,662303528,429638247,596548570,419375715,96500468,958627350,597728355,510356813,57485441,725250537,403233108,4306217,130464198,602145528,167694669,874454333,242485391,11264058,668684803,673207355,640467778,282987144,806220204,299054125,901120568,448677358,622342916,463130285,200809269,750569756,120683539,405237438,733521623,119136438,126742621,769731524,155701190,369846484,533292028,305562723,483746526,301258454,179733434,494124292,504017476,404756708,358070651,245564664,909146263,878078518,850082398,885591612,296622321,701969836,10747848,151546872,293425487,101519513,946239080,125140025,181754055,430043481,67681675,248563501,369552746,984269890,390657111,508409762,533148765,136826726,389042421,504965764,620367716,800546409,639621757,920932920,839176542,432646545,588321487,649465435,703823376,184695147,398712734,668220045,833325501,886717358,237381072,330820841,210582481,169648351,445832121,885443012,472595731,177571511,354297684,209596069,726865615,32665178,145668625,830733063,94595625,313903236,756637405,357777890,875246426,634103516,807348828,57275608,703821475,821360874,367919640,589028865,862302741,441608988,194648121,157056663,314867682,529998736,816061365,133066473,216939780,259902937,912505244,419086708,931697960,126031975,748729572,453614599,720070615,801671460,959760321,827371299,146612202,446886271,655274055,817229697,163244519,728453879,688517539,494050341,654165918,505819940,151847565,481982141,376503367,360684790,290426038,685616754,782602264,512121403,740199269,265042878,597592827,27392992,240073616,454043837,307483002,407361402,173649229,248272030,578531593,481569960,484511012,540285475,722869991,859237437,693641770,674988864,137535234,851815017,739779196,907107929,385121599,212960261,452069884,280367328,993049025,171910387,955951013,12224057,33715989,248070167,270999594,41124263,986679467,42739047,318901400,193493782,215582594,916848211,147798997,645459073,903930765,330168107,70953706,179823549,285269322,87984908,768338011,909002661,264422227,270157634,381347342,731249850,917023137,587796561,16727822,230008141,934170518,659357918,382117568,100577609,863260948,971401091,816378461,735948026,512574572,744340332,546231112,786577548,560031469,410236663,325253221,853484939,496635723,529761551,926891997,955519170,380221490,140554926,21200235,877589743,55819690,186935812,485975661,308909523,82091652,641429525,14820617,324286086,388881716,704665440,681830438,707752257,57708910,497056729,558697516,1191298,724533551,394226520,74588060,594567785,81995050,911446528,570277846,532206413,797366720,875609260,422010819,879254184,139700264,12574203,924668477,240962051,137190747,485899931,24407200,972373345,176612261,617203649,50956483,415907884,646867951,34166931,517068606,670026920,137693763,962850725,524591154,253444526,597575970,663107291,442212842,354495218,262726078,689823853,869455751,604758486,129246395,993383174,954444825,465499550,278718816,321138156,528301779,259454466,677826221,307060620,511588376,604552131,245908645,97055964,216602233,949113297,4620876,922412543,532189463,20373152,585768021,846751494,390738081,146107474,683167407,39512857,242459230,486583250,587450677,163614855,584947644,452349402,305823130,137903670,448380961,188510542,637711802,920280484,538967636,770731027,129980885,595594840,869598232,85255680,785290021,815424910,672086901,873235907,206553591,84373837,150625187,257179321,812868108,509810712,863024872,794813567,164957117,522599023,740678506,626586935,251620428,821943398,585784630,136955710,573682848,478643293,996046944,564800524,434974039,351562428,579901970,690270534,89309656,233727670,518318677,930392139,785641653,331497448,322199787,855325290,270038191,941220027,200032805,823688474,947254481,751741663,743921865,384888635,125540428,380866649,492834958,252822297,713925013,523423802,896791930,471614670,619131324,784256241,816465292,933786704,86672976,794455621,581361861,683607410,88253188,938153878,397734780,248411367,567660015,419174217,765345844,826847501,139907545,383275103,746877847,50091135,365730169,459435538,615145340,538802850,864306267,893279699,141545068,840550765,596267097,579405346,264069086,148146604,727912837,856270410,9045244,460686293,204990223,368737608,39955439,618366320,213336866,351843523,608551991,959025710,709034272,900197007,193317762,823110159,928980547,961375931,146973955,640372827,483894844,358838805,764239242,207722436,205049005,759189371,399471764,892722022,500695972,373116082,202975419,62887803,244905002,977046711,694519664,735031075,677106459,253062836,872104429,893082896,592465564,136124251,728556724,439337890,862368062,450495708,121011948,104026264,825102236,174896883,70099022,659862408,506346610,444263582,344935766,947002981,899319305,917281823,890515518,69382403,768148483,957317687,901828100,202149409,571876409,258140252,917681530,238525271,295610578,668420779,502093949,686667267,21874704,513325774,879013437,304983127,678823730,168638220,99009806,707164056,822544123,622100295,647209250,121615450,108661073,153432022,557520223,730768279,961995728,719648213,352812505,103593889,426659130,624745067,338688461,88418118,516502720,874354593,717895225,827088484,521985210,71397600,736907116,857530628,511842254,532734002,255147469,877499431,697698536,67466183,62214749,965203491,829760151,181283836,516788894,440439647,969355992,557059516,406400404,512798614,512396281,432585426,57288446,882984653,861937879,152068544,837939436,987552536,457047546,723564984,382376637,297173556,215428490,640708730,238068864,600713444,727187198,150951833,624461785,738826510,128321143,822364551,886840242,560570622,756099353,28092192,533502572,622797582,191050347,364052147,602101947,481225355,919921121,151718610,962817347,712597268,307638280,974019893,804789647,178367714,641742258,87823958,165239668,363478523,68809214,772259538,92114999,673148008,759221877,894847782,624098639,47981080,850657009,239482770,409745215,516516930,556082881,771668738,89204993,615967294,862002727,385811851,444894901,693224209,925346721,806908844,670909394,431816332,136675407,285971141,366335529,984346522,161979166,347509730,423288241,336166627,635234446,502870144,65612938,994956288,216835933,283202046,374350995,677626868,794913743,883218260,930051427,740115545,841681287,322102066,704714366,773306960,501262987,919746191,32452670,428009750,668057441,86948451,769393889,532034369,357493956,630250466,774583782,177943092,429957337,326259300,574825737,659464066,100827527,927795346,34447994,103119176,811492921,891119018,470966352,913186565,461926630,12298863,958839994,712618372,659805094,841389403,408193890,516271019,588914981,555331204,496031994,678200842,169065276,326829914,714597214,38815011,4225205,393641678,1496026,716526017,721398773,976589688,804444413,907488787,171553368,772908384,734074699,647637866,729616597,284156280,578090470,595940044,450598077,94411269,98711221,406742425,638474417,4413297,216590305,6654076,21499522,250192629,655900432,984644340,693327654,763223667,524016245,597281855,974690773,345566678,677597832,481703903,312889357,225232215,796047590,988733118,347459767,134969244,893082849,521705387,169008059,135803799,727543581,137395342,108890829,215607132,296393492,405961141,53525955,168801264,100082970,853533694,641590309,563136567,906237685,742289612,861645144,558510249,805964824,795724182,816871437,513986312,43498451,365758861,130761190,740854579,128284758,709073071,188321083,326944925,527391923,82421553,185201605,159094832,264859205,150289914,975414757,40966053,897478657,668556494,730109003,794412966,618284283,691600971,595743115,598948806,497846530,951721122,33739714,185984173,553625601,489257203,733891647,363631365,478422677,915986934,464640625,173045001,838961691,935282394,417292736,51378125,530213718,373482385,250713605,304302226,382252956,556298652,374733922,558030088,977632014,267348394,599036833,210907535,204383181,36825916,786368753,389905576,154765793,925600721,508430016,275779213,951428642,200245634,604757115,229477876,265887160,277953602,158085104,834145587,850180522,351489322,958780420,963225798,80757829,52041304,516134909,70666519,462692339,436120271,596441744,499852368,360999181,907177076,135718496,43454099,193429198,803408835,811904175,379731622,456641737,730607813,487407568,732699229,222358863,887266535,348646378,5758820,70170807,656728474,941972006,74836084,794047230,554699414,714232719,333196518,472986042,598724988,345514813,41039113,595911539,615464186,892067922,257972713,209066955,358617063,250367363,250389996,648729682,681842527,164717045,343669928,342917623,13266738,433885674,681181721,267234739,604716730,808781583,492938298,544737266,924895817,488812749,20359657,844496204,599371492,780542896,708702357,130588129,849254567,831027461,83867622,448509233,7317893,907622576,590344957,771007334,703102941,724180762,958669105,953067449,351538985,489440710,203239342,95609487,180489445,103549395,595106973,607938168,496259003,239053733,351817096,336282063,775400673,186793919,153428388,702434719,815836667,763939030,620579358,67580972,67828542,671015813,267933140,242585657,668314784,443814994,945309733,704606306,658814214,304943263,922954052,990410617,642966139,89877512,418651313,49191889,634998013,432055777,376219092,747671623,169745560,971598374,495646258,714821950,496191866,964515733,389613084,235647948,302345366,626455548,25967732,163928884,266236949,848907331,979471009,495451255,55637582,831671663,890423535,233969567,633639471,669270419,611681093,919643864,431576343,82026208,595896840,843727549,776412503,194817883,750269260,282551598,502284008,418908485,888868349,948798692,410363272,388096238,355953714,773050273,802658201,237814080,739443025,409273550,659087857,47474609,832542157,29666556,960948370,803498048,756769809,782137859,224517677,318407303,698535473,95340122,772397877,69249551,801354171,456559553,520776890,424045942,150946609,466034472,50727692,264078536,731095764,743467090,643186484,188897319,19340365,158457081,242835757,844115280,164978276,410870176,774481552,44733041,132277917,672397983,918549864,455022663,506619080,815094860,471174795,309261371,604837966,256579692,619077731,196776629,676344761,20322422,360960238,47140072,11169952,414122357,133286646,846442763,76593698,470204771,983288184,576081777,228741122,940826517,309374134,430377561,392484893,299083964,74915433,483680301,446891073,705477659,489268195,780682099,425157849,433635135,803923311,856027735,353615989,573977461,614318761,677850030,809263947,49485775,170602813,325224960,466201115,796312673,953449925,470324594,782743350,117356505,128485433,636364825,826668060,814050222,468718359,765271587,622427432,865401529,712190695,751162992,567149937,645327324,584228059,712855736,109831081,183577543,176418291,547645246,329833646,545411958,91497872,210680348,101192149,507826796,551092979,714944268,420064275,643658407,224868552,186818222,7262693,470588046,14332228,625262204,989505530,853079386,55734361,957463183,93164986,409649836,382487541,905023960,685683318,910223899,899126996,601007766,686599411,44166003,449953048,450940487,467238521,935937727,232334110,171589300,142450824,245422289,55517734,988103910,729323490,670295085,420645018,477250174,844120768,584586528,705689869,758893596,220212108,244564516,911006138,450802076,551301787,801513032,866093842,938900082,273003585,29917912,79854692,610599072,928396312,735388047,721227543,446540191,154567837,766766525,184500453,229818427,93234822,224461985,821007666,160790316,466717040,857335311,148150268,770464550,178855016,398369614,952956713,162063245,607531836,600797694,986569134,752768082,546323850,431226082,559549556,536727524,695484837,374810270,204595061,339387736,265329014,176757804,61531945,121285825,914093308,765802227,150521940,692265190,44193136,453014438,478438046,839893217,444798024,94976999,179378993,522142166,882257754,56038923,567086801,341348304,656772140,820484811,366819537,185226044,602890409,195512787,291849553,632664953,196667474,993133803,313315432,612948691,770369951,195109303,230438528,343803496,323789912,479691975,557445350,228618714,753734359,363180774,499641868,361536782,391773139,79194609,299739540,741584888,710596105,185330664,920971338,878920688,425112794,361755804,385036433,684314297,203563067,965094561,232380890,179251015,59007635,829858389,973643287,882179668,580590596,579657554,38548726,985235123,243254334,795186880,753800990,389251,111843037,35932350,334726375,443771151,143607274,331996405,754288736,508261257,435222591,937761421,568695669,62286712,224306807,123626909,179793579,625026522,356070990,41231919,590485756,899030513,577460123,649866538,791979832,583283073,888271336,826132591,956177070,226193291,115438978,405460388,974257732,83346559,103813187,264940869,667457479,735969554,694156180,101742620,120403734,238711419,810812562,603141919,503663852,543071830,64078791,35678858,585208358,262452289,997246813,831379005,655825861,902168850,31847503,738053422,658165254,146217525,306659171,800633185,691191800,282163025,957704209,852650131,243588028,93036371,344141492,11758495,717812235,397311947,926520144,816375322,150740583,964374461,103404592,954768060,776685205,147390944,952764509,924114633,122068861,396150518,279410026,603902980,500250719,886585995,473280622,730925584,200354342,335345468,905175880,633921619,678820639,232360575,634506677,864274710,934325266,232689422,56238,417661148,374643238,533273651,507688622,455715166,837338701,158371682,857545726,879804513,976316122,26357493,992494785,572585299,987397559,410467403,308638463,465090019,936312276,463752698,374922710,657001450,717508825,538348924,913893568,801632633,855009713,886116866,735791540,34861032,731183756,659868883,710603831,420897094,804000678,229909332,758034299,28117376,645817450,86666360,771349191,83510214,911958618,808199618,890444757,139413297,156819696,139054309,930643238,122045486,616044762,734758086,571189670,336507178,786307323,218641259,717161734,110951388,604775369,98497644,856279572,162272601,271449887,575528079,259255396,261351197,532992861,29564280,310993971,301916548,615980223,45272195,344160029,810372091,127731826,745077177,714741626,859832289,551386742,147709350,107855499,674621524,568694232,72092370,646018430,883218073,898903029,839149631,310801230,914004113,551550920,570774295,995930013,934879808,592518800,229265039,103263429,863523053,129486137,379271818,561069894,763562640,924921297,138270256,175053324,972559028,217377688,574896182,900920145,719314810,661952009,151244367,48581228,802871193,14443977,533564073,869722024,334358004,927074517,711782089,265114678,228159059,112621876,179820689,4097875,767021612,119150012,446609453,69161281,54441174,213735112,574616068,33491375,789570196,896662938,122093041,87559711,641834759,951852474,502055341,393975179,37677460,915987973,188466602,462891631,120912557,582779580,661623397,734013067,796964611,879809476,955375443,895838960,553946768,544713619,640480499,480842343,304905149,487028090,377014406,720782780,600828402,70778489,194243927,924531926,711149796,342497624,4095456,861165803,551583822,367795291,989725896,276565990,221610082,589051145,654739122,755719211,172839014,742250968,73193276,525106737,689717047,599450888,2394445,324220006,197794233,461197783,883547591,911210287,991594157,555270481,111986661,627570408,570711249,54733692,192432996,338774051,813618876,149149437,825489299,16381385,467980732,791089003,253100481,919586916,206662314,37756533,65287286,763979677,920062576,532251158,558056129,610660481,950173883,899592262,302594460,79901009,743795022,436086973,613919009,766823690,31989687,991858614,426411882,784812994,566609318,79381320,420203374,819214729,835806362,76393737,285694730,589266038,237634975,202570404,831868900,361208846,375347855,67297445,608950164,727633170,347079785,365880553,572576132,202482407,468526310,369954763,108579544,231029717,154837693,567220062,762197188,118965866,910060196,466170805,683003246,221572288,750552452,212568358,260152896,747974225,989501894,265492641,137497786,627900870,717553382,607177113,264606080,168799974,550498399,773252694,354197040,513560372,721409777,647216567,607696540,583059655,673990227,992583803,94848689,169774756,121752558,172727249,848195849,599390472,548398730,987810983,702484181,241477867,212918080,94269934,54841803,398121678,490769443,808122863,596461726,923005441,448380701,802990504,671545044,961178585,521895515,94015505,676307980,392828333,923831102,187869912,58951080,93750358,334358035,438492267,982175129,713177498,743899362,152317912,887639871,257942361,652673803,690293669,663688987,374342279,676372668,204040080,479578589,191218354,630711843,905791683,924069219,494969343,37529112,447952131,526761051,464024212,827200973,104266564,261522976,910960607,831961997,804815374,288414746,199400045,147716170,157793559,689772935,102470254,842150002,939645039,351827305,276728145,950807363,512634028,937070023,484798649,763615043,421748163,876712294,525826717,547920047,840625801,453667779,578129756,992520613,328809802,550029649,498752085,709688266,590606704,495680316,366821510,374873827,588052298,120805873,378640611,826215321,45741987,324983231,199886188,404046008,976564543,177466473,477822042,229961612,967373223,466274448,796122858,774661833,439333047,827709326,808180930,697293323,938211304,283970834,952553053,376804274,465507934,907952749,155520945,664355026,167246004,326133208,108704413,225298321,855287064,308745688,218852158,724261094,490420248,627609303,695387402,70511250,705733280,105811398,428200186,716641650,73999624,411764688,433263529,80186953,227730670,957286154,174016609,952395021,822076374,259666083,954052604,825415245,346502210,103331751,145754488,765033158,158297458,787821784,889787865,862375883,965928589,856743968,185093440,458878220,925511864,361693672,506646665,899075088,257133404,377241158,265864138,689841498,681787958,862798873,310177156,566817999,427335092,873738347,362862727,435206278,865145032,408525348,100646474,183877794,246760179,991501146,125600946,963079204,962581952,480203666,101146328,732997090,297023785,602519295,142593899,402795667,415527963,707822184,30522038,385208792,665496660,164742409,108841350,117661389,41355671,141277570,114188120,590158318,697484165,782737618,676953039,436451755,611950656,887115369,235748302,114925503,450302344,978173898,944912057,987568692,467751831,115081646,918176434,939102402,8905538,674175029,983140002,814907297,815188355,449233069,385100324,763874992,899457810,520629348,527790248,366619779,406849677,19462971,956974460,271215688,221930048,955425167,715245720,289172393,111476280,186032922,592788131,321001241,266297438,563758093,799498577,382496831,559000005,856455769,148851877,426208292,879009134,238333284,775087041,583192598,50528991,835994417,571891413,771749449,310932423,143871212,452604836,767679377,517475868,475675336,619777993,651004830,207692672,166013555,97885711,448246256,315599780,691507295,947980093,827957947,273848959,547233394,728692092,671873508,394306946,625570787,759558977,216607413,542356334,455670373,207441172,248770047,321231108,333612484,624196950,188900152,698913755,43697332,877640737,297315235,604557884,106533239,360128745,819652328,870749337,132885382,356419815,166638148,35897990,894270135,986462681,155640407,262780169,984908756,782421637,323661046,539228802,460001104,226146083,228969738,942702603,804079539,178995467,318489111,492184712,827665604,868067625,636941989,348455819,353588062,162831225,109140246,658175152,723620981,822990427,695444927,844084681,515783241,791053630,206864298,336523409,687204050,708320821,918592795,23485517,390683290,386626575,502023037,306667554,699920905,465916649,730453482,683127962,766978504,986434242,951377631,65882917,450941013,4616616,444824752,863252725,852432203,834441468,373026267,183340647,110897230,666769578,664114720,745774889,126808862,392010703,275841476,739821132,480406438,345503043,292406384,177502968,536427223,399283786,230686068,664219319,300634900,565656991,941146766,155066226,989296698,387444360,791940694,582520837,167816432,236394540,106384964,980229147,178888928,296247293,801781897,339969399,831237314,32336979,925986760,550528288,254191128,841677203,80133966,699701973,745525006,99807036,119541351,963497691,541720529,988645838,208368872,570360667,224857865,770600433,938845551,42676771,84299584,43143532,977122895,882058565,145645731,83209157,208432771,740191097,437299658,444360778,909058245,695515114,609110,475047913,256419515,356766441,76466534,877051441,799444609,969708497,251659969,481292463,417022762,464823153,452550117,859927667,408089659,928889415,353700199,349428902,583070558,483913349,608297213,619592086,433860503,947120217,986979408,350478902,865553417,668301859,405209069,900670215,492051395,427156531,197620362,89842879,852035820,92952967,223501499,716603123,35791293,554902554,392240355,923885668,665870049,86723022,489933301,864843266,435197806,618032392,669311727,647852792,287147086,272086491,371584155,216371205,267058724,471699741,870350138,506315330,583077088,974499863,357440745,291877923,618325469,741198194,55589942,141830579,190805367,984072630,145588124,691925191,591028836,341375099,647251727,23182409,591754121,748611277,278334016,636138261,10312419,223856568,835891031,658230084,388908561,221247579,953802150,307080361,737097800,344980056,829075446,971936735,488258456,682595745,852663314,321176317,147658127,321498106,76560873,349455490,696164220,415867367,457454603,996513531,276107980,169023262,868697318,801257589,765902818,435835353,781545217,700340448,385317116,200160703,491773394,146323630,253050061,758006389,580182586,606451485,211847672,426430536,958987752,753809454,689311382,157420224,308761115,440147910,201669794,694382319,106849577,654602231,624000988,596268367,279585805,929934455,933507885,392204557,687349381,771264188,982196247,938037146,390006695,345147838,231486827,442602507,788638832,428315851,985755540,592632950,640852354,923560013,496484454,422575500,832944090,673218827,891268607,858773611,974229762,859431938,464284111,570774671,461834160,883281429,445575464,760581798,953786180,170116184,826820044,44209922,336990016,93585181,337645705,221571557,680527105,206439466,294993311,642134791,137940105,22533413,710721347,658190837,214816821,250605338,883870744,192299115,581585817,165030365,259942373,395051341,79182440,729149184,127278349,453417607,723970056,356772172,199777553,867796436,796950957,455254097,679675984,733008841,9005196,272633433,540250216,535062551,228586,170993679,130591525,356459641,278253763,864140634,346346560,874207629,527832013,838189856,940077719,155058697,263800428,722098577,994063907,213346671,642399950,276543026,686021893,171634855,761382866,477633874,517358816,673861840,17809503,584688874,475135521,163386531,486250798,719995971,54156857,156473093,553009102,995431637,122652878,664732685,331624894,849770854,696814345,507734716,436158931,759805123,320757839,302834610,122614911,393766115,327105321,796730880,893651744,702160511,690632667,428458077,719113364,529547487,353063861,499009640,902239402,901569642,611526426,93894049,994532622,974655727,308869884,101544850,727399383,550326014,599859938,351963387,812481884,923283258,992404668,662739926,521441610,278487759,824756618,107607423,929644965,222279995,70592471,628639069,56430012,489730143,429096502,931860306,833241792,840125476,452239202,61965534,130495309,927319608,168782293,992673741,753563893,164490752,303940483,930210004,402280712,790702672,936348937,720490676,650341450,32276925,900784798,814985429,836686536,549438219,422553248,371032563,264792610,488639359,151714565,79751334,285594383,252606640,809811568,124816742,368142749,621449942,403718858,994602366,191274655,341608839,962488818,860257894,144217682,978898529,36169064,420549512,119083440,477067231,834705197,744722784,575189092,480532678,971022151,652212162,156543041,324260427,954426667,278646656,396672625,599941321,962720189,744124459,107998273,226700706,68205703,238186329,326512726,992362003,144395004,578547416,600945512,367365905,129196450,659331411,580079974,129531170,454960817,572660051,791008471,98727787,100636605,777692148,605674535,718349077,899466695,829245302,236794842,816396469,351852032,291257374,81962399,335815225,558661297,262345630,931399272,635691979,644418312,749225414,698437981,944966542,532772816,850173499,953997195,407708485,268553616,101592821,243027886,444732832,636457868,802377956,426242234,540550713,524481608,979261383,663132092,278501491,516396135,404773775,195797403,604071232,972686397,607856947,700691171,157186928,530895267,446974968,139728260,918557010,30395484,564009946,522605391,718469529,148135730,413204000,729082401,791036108,565616181,607975584,330469841,315596400,552244330,27825421,638210125,105725881,469140370,18035123,136681964,409614776,453751615,160537118,668828318,529173337,623098996,430526580,391395733,469717793,182158160,150959679,544601678,498080065,616867948,177719476,79380722,227022149,477815777,732448466,843656716,253353402,579446584,27288167,27311330,911856813,758853533,251882611,732809740,65370247,657605179,276428824,118402999,281427355,859789053,528448199,149464497,198201645,950525942,647152851,464391613,317233725,729241639,52539138,379159862,343741298,380028083,172406053,559681360,703877018,229812466,76700358,23124063,33175976,127641107,899470214,105241799,334168084,192647624,390338234,559664837,368760852,456332090,16854599,539528949,967400881,605812555,946216711,856134673,481892255,776879789,317480110,362160888,968469704,362479185,103570228,866982940,631251383,951411579,29652503,824041317,674330160,414568380,707849239,778583968,159066458,625740111,348851147,837615317,617205611,862916931,244574980,163087609,624173893,949234070,452284117,514500359,86139696,362779546,439502000,934613922,388303027,671778097,385438762,647791638,602934978,289378299,242332473,964946573,407296568,131054087,316951139,28076425,762160621,977944474,289242567,953018359,475869330,216151553,671555600,359802705,997235763,892821695,91541240,477398469,636972072,63512923,262527242,114938823,981268854,997266795,382810431,832725339,699529427,268593140,108956484,523555259,966494032,924246492,904307956,561554546,119214886,119065230,336912662,113301922,280707977,998069506,345640463,402318186,813715998,1821367,136190586,146059097,63664489,899433644,781468309,656915217,770075598,241334181,930042901,585878809,736333471,515448011,802594622,675655870,245611883,729026334,481543401,848726106,685459360,356307409,154566350,80033159,559881227,328816537,931606245,406706750,981063003,551751100,210062902,838511743,827827769,330399611,683469338,365528292,23936396,587990784,328876712,622329362,914052230,918150738,72014046,905555068,892375236,981000093,259244730,254378507,764362623,70052851,679792442,856249495,973054226,121161256,504226579,494453831,961290301,772880259,202218451,791799370,322074119,804818093,938583555,537898138,835579067,956109102,225686426,180517777,38962040,11253139,295807985,949283602,849913825,1076024,101194586,86749254,864988450,409678808,394153825,782831775,819053205,208562210,392999269,331420666,109754136,892343205,218998710,631266813,76015080,544856170,144336764,520936288,701498703,555694834,937022791,795743461,943472786,783225866,258313019,749392869,687141788,476549806,181659379,823744656,732186546,57197284,90138172,312552766,735359362,410157287,424041370,743970018,519295988,571763635,65547835,846130805,885271575,638535490,494217065,547618418,775645247,121678346,248652405,530726474,441871609,51688470,586197923,963258232,182928863,896046514,832713887,82800689,651475275,481576203,141553359,888553748,399537521,359370175,518380027,387488582,372763010,333087267,862288345,137914848,819887264,325503837,146672150,51652305,974714290,517335586,421725143,218734938,557821657,844567678,821295863,717405198,988694802,701038544,604553060,307916766,62088313,278109992,222190096,403404424,685130851,89359794,617242571,772468369,865703787,396227578,828004666,755038370,243489913,4251441,132784012,982376328,568080889,981420190,122294341,156630727,993397072,119790231,209084336,506112642,470736487,377659283,265058911,480739928,937391711,170546532,910462604,440857453,157212849,542919363,57054452,768293538,777742346,181070883,509427451,972755153,886087298,243246376,631852174,953413533,525545052,34804855,748539366,907644641,884906787,63699813,163337790,800248168,331974070,542532929,583003283,545768546,106281262,755400165,79530840,294390743,298183636,144825638,222673823,185028280,423612431,332109173,891041691,233264699,273403497,697126383,445892543,752733536,367180455,975302283,326280575,525278986,91631993,451243323,116916743,313282859,207590187,327271331,440817326,424753329,875913150,813887501,897972505,492579315,682373929,952090889,481325926,616624596,800795744,414897954,609111119,875362021,655934837,530617803,381917908,371475408,72603387,791097655,262837867,950365904,516916240,902964024,699418307,823254604,122994264,258328287,476573455,398849114,966318494,646644053,446369354,572058147,496979430,568240250,397179678,959150571,247878666,852597203,657834704,532884263,965198699,629657885,437240858,87718645,185638929,518455472,11117076,498243677,778069554,378937977,66950672,953327253,259785107,536916569,911914535,767799207,8576430,207547436,240064845,608181549,116865002,669949299,166957229,107097724,193170498,321697231,789905860,165650317,73908908,969564405,572291396,756177947,644412854,443828073,579089,241692423,184445480,243664371,328472608,453390819,734817551,696871838,452527412,542726787,674568573,210946604,754091770,514259598,281021430,634943195,324167596,490223466,29207504,761350424,801842845,606467813,599347599,622003012,76590351,117979011,986952690,15931562,619111787,361700894,499145190,220024933,461430786,153402563,560262480,755938003,632279766,357687715,622646972,901095636,123225095,767661775,866756541,537787046,504255929,138894719,657379070,361919340,20131999,136025109,504586084,614225664,805045486,157125107,980486620,749647147,982551900,207693992,962991071,602185238,934349996,329272673,115561547,195513390,136670478,516537152,814040829,826498221,178220783,32490876,319119492,755185184,243749645,435189858,128116819,323799577,961592866,328305230,951527810,591091960,449106027,594706487,270358530,880723573,249463141,170015332,931896770,877691517,381841693,874636496,259831280,537433856,274718499,775739742,439727366,156971010,468522278,654037998,612592396,606366804,940225564,392585560,673189897,752722108,862023599,690451883,711794370,513157747,133569109,902107590,362134760,912881109,311869830,184239633,645484916,416696859,595035122,235834544,410462336,389477052,715845240,960868418,50281236,651376746,613074455,726085164,125179405,649453890,11414374,121597912,95190134,654410447,636432088,300880259,504593271,667732276,50294058,165851934,819686744,80365594,884705896,795338760,878758269,981012454,530863384,823584768,712333767,428614751,126639316,588506234,306266278,951158369,318830881,971617941,40901325,674244358,479455730,843042957,7518369,637575613,915983926,836067347,50557573,756198666,622355968,70607024,854642559,858753603,621351958,538320754,88672714,100214937,729483570,362099126,715301911,642405224,814362147,283148816,541294570,575754314,512864230,725022244,894506252,855897390,911181577,473623105,730576586,698831980,441709265,19060331,351171264,282209287,704594745,726200155,113887766,71335015,155460094,359596959,256841522,800450167,115945766,801629313,146433229,787502726,751435217,687286647,61580739,142337199,73149479,906750169,261746338,27427939,192283036,912014425,933125573,101508750,90865865,12047932,894019208,35499881,415155450,458501533,710546719,606878657,914398629,823240426,630381605,950387574,221918459,335541068,584407384,944919102,326263754,193234972,582867755,854431943,533619555,967774626,446058386,650975762,811549234,331426950,85834068,782519496,362781278,53752120,814377564,160544156,557580561,143495235,927123986,47183365,703917121,951610819,462217662,127428649,69929425,889157547,755255964,210674313,659393045,721900353,168695283,738001955,76895366,528115610,189532191,696925836,767174341,937691725,300421173,299853186,122461033,745316260,395479186,665179365,494231433,974731159,465275010,33552309,403519435,638417073,28291029,633742488,878780553,505264043,141013627,115306041,379276457,789608099,506772550,913835820,851554852,253296837,828229156,482295963,462461853,644928375,783732370,391514608,25471629,834786942,886940422,720346213,630495415,752803338,665124263,102767091,439673190,135011494,561653617,39681245,702385818,104106143,501621178,217452475,116460818,176173525,587055656,951755397,209985784,585949640,739858146,539062660,743593698,829806965,705802079,34680518,594898465,222914291,948533237,183280021,242159300,197901771,132826441,811709009,466292609,888236349,970341953,172802587,925832816,70425523,42981994,682485798,20573037,76683646,553337783,131840312,375325046,892702046,673030567,941552432,489311683,481304016,892313244,6009507,388200516,151663300,212535591,565302498,95355964,483563501,625575588,665533192,267018387,59151080,452694488,533346654,749316869,420310123,849251438,270104543,752257272,538581644,10390825,544043999,25322699,349241216,317006985,703465852,147950964,139438605,225482346,968296352,24690714,994509017,423185661,721759546,808495028,507035992,872950824,777049217,423478023,830590521,483098273,976765223,578236416,417851960,531784288,630527620,836185675,711456034,404418201,361949821,760499201,347039352,979365234,436184459,632464819,718964521,374493292,304890006,635237099,1684642,879169090,77314316,448067378,745112810,511829606,256858844,421372878,56810830,703027440,222924458,520541409,214482149,933635157,899018180,934199693,613012713,463174885,401123950,131447910,967973644,595725488,86436666,507538011,811213687,787643802,953935252,467658135,272095449,214091102,606746849,730739570,962804720,393478124,363039929,96604575,141451155,809656031,808678357,995418452,680950950,916303127,459589413,801815249,515186179,308049679,908744473,931043397,269182777,938039060,546546208,217347445,974640559,758925491,632905540,960477105,774614214,960962260,335389144,688114044,238868753,921131057,469582594,545388476,606329914,951218324,963100738,176305404,135057616,383125474,197237322,974099854,971634686,587859899,290826162,890301452,297340334,336186876,291368752,821927504,972648121,253942292,437244611,484861018,603013572,211993439,329435004,88428048,509621397,222409166,387120559,570131836,554709745,883673348,27012630,209301382,460236436,786023448,495946621,103483116,528364764,769620743,141178659,472005656,542413117,231165541,554759578,436757642,701749805,727104223,761712833,570999902,273330185,286461261,616172851,286215380,584373062,250658458,316565296,736068171,339702698,82164732,209922223,284279908,464940327,661632118,566887941,720243722,448142787,321771799,265666133,549644405,168495537,636226343,141881129,21277340,953683875,248549790,493977871,659571699,575366956,942458420,365249024,149872231,959490526,716976999,175389244,508353231,682124829,320859584,241186148,775548075,33132742,141943633,67043998,104820150,994878352,760458696,470195033,764974461,100188502,652090103,188619261,691375106,848444722,360813771,185571249,279608901,420693912,827215303,96370711,540747633,218401126,996304475,537141411,543325956,887285672,23074144,314746208,492703941,266146398,717775731,314737989,356211608,953947421,203589709,96424696,545203057,946383187,314171214,411040690,965924798,407495151,932357530,130571036,106621604,981861766,100984261,109903776,387289733,579932960,935915547,766189618,711197522,25652929,577626310,705623497,912856479,142202329,784272287,11913834,396018161,245528064,474284456,245485379,337308047,619025358,745566253,462140241,538571759,291029322,734486751,88427131,467428260,254159054,615491474,924788644,18463048,181539270,62384845,687224688,143911540,743705203,820528505,757797031,190425016,154990977,55492474,507033498,981052971,816984038,242180193,659189441,409100672,802012568,346398440,214325480,342476214,977042110,443334022,588409598,525511084,551519154,272546139,545254642,380479061,901372299,433096958,800513124,232025194,743503811,520856384,598205372,236264693,297950123,825801773,539870878,506918783,694605575,565657907,781123011,678451645,307459,782839595,970942251,92346696,848470330,964565688,81203816,803752155,832653861,664097027,124831981,620906187,128056689,92237470,610988457,485160528,264278135,760216904,668571204,462650791,317013631,646529932,326670759,764993338,307899502,481917743,251950903,11365009,114598625,817505489,766264107,104431497,160609010,539690884,405848663,325284932,451305085,320737738,843853494,807064344,560423393,951173578,336722406,736831032,172206990,108263185,60412221,46225588,574746196,68715444,860888697,942397859,352749684,14285749,5594981,561147236,554644472,688492815,672541450,555416119,561749031,149034105,394374771,822156862,503072929,724731894,910789234,948058170,187142323,608568896,276521339,303759505,845047731,636619609,759525979,441836942,688790374,838139425,787292178,768772181,276789532,17692548,517833047,171719565,792910414,532577394,103538275,679283151,199603936,525772442,750263337,189261631,74873820,121098038,109967207,264682938,406913384,60960808,404690112,995859149,808340445,200640936,893830892,865522996,873093826,189203482,621697013,438950764,75878404,129739588,2052868,905632596,3207394,376313619,500827726,379379256,168341851,67149739,552289458,225110851,283486204,638650382,151937107,911154270,536752705,176840316,538424968,321219488,497254008,166635847,349041838,321656622,170084953,525065672,281649645,7896707,495590131,301322570,553424287,601101184,432870904,371272286,38167606,543018068,63332865,571699425,152968503,57363446,197149277,281898939,667431905,853754771,26203513,727216358,349165485,146794905,24934039,285597798,425033035,265764814,215444203,20429032,399060150,211649283,598697328,130816619,280341788,420805442,722805387,982279931,94033504,549369024,587561213,450849915,555472757,611067094,708848633,985817353,739911356,216051121,217726056,212368042,531083234,554014894,675432522,729701554,263574911,555435230,786196360,142801552,515782953,16140769,11123796,280549074,391532918,104229443,262359153,357484644,970139977,490650599,294241094,40787558,700525117,67362579,529502843,353356867,673315180,333472012,941660926,780220704,723511571,597480854,808103317,745823196,538809692,627858957,877175347,569674488,993149209,925328335,105414802,829230499,154503215,481918480,379294081,544140611,21599761,536214166,64818902,114812466,439643637,609905139,448370143,581309654,840976285,569953264,525868320,739085829,949717760,254063802,384523713,962469309,437446630,329490815,693959029,990487642,461185271,215632679,289859320,864082554,37451018,292830180,64803735,435456727,131697058,383417846,59310494,522296082,75963792,746323410,256134566,511319443,380008059,850196338,7571819,993066757,85299558,689645151,318238233,763389328,710649283,925464752,166543627,325557403,557171215,690221401,790421377,54682399,635339142,600306604,343249665,785474018,603013935,367775081,91920595,308200120,517354425,154833636,827703363,710578153,158135974,265500100,223624224,185677785,597364408,141390953,460356242,848330698,428919174,857566694,764436700,935956209,121243425,738976525,602683250,929584471,539394514,608195102,875538282,42397180,495184624,19514854,196759419,238042422,673786735,235208224,437133725,485154245,904486800,314096409,980868271,801984364,717750119,650554490,129069342,14396379,316355603,607756628,575412075,438275059,848591638,299194612,353625889,654723259,610632774,924598178,908047287,100874253,53675617,374943905,691988433,796881123,264566199,935449102,476058065,194627751,278849885,959317354,195352411,84982716,123590210,91099232,789444527,334069943,762863255,246468788,377717275,898719940,728649426,430295189,309318298,323383352,55754051,162107018,403568839,916087145,634394127,322754512,968982693,487109521,939940596,768159833,336339422,588778317,438829129,531532293,61275055,90604239,717156071,741351561,447875739,13621394,920555103,624016364,910414256,942650641,905474562,995481081,424122244,503437597,406945740,116148100,524002371,326485387,483295375,408501412,589116209,229841288,440375118,909769325,530689802,981394137,119175414,118401023,615137443,399963196,483378853,815988865,812646527,107971414,651209754,357032558,189508643,841141837,284383892,839825235,770700,807768697,875054001,114421685,607246618,10249337,818680160,268534610,503598541,103858247,930098929,514959802,590310860,242108947,586577153,964981065,252008563,559440494,377634713,724251850,776320932,907861072,590169945,173241052,238283494,613628849,534904892,153453963,238943765,175524352,153999898,731332244,539306384,217696500,193454680,141845087,183239386,468804560,570963307,706893923,832296792,677367317,161299303,799062911,973767103,881735191,473592584,377528159,296227069,960134949,806393969,533591527,578248523,970388877,467523736,238821392,704795176,413462617,386464006,532531358,941502827,22222368,321305369,786505435,349768113,368807978,303902035,853371346,304100992,961469199,609772986,737049750,905943370,87303650,384602721,171068637,975869566,232872556,240154539,112810432,443294823,54465377,384720840,955943049,465551222,786428896,542279474,679670440,948896235,875722559,730106551,832912264,831017707,24573972,712864505,929258268,636329451,990741477,285180357,829037780,369331737,215652628,925025550,951264461,324871016,884129316,563433507,305949527,732671446,212311580,178074399,61465917,200910087,558643879,970779082,648748513,278324398,103153211,287960462,400032927,358613418,771714992,590873037,896253932,557367160,774965679,623037527,372906255,41799894,71010973,31512870,649616914,634981065,284244037,377214988,298225396,58582509,389564676,233291861,107498853,161128619,646066024,63032279,42065849,986342967,553515932,996365065,956542862,933399712,297592750,852031256,605470950,271818664,616757356,949221204,457847584,482093499,167659381,565591185,536956128,727346236,204828785,667083639,466118559,467082159,683176982,714452480,840092893,266130219,860608751,17626827,446164194,977878826,162720067,230251472,731976887,651494989,144646518,673366503,525669242,91701320,39447060,294771082,560988801,417459677,551765263,891194815,582170420,589777536,555963975,217754199,598203372,194452282,342440782,899333266,564435524,260663196,873063389,931828110,813099131,38251245,729240963,509541523,3808103,984780751,926434588,754274067,854404404,343993207,708868977,620472427,423760054,552369283,157625597,698925912,84729686,217514677,962077967,490368092,982229723,135689395,323751185,948720381,639157388,205130219,747435741,874578926,634945898,210080193,360947084,72281674,256521981,784941894,862396895,610874770,224064766,736844344,311661910,126616631,543245190,611511308,342078080,109099564,449550708,605422012,640468783,263611038,366341144,447499201,71984015,461525532,348469255,500499768,848545203,490211592,613489582,21522542,456956931,223935799,484257965,941160724,651301764,368394667,230647154,627073778,844664610,38230553,837806741,205132532,215567002,208020543,112664255,961106658,653145511,426010622,522998192,153585136,144386550,159236345,580370053,448850149,373824631,929717504,123132869,326897802,884460215,736436222,396567069,676217683,40829179,428865672,823466671,137531553,481798581,836214282,734880331,84533025,291100606,360260417,716571430,494796875,423023533,929802162,901673824,858962848,142446388,653783734,431923993,944504464,572193128,829285154,496690215,284389342,666331053,712129675,136072000,151750786,181803203,322805867,61474978,731005854,971235555,127324323,807884809,139109491,278084001,26384375,168153386,201256585,603665399,197532526,104488483,959225802,332583584,779515028,875416328,578657702,842271485,546848119,202284244,380256551,323798988,399568012,931756375,606943281,447485159,116256177,732642728,954027313,377413864,639600140,582403289,849466163,193885536,922585647,207525643,232702357,691677896,283943703,763421551,632616383,630096092,437546833,804888067,150184891,787193434,573010309,842030400,86206791,230955310,36091435,889052049,416846330,469214577,932238842,701447184,667944352,358484336,419950916,341879284,468392811,816924822,15095984,321152009,795055085,703848273,550682792,366226314,573457148,956681563,381494925,225775998,542562022,898882618,905614397,568463661,767555192,328789906,719694690,97341922,965769370,222697181,523746388,67221543,735888158,669457771,443356958,860753212,284776980,470704788,313863448,390787280,186354678,467629269,515837657,7522279,475298173,810926224,249383413,516951844,687122217,180167301,335076529,839185030,6304306,729261489,947919709,27711233,596918018,512673683,865180680,154094675,86838495,77832071,808584522,629565778,533584553,557198019,307742815,460182574,856397129,489802109,764341904,743313173,748699233,231565624,564985024,834502832,462487181,621428673,73855655,105074193,268604730,156568274,597139656,825308318,211885953,572153660,654890666,583670626,931851807,668746585,803675856,465515507,882880535,195855918,962914108,623701656,267644402,379556434,941460073,152469265,674805873,17473745,437615528,334127100,141119026,614645680,588309499,834884995,643540677,591476842,493171373,622999947,598022395,920193981,560043358,624456734,128818320,41144192,309264677,839187185,451575096,500160507,174271052,447020648,152579505,973640306,366498854,819229937,672810329,342626076,311862148,212189291,867972334,6252895,450811694,480066936,229793877,114028432,989993773,910795275,863085498,984486586,789093395,360823292,711584656,595086682,725626131,269091077,477801478,986867424,115423688,880043965,857185451,789583147,404556546,807099733,78721845,533202853,695824027,254112667,413558429,756236284,969379893,461326479,265922793,253928703,150461702,992156866,603852592,535103020,733385551,526414621,591771001,322515268,363793691,91071236,84725825,343586172,509400161,613828623,211074478,202271929,780047454,790122821,911045228,225243719,375608634,481681742,382911924,325046623,255245243,921318879,207418225,732481972,749714332,524854324,594374692,694702456,850980294,357276674,701418736,963823756,763933754,278230109,315664138,987012788,683545046,891202657,482506073,427871090,316956781,56844521,995865978,613626,83623380,760485487,9918785,204666301,814698881,386464671,919893175,215128888,971452323,138576139,332098805,445244568,705686448,902976950,874532887,456555015,804711044,367020484,92686824,165583576,387757616,136754592,31745602,723793751,379386811,608641658,742232625,95942653,630609439,290290784,463105802,533511717,986335153,694160092,94701733,750982576,496098992,136733944,94400208,979529405,589546446,760516994,840743947,881814878,496187897,690414175,300605714,978838023,625151682,838325902,473045166,96355730,316274921,456481978,510044467,452948251,481642766,70794268,895331872,786645854,136467885,587543454,826464442,362973542,636170441,452108426,373341033,
};

main(){
	int n;
	scanf("%d",&n);
	long z=tbl[n/200];
	for(int i=n/200*200;i<n;){
		z=z*++i%MD;
	}
	z=z*(n-1)%MD;
	z=z*(n+4)%MD;
	z=z*((MD+1)/6)%MD;
	printf("%d",z);
}