結果
| 問題 | No.1327 グラフの数え上げ |
| ユーザー |
 tails
|
| 提出日時 | 2020-12-24 23:48:45 |
| 言語 | C (gcc 12.3.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 59,976 bytes |
| コンパイル時間 | 241 ms |
| コンパイル使用メモリ | 32,384 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-09-21 17:08:36 |
| 合計ジャッジ時間 | 1,184 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,812 KB |
| testcase_01 | AC | 1 ms
6,940 KB |
| testcase_02 | AC | 1 ms
6,944 KB |
| testcase_03 | AC | 1 ms
6,940 KB |
| testcase_04 | AC | 1 ms
6,940 KB |
| testcase_05 | AC | 1 ms
6,940 KB |
| testcase_06 | AC | 1 ms
6,940 KB |
| testcase_07 | AC | 1 ms
6,944 KB |
| testcase_08 | AC | 1 ms
6,940 KB |
| testcase_09 | AC | 1 ms
6,940 KB |
| testcase_10 | AC | 2 ms
6,944 KB |
| testcase_11 | AC | 1 ms
6,940 KB |
| testcase_12 | AC | 1 ms
6,940 KB |
| testcase_13 | AC | 1 ms
6,940 KB |
| testcase_14 | AC | 1 ms
6,940 KB |
| testcase_15 | AC | 1 ms
6,944 KB |
| testcase_16 | AC | 1 ms
6,944 KB |
コンパイルメッセージ
main.c:34:1: warning: return type defaults to 'int' [-Wimplicit-int]
34 | main(){
| ^~~~
main.c: In function 'main':
main.c:36:9: warning: implicit declaration of function 'read' [-Wimplicit-function-declaration]
36 | read(0,rbuf,sizeof rbuf);
| ^~~~
main.c:43:25: warning: implicit declaration of function 'puts' [-Wimplicit-function-declaration]
43 | puts("0");
| ^~~~
main.c:1:1: note: include '<stdio.h>' or provide a declaration of 'puts'
+++ |+#include <stdio.h>
1 | #pragma GCC optimize("Ofast")
main.c:44:25: warning: implicit declaration of function 'exit' [-Wimplicit-function-declaration]
44 | exit(0);
| ^~~~
main.c:1:1: note: include '<stdlib.h>' or provide a declaration of 'exit'
+++ |+#include <stdlib.h>
1 | #pragma GCC optimize("Ofast")
main.c:44:25: warning: incompatible implicit declaration of built-in function 'exit' [-Wbuiltin-declaration-mismatch]
44 | exit(0);
| ^~~~
main.c:44:25: note: include '<stdlib.h>' or provide a declaration of 'exit'
main.c:49:9: warning: implicit declaration of function 'printf' [-Wimplicit-function-declaration]
49 | printf("%d\n",f);
| ^~~~~~
main.c:49:9: note: include '<stdio.h>' or provide a declaration of 'printf'
main.c:49:9: warning: incompatible implicit declaration of built-in function 'printf' [-Wbuiltin-declaration-mismatch]
main.c:49:9: note: include '<stdio.h>' or provide a declaration of 'printf'
ソースコード
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#define MD 1000000007
#define N 6000
#define D (MD/N+1)
int factbl[]={1,901854242,710379461,993385195,730966892,825186220,659189998,318732167,757403271,524916839,962349060,983251362,18014101,135447289,557696156,883502100,745118419,237874580,286641872,418806824,347686624,954187495,751843235,669188,850837389,909987544,64973697,584887416,532400613,372426386,335860618,81767053,683392236,563094647,149939995,398194257,489743711,12863919,499295599,521334173,682028241,10166295,843326065,41082478,154864948,286617716,483755159,551870682,749335061,939546826,112079068,258654345,594085552,152836035,662907021,76966521,442169569,707215358,363789996,696156295,144650061,915502730,426885988,451452165,713183088,487868034,378181594,549020097,530786532,452797764,768827995,296491942,25110468,671320111,911165839,163524463,187943678,164481947,60429994,591322754,930155957,99238685,485237336,219889733,267131237,906577487,653717312,593593917,444928890,832326451,928117498,932044213,210103099,527506258,380398807,623116780,383842542,532637425,18431791,578251004,405229192,64658479,822062320,90000626,747646526,239578401,416581632,140292103,932375233,505822419,463328923,855591131,952449144,783129993,345876444,184318391,334923067,615334352,280952906,716022726,318732046,305806232,478078459,426786847,427591208,703219718,911684287,291556714,936759039,316975671,556740581,347766463,725463896,379975652,535016165,319038474,464188011,16519168,640891368,266105107,482687363,7353552,845036979,652265532,726441979,149028352,223465442,626954818,96081238,217003183,167808926,263427652,251016795,503390561,217840711,357240431,869764997,298909114,90830455,69658095,234150138,725005769,533073859,787363621,98300125,498900240,115918421,358569212,778865557,605043177,259256952,398018287,234511144,202799335,765850245,727516717,415820802,751341869,801484047,513771066,989944088,674223705,826287889,667577097,520964511,560445539,483486099,347222609,182636607,886251424,986655145,592234457,970528058,888591368,129724411,712082734,990728676,857087136,641209760,418712113,466830835,115177288,263465359,814205172,914011496,936199568,836822176,946337770,274286342,71970405,236482435,441159335,59433187,381309250,737612046,323194871,788928994,318137520,884065796,204448328,975474110,344404866,396459081,426507075,805640083,824441526,377131480,882394875,384846871,873718745,83597142,295483431,22502382,529745237,770392763,163932862,141332379,611850449,591650300,119271291,554027257,553428074,894092424,414802901,159742164,233142662,773692414,534350073,171312011,765417640,906322862,249131845,129962472,341258707,525724779,488573424,494732295,968734702,638074197,899287299,836031131,266756803,320454767,450261688,626876865,679555528,957152893,192765465,448611613,700811575,874984121,369734909,539323527,944168219,637632263,234173288,369123925,382923861,969455657,60481913,818089161,566709984,148718550,631972462,357775423,989092825,647387790,719047106,937873085,103595501,863399812,125882795,345486659,396965307,848033029,29710016,240236583,972225173,525519828,803012208,222278328,497110521,676899167,810053131,130521052,341687341,482472069,453462683,501244799,565689167,972032603,453205060,309548182,383464534,417790273,497980254,947756949,306977023,346506420,720933709,390595704,236334053,388532059,208207825,952251877,368983907,362855369,40082079,725370846,192647634,238037566,31365518,638463887,77878699,933628033,25059874,110821137,948721874,795113024,547720725,939204615,157850174,27325330,299350934,244041803,733700336,893466586,772325073,769103266,705067857,720624859,501254119,629003160,674970567,785173915,327602692,262659185,340290324,685185519,797984836,466803699,142708125,827031980,252607448,187414141,64170438,384229381,629537425,343900314,301391133,702131109,130111133,367243449,137601229,621561011,343352642,883517104,597502080,553839192,310658562,40241143,719135740,588484294,562289557,35475352,446159333,395513602,281911923,699828504,83477312,580754176,41693097,691858700,741615984,590242536,308694302,282630811,637522515,124309890,268011565,226777033,68236991,855008763,139883013,499929597,801038547,954441596,174230120,513879953,71201314,703168005,654667491,678942949,470033802,206775184,392500458,799229891,170528554,562574667,405837221,893194234,530755765,961163830,906513741,505662398,580743518,322778562,684890680,206451908,550247701,161849409,944150066,688090265,270207186,99432753,217255602,495138822,460403119,462212929,429148299,289426198,998742681,124480772,885646791,181868623,881573599,20261017,428858037,202715758,116161296,662442536,925088596,541564621,531123857,998024191,493026332,929550716,744105701,441079767,488038857,2870793,119093397,804511564,840214862,492806996,542748977,79332826,916558353,317167412,940722344,767574644,917838057,631992055,262129097,435303256,448484273,664154460,659191541,596310171,29173397,419071868,684188823,205632344,341341470,768640301,558872412,273963319,687995056,288707677,282466140,668781969,850827599,312373327,198145088,787245847,226436782,891968429,175746790,627087120,507556051,351035201,114367572,407754825,436618054,684357358,127584752,441371395,251414955,924081077,943137544,222202249,620112238,886998195,90440364,802483907,73454605,913132521,252436454,712780507,569460926,963302351,968337687,957350608,608737317,403280111,46002034,995053653,504481628,464326151,740421129,300946700,981274179,718158441,371295964,512052698,517274487,417328452,839584048,961936648,63679996,840409328,652712900,877108171,5635950,860707517,616183852,599100549,755725818,224261915,487012626,782560461,106542636,595749254,780684555,773544769,883413861,345217082,502118220,277832562,632871234,96868366,440198480,352613485,721462034,250310206,523242891,667356518,401217419,246371873,567787947,886943240,99046533,14988932,721074837,698261279,626576164,335026418,246715555,731308068,503052993,622746358,560173727,324092758,94437697,972803174,97775616,341076947,7978025,80284635,318549262,192054171,326819157,708083535,895491705,242106754,89715785,539520449,235325625,233101421,665481887,392201000,342732873,76380428,827710661,366530025,501241942,538374640,813101609,863960376,28690354,502000127,458427266,95437377,107926521,250663377,100693603,548842624,99039723,884232876,375445063,220125567,320668309,775220278,919278971,76561108,245769276,829790680,43697508,334331482,776673174,984010168,431286147,488206966,117580996,821423724,243784545,980619098,994509440,347836836,770971397,554083196,526255755,991229479,563791172,778416304,409919529,685543175,791479717,774014618,581733668,231114363,39546775,429556996,37443041,872722605,349577894,621080645,606553814,66520804,355061491,862974902,75416631,78250424,653730165,170563519,205898951,320149524,529725368,345328328,931270405,834712394,89280950,721465406,727652010,3974638,778715928,512200229,193683744,362602088,766930091,458011531,116872526,705910103,356556511,345105472,823007392,637100946,100559692,183388875,53819408,437154486,913119239,48876504,904552354,481305703,786121122,935604216,519334836,36929143,344425405,895008426,484241366,602977613,590152234,100588156,599276218,14037907,322608388,158325398,670390062,898133786,93069737,151687872,242924133,433209907,838190819,611401890,613053094,865070320,809202753,976515620,927971417,26799441,60282322,104620616,674548931,333002046,94356437,673719019,752010054,950579641,487629648,379457300,437880365,569550706,133155766,453112204,246078198,179241859,147550174,78921421,709661306,301515505,117787928,67813055,510147980,350794076,446653814,709750258,617825063,78420951,216613213,510203982,411543902,194973445,61045329,535315837,939478228,220486114,117750217,225084679,521105699,517959892,491765031,276173362,339342314,446387697,391520100,385061878,90904631,458737300,499072682,197946177,291158992,57377618,199374246,412904220,968722802,851464004,569262082,330571243,515604253,709654680,205863119,654865255,973002541,783598242,345527310,267927676,145796116,4241874,518107448,749295977,403141269,50759182,526010228,7297059,935289174,883268039,538709720,919458471,940907413,813487394,980613398,344949705,173110057,861814812,538925361,142754283,198840635,469031146,48393273,399179927,953726213,128500115,484536251,956105552,400453526,312150842,153838447,447675944,20488517,913150403,339427137,960577038,746238927,494641999,633275792,743089231,728287400,208005996,362113394,765599821,66246880,142825047,651568662,205790490,830251307,366544991,506260258,583470516,417767268,405141791,224898926,797848511,143358699,227622433,336908855,26860692,351990281,772871697,584247172,576903763,457066496,520157721,949020367,46204959,132807887,772791281,385052716,44347310,754190225,837021409,940446152,850436643,797654961,757497232,164244837,56278720,332601726,554774537,191457613,187430053,101010169,797640614,72468810,52829187,786190055,996930923,297033729,852937065,276875001,743020592,432051424,329265048,715543232,942885706,296790707,739288258,482475713,789055165,538040237,282508369,963407954,108105983,708996271,214209440,272038670,394953527,597011156,826616898,145385878,39531021,623633886,460850962,248734666,411319195,800231251,6211303,219758517,549580591,559307514,773058463,517003237,792629359,927134472,900626863,256536745,775457537,451354550,338318587,340490640,282473571,627675719,859196509,540942022,19247584,950335335,583389231,697519171,168424063,688987417,28021884,353653970,465839454,803668825,603402618,967315066,372442194,224513912,977535843,349113484,144374618,547911205,687100187,205611810,591977776,355479274,787054731,848213123,517571596,542714651,90905868,112054917,647021712,588976611,771857534,330260825,598968074,167887889,278830139,971249177,497337398,107669281,160528882,876328538,270453674,716998821,377201551,62068059,420971044,682248486,433486821,308374023,404622103,839220259,229531622,532023164,886690937,610282395,935850800,541379368,614431791,346084083,99516938,194298294,931992333,90212094,995148587,690900104,232966965,646917574,702080437,928230085,515455765,984697986,227346281,32411927,744963173,181140254,268056108,56669208,719625701,729536951,225121913,576310761,769200023,768032916,809002728,713365889,337590647,769922659,889978046,414534605,828804701,781580651,350629657,920385290,767495575,108749296,767410598,603399475,299925266,500725173,346403132,788033242,703550746,514555899,487678105,504034946,310391232,423105011,428275786,916301558,168886998,23085204,280740390,234377631,869949503,762389209,796855161,362541383,479344,976304553,338787188,954226457,730904398,204464641,293559041,536046463,972917583,639413513,364457423,929397330,900060463,537203564,653616978,172721655,391661111,641332697,155223428,244911386,888596570,121161239,752517383,696279200,347226310,638811589,665430171,757724739,52170609,279314414,791982483,522085106,198384782,243633969,780456185,952747077,486354413,750812470,147269901,282660361,873422028,933018396,681846799,519763878,293323438,895279108,988068392,541567189,338599161,694677103,685483349,288190837,399733678,97863149,831264736,342351111,622160267,49125795,431008990,448364938,233337716,780002121,68065202,839967095,655017453,788470873,391436856,655682722,757001077,679287906,321478424,580452048,217467001,824551843,995437692,225563811,154782345,504247717,744382202,410586324,821425587,675174258,14235654,980313040,626596373,513756754,404389789,604590280,941786110,43899747,127278425,403605400,735342575,121045005,194140911,838880867,371802138,191090032,100791819,740879900,999312977,106424432,892048859,635812808,805093124,395049524,706017622,551660012,873737009,984137320,490088289,190076563,412865335,612964927,896787951,539813448,884529047,740556618,606425192,193556754,516606017,161611528,465656764,181279639,958551239,74188019,628633286,189106865,366369833,250165299,673022304,584795534,517759990,404572817,593650941,655271833,17897758,518920424,474836302,269455643,712920500,103884173,816327528,222554786,734414996,340753681,785561803,366201896,589959788,596150419,334188907,615710738,80558548,236831015,495909655,397073203,583931069,7610313,840940728,612432056,342477358,140738130,290908106,149495937,872279533,817769829,893432679,46296740,323222030,53386172,813426497,248821891,746192038,525107039,816488382,728804017,157604872,673821039,277619778,467386603,42337804,977347556,99859549,414724239,145113790,413298598,129906560,760665079,374112248,283069422,593770738,440635994,688352560,134533436,290902060,728745854,976615140,821408912,588111730,828607646,566460200,580513196,682771494,847848196,249404865,999773015,449891426,162153161,997561276,806911624,98834850,299491347,913607171,677120740,305760742,25314236,207133670,815066969,699849035,635516095,180938096,47084061,502267344,694491191,262992150,671473657,732262680,255863877,890838413,533392486,635407650,731858934,207315899,637087249,625432338,516218519,254294259,307607208,499554347,856032667,880460092,895245452,301118483,27639038,948410852,818265401,729188947,399233163,49988011,548115264,759710982,743749904,914353727,591552954,466376477,529163341,558163418,362639073,659980861,5195603,820814395,413421582,4930015,486190977,611386901,773746215,454901846,935218609,172436188,181421642,489561016,385170923,315020134,581863924,270706410,380809958,414166548,51459588,123728381,61927031,982214853,834494060,81759890,220374349,196127019,324127515,892786605,157307939,200534738,99827934,843056091,777631578,113505824,113578311,194415949,371148840,925192595,572099347,138233747,885708136,68995496,667492893,846469023,628556716,985619725,313112308,162028568,909300108,860735512,401003488,559287018,621130195,407330456,138667080,512982422,954451883,561229237,312344159,813969890,892877282,565079870,409251483,779208730,289237615,250734779,644966142,726458485,927925738,347999504,77243156,889772002,442104202,317478856,366604813,378953434,220084729,982382958,80183437,404587982,720007672,469637170,219742437,240744342,795399994,29992566,411656005,469670520,534942102,218491275,810656130,180039049,602266677,663548329,552648473,267571575,766914966,834260040,347250480,836284301,545838564,337120357,140999904,620572910,95920747,177603438,362728921,291863224,854407373,606383070,493546658,489960688,9870267,70979007,349231080,698786881,558391025,415698308,381077417,432629363,587721879,779866757,607145091,137458618,506231488,666488487,361380984,805260820,1312866,576733610,318345172,205538031,810278724,9234443,795167357,21231340,842596294,347743216,105567569,26429234,292439757,522683065,541190991,136195520,985229847,248658537,737139710,197888448,587810481,779317825,739826879,865365859,208446171,671149223,898758874,461214502,954236277,936437906,52165043,879306589,956061135,858031638,80520133,776729249,2189683,562104468,43506905,306096386,955023140,684849840,92561948,591574968,96354867,986373445,213405354,850853023,20449664,150991955,133816316,83159163,541169400,280104305,178309190,211980432,204611064,786955302,247464609,974897703,31390257,65769452,532155072,318862176,623809116,862278307,156991154,881152285,809613509,362246724,565642223,591564705,847771751,23074923,188373684,560114600,538210491,419323833,929678536,239609859,330275712,624449448,702455071,442417229,529408285,597340765,843259699,61455502,487843448,179394279,781647491,365801776,552683426,92666119,101479969,184269725,789960352,199591133,391847256,400596600,517807737,764283002,548209648,56314977,732642733,233066709,193660150,384375723,317564468,987897114,219759090,408431849,285319428,683818033,377594775,215848420,220065357,799996871,356515018,989237434,608605964,54642233,993545802,827807267,270639995,812616388,32862059,356502138,626167562,74499128,463709844,197324404,354297915,807232580,535520471,615193257,188246342,734684176,75772247,280095358,155220233,676737533,224948770,923424518,864688965,23792368,80634241,271060964,143568225,651871214,974230240,278818344,643777867,528985649,795906682,567052702,819961120,608910762,904980058,493832897,947028730,129817928,641299967,266244487,929861925,546111708,37561551,311479005,211834926,363652978,236385610,225477931,781006971,279101866,858950454,218971042,418159473,860252791,706185708,333074055,679188485,565901970,651009060,412242952,597855336,980532310,137675199,345431681,643296981,618519346,553193832,104654820,78005927,491551837,443443302,291444950,326912648,290058763,301669598,385942930,157503773,295739631,446695242,113199391,190179122,315668572,801356840,985642884,951155822,6871174,812090697,887626584,182801048,904715065,498778813,43541530,497757583,943525838,54005614,535224722,783569436,194008915,458256434,578893868,357810698,994729579,358063209,649845000,116735923,766646191,926347573,445494527,903713029,388320916,714237773,868257798,977900828,268826305,990473338,45432956,786076529,171487283,650437628,102043184,740827792,269706451,633366925,15315615,985058358,934989513,389293051,690548538,18629155,245484568,78422183,238311672,235024583,139915251,174626292,395303144,939879299,607006087,562220642,994909605,457388571,762254028,557132053,488891546,996898675,313840648,98896502,872268100,500352345,521473616,311825580,229015013,223176572,223364930,42230486,594044912,264736437,821668600,844428741,998628174,937949569,918464493,436204568,977285597,501532468,401140847,539265759,138237687,111074045,978304568,912969920,959470539,747656674,889871477,716081519,803962850,159453946,381757384,885645710,392166737,692758845,861115541,974967450,74922761,390967848,526599196,18047978,642581693,723290941,401608042,385578198,609767818,75972730,403953620,380099822,928203079,604589266,617578048,244189014,417908450,451432679,952533144,424046587,996892156,435498186,623524391,953026554,742245203,855721894,850176295,688552550,777675753,675077453,166818585,856602338,974255297,691044731,946951150,12733270,998100922,452925753,282408041,394304813,128850791,938500199,101322850,822855380,744320249,263387468,205539256,210703187,977520877,119671811,527402841,204270630,938982081,47414493,149221390,381670980,22696234,523556889,315852127,413452704,57132049,817067403,195459923,860024908,651030799,873013187,581650935,383330881,609952341,585069827,376115626,861488945,303202724,384678521,176557845,313313414,499816543,473879949,699652874,919882808,63215315,917958684,748916700,531044433,259869612,617951299,994731065,477092952,791837901,125802875,663029535,581017230,167310022,819365245,715392548,800941373,907465320,128229678,829229529,745662603,841797300,426952980,676467048,678179360,617424282,251695841,144113670,359207353,31694133,546048700,609814811,351334946,334527089,23048865,251826577,152086206,20161211,345026506,199138694,227426880,570744867,97516253,705241275,877974199,29315697,71976776,758337774,10879573,763588511,257950568,103765595,528445336,155727485,195240313,142924117,549989973,511807208,489547975,890634300,115206448,82753217,378486684,591901105,108496414,960647702,350220704,239911675,126059889,773537263,704892305,214723328,287548486,114295145,317676959,541371453,629259304,328702725,512711820,64617858,452083204,255618824,319321981,615784110,912840822,647945921,398384981,269637851,353828062,531061956,106058592,309155670,176929188,765686701,206750379,418418876,825751186,771451066,717961304,107672044,15177978,509730675,849382927,819796271,700105694,352331290,731205703,152426158,22839747,844643719,153547360,938939200,176082102,677064274,687853999,951716450,449251895,388887204,683489512,309195626,566712631,852086885,93071709,737387479,95276941,394405396,64618643,367018483,183591320,251140627,873169705,678621163,575272383,308308045,495077000,206664639,787608412,457205126,859487481,520030948,8018912,783339663,131581383,503502105,229341665,221925950,777473161,565447884,709057112,919903830,161174835,616368526,84832478,442002420,863853469,133684537,66145438,358438008,739945468,720359188,515023152,35339314,152333189,815194027,269825800,266235458,156445625,894125039,976261772,957927375,306844557,826030549,440083665,264317622,262932514,898206297,77266114,935924276,946152104,887281031,853425965,730735728,226592371,522604959,468648294,879777497,800722876,605712186,880466632,379020329,548704219,189460604,131456997,158436793,157134368,867114901,452452084,3637918,476685553,398313196,101247885,774121889,973449986,261538888,767896550,626808663,664896583,269722981,297810217,776157312,218530837,290526821,94127281,924838647,555444733,685284717,498955841,404291509,848590940,504728150,845388267,997906347,542559357,409478608,307904724,662001693,237982350,925887752,665489527,82328325,295741057,501404767,987583629,202295946,897900231,480188597,62055896,372734625,609024162,866304056,921744522,474558533,734359698,378186363,662365105,83414779,552920725,415708858,561266012,930418701,331521214,220045349,473803807,269966230,15615247,80068957,426085361,497088887,592108217,423907451,640211222,897955793,649531597,395479114,159899784,594746012,275288695,487101666,593890103,821669745,974283906,916903299,841271739,210147431,770554935,804344241,380217233,704966317,441096026,870202974,458499073,663186485,763324616,599108951,72103595,924317758,779821686,379118635,403886802,119560059,667509974,486573061,441669970,734587640,233377924,193299820,679978293,385662589,556305372,262456160,844610403,6596577,865205240,502427893,513835999,355779275,749209169,230755253,475810976,19783302,988581790,86418748,542929341,820318421,843476195,40289710,219345545,482018000,386148587,770851052,822146557,611039976,634145748,684453317,477676346,930537168,573795581,12127220,838078644,531122979,929038568,748696256,529134165,10138988,810556870,127077921,721539393,711441583,400229154,237179080,51401885,471145678,858662556,97464575,400239974,815006891,369230665,25820480,619688135,764543988,97226597,153889255,62116765,896001806,718834032,361905117,922257137,581039700,868939952,379483292,349655742,965328912,429683932,403412201,380266878,865613490,53704133,248937301,33692901,482661501,595024323,337338835,668381053,636357900,276413918,976689055,167727155,653873230,635621546,939504044,714263886,635369950,693272863,633317424,564459560,532066454,251395722,419869285,8865196,311214828,310050228,861656073,960904757,339426853,13998122,856570978,332258980,311098176,838524127,163322160,222941024,454291839,484911541,219416385,391962837,775337504,351011476,426536901,284634674,724509134,658684449,548661467,370842842,168072789,561090877,499017659,183125863,81070522,475110420,539937637,213869529,868276040,15015259,937078319,856100273,69035992,132975827,134041837,240586490,198736189,837817748,859338901,861358965,927632908,901942303,34101546,796503950,218590238,952053782,596462477,896165825,337343128,545692419,954361028,652826844,911271996,132367065,373855850,383308273,779749686,908080075,367779524,353170200,481343510,753791773,734748230,780087412,768568203,39595863,164126441,502474044,515603277,376734004,574645504,509521180,553759688,538247454,227467448,873983680,258759215,743813400,640292486,462367390,199997213,936114465,744212987,183993402,474508470,829502729,566336509,744779700,396297405,16318431,535150508,155116902,393726829,634055492,50912245,548764730,992528529,602947491,427135327,15437525,602026768,381610554,825380728,759779354,400546776,704356031,912931710,152097584,116048485,435819008,923639638,559622892,776453616,490043335,823443322,341864563,396559397,947123394,824836509,65720421,66617065,836401682,159351377,952923732,316655058,44348914,100621216,418491893,420398744,855057909,948206779,487452702,91666737,409355063,368701746,851659260,311132351,296352411,185065665,741916788,156500666,251712830,892847908,669765032,804964508,119654361,255519818,913796429,817658678,442302270,383794705,156540112,702350060,991849305,137093162,540760171,196900074,122372204,575809887,964943821,580019400,53451285,992357070,76076329,235247518,579689446,336543461,183154593,987138751,248300498,995790547,445557535,44258552,98512261,672847035,391218860,898513133,444321622,470592058,9890591,955352037,259813036,305271899,342305038,195385449,560827715,452766116,628441360,251013388,171126923,438887690,649288416,50404519,64029641,38708169,39285203,442074595,998685170,318258747,492634925,62561749,594410184,737990419,91841283,866557474,190313407,423127948,111952045,923555408,474475931,421583482,441305754,15593526,135788588,601853855,186993832,552647019,859280688,263736166,65595664,387712609,922585524,74031483,806820809,641835259,276175145,258663611,15215046,432938383,59928945,438810742,625778705,188582707,931073634,906059743,478092403,169571,439670773,444566320,698467343,191985777,904755694,159878664,886393550,766899617,251147971,30516077,251449811,805667511,902979291,112472854,381149402,722173543,531939955,389081949,436143304,136733177,515532554,716938379,518445515,296189620,426105363,381170625,968172700,426801861,228813815,546572463,308874641,125816084,797298867,689398127,437625239,898273207,521991251,281349036,855734619,196332991,184660354,395049295,554925901,381210728,393385084,564424107,737487347,902175626,643156434,265104752,61572244,718351677,426211671,610975866,430967549,644376256,291903317,461385894,553468562,948337437,327793539,640157684,430562767,34667831,203256328,568745064,672492786,755351288,577555735,488780013,57609514,861755784,811521438,989053858,615583133,618688290,713645110,697706090,176638117,2750777,564475711,294294222,832516912,116425001,429424147,359302133,144631137,515073835,708361480,924455208,433879053,745574082,678979402,536656488,342212686,157639748,746223652,784091270,669544898,375206721,943130970,163942508,320173655,238142589,621255204,933395395,289453491,799773302,288107606,215981049,858672490,232989325,522362171,461759560,938954195,772666477,121943757,848892468,254356841,274198302,807022406,290527874,30721072,130198794,326127826,991372051,3045809,289762611,466146187,579975428,305847888,931632890,894969616,820452704,392646715,756760698,107247030,851182464,548438348,196499098,403102038,977436554,142020697,20637846,278540363,800589515,946648387,675776617,140611737,820684143,220917624,685392889,540610048,150109636,249844887,852828383,725721838,244099129,546615415,861305137,486847864,103666027,735169679,419374580,577847153,746218690,721748753,760785276,535502274,290957779,704896618,431439239,728735097,342719458,635740827,50754695,522627984,103691398,894472707,606375506,160783046,885003706,941862707,721397586,291770270,662289963,875593162,401140434,818428330,909301788,966813854,612381573,450418843,846221015,725570634,31014212,473740511,856797488,285398432,437597699,513564017,418855700,627238956,721918317,916095620,381248494,590534880,241001832,900687025,551743742,345930576,102668017,768076661,424395009,220870344,467265388,81073221,871178544,378794754,105611021,115974542,470998294,360022612,200953349,405636420,528336854,909270486,541128615,309490069,609396095,271501468,407688054,404428202,773984267,74297602,909724644,965658182,533200202,680819620,44857018,783592828,629464729,365927838,618725998,680690898,188272437,321554599,106528666,259947420,558332311,199798839,44230067,462266791,828979786,973682710,164076388,851501519,432533309,74984325,373195133,44168778,766451793,380169056,353971573,732234516,637552916,592399389,362390488,571754582,22871222,374637426,612938221,109696343,918733205,244415272,270976132,885288632,792515314,897609564,751984118,615250276,690022714,708221029,278525278,274144312,132140826,272733297,586950643,478113605,986315390,414270272,824959677,7079932,861073735,51433295,838722245,143448591,847423980,532056636,680059882,341974922,666668485,845862314,339094631,21384131,353297812,437472260,299652286,299667339,749840427,856103631,259912992,794594701,588327845,594069274,939937437,126448693,635089789,905707663,730805206,867388366,495192439,1638143,693668500,96819138,218870049,298376940,289114062,615467958,119862728,201973629,647354796,164879178,614633683,114332762,162355665,132699483,209144525,428514479,646119516,529594813,227045284,200312882,690482163,727680611,833261445,353781192,456501939,954183784,150742815,359672262,568132093,128898453,379738304,176270425,805362775,482813939,193119400,81312840,684220711,831654342,574737088,681768387,360631524,13405996,357393611,577887922,229013612,770484075,283467190,195234150,498341897,384125024,73187192,305411396,224060908,811286371,150103459,953291298,797610403,471246231,842083823,835327515,732432474,420208670,253404800,72665135,941103100,997776460,106471950,995707078,189080564,274691546,748617420,733719635,197127478,738698317,916884164,706214764,282823993,156607332,294783482,748366169,864379444,247918437,620330241,290125969,502383131,956391852,434966026,888619733,632419710,265923681,81611666,480291493,661136548,486281153,347332390,923216326,838251544,691509959,42870581,20946845,5299876,573582411,83183210,996427180,952209143,240960159,733941077,527362414,181255989,108743416,932582612,653974379,702118760,55833444,241228614,403650694,602101806,636009572,440437939,613791450,292483863,70753311,797285618,209760771,171996450,301424497,684829461,844850621,530641006,22581184,800764218,991423957,570162209,361513171,997933456,818923874,126196425,332015113,583082325,19041988,548776389,174440463,403302590,494606498,609603691,302918557,737565987,667673132,904796598,123088367,59159038,377183879,328527422,364105903,447327634,59610864,191811185,814435769,721812827,527878456,732494111,743671084,825055036,742948905,883975564,363088216,172362671,974696253,547683362,555139599,791919252,497716115,345875050,262089121,466379996,472312431,383918957,668808133,146454459,949276115,907650307,359071132,891569625,50177595,612999364,312446792,874969596,806616304,857606116,936293214,473140274,436305606,663133435,214575604,274139046,23644006,697394904,601734903,547685208,912389114,370648960,864358616,527017756,443382914,583702450,213400225,882952089,294712853,846615165,476122675,851641688,874836191,362862532,313219248,330246977,676272713,756110634,95287300,524581810,184989826,117782326,749462438,534495547,776010985,7370389,641770966,555935299,625848740,595820121,673037819,575176731,878405260,584952290,560724304,710876294,58292672,865037467,375219628,971300441,294903767,875605942,729222255,940492468,171914137,917452038,884446041,173298356,966965486,842401299,797627791,210543083,442032921,489669653,227889148,854662371,594227286,374360002,974293840,185277191,53016034,791183587,164191290,110516744,229506182,369828843,453490529,493409171,361779953,997722432,85009635,127559426,351860638,698657906,39464141,858912724,254452750,854903040,715880908,740722566,130916134,580524077,371463440,995294772,930632436,8033550,745846283,859733648,482623988,372328080,416134325,236109477,576794509,26834664,788015527,322644260,342127531,574289802,71061470,157547180,687149561,366041227,159967843,997144839,629138012,482151119,706953803,780639075,182900015,752933972,297901986,318648910,897487044,713867345,887350978,660953787,431516305,520151363,694681347,478677516,450547073,919174565,126227383,849290385,871293373,679737688,285137253,278882321,463114842,65294625,291062427,676027046,882995124,425654052,908910375,156482138,491055635,535846413,967884887,431300833,808904885,183796467,974416992,86120489,597965031,152535980,951493864,141672755,489680546,458656976,504064243,418243396,308967219,369617804,185047515,568379926,780354496,922258239,900993392,515252340,91293075,766484218,352496923,185162480,369067019,309497588,359337161,262428447,880834583,345198076,56715962,293073035,259204396,40743016,914987494,457046021,535924641,824526118,200612967,734534964,64531778,650145412,996756122,271629263,903923540,940760087,12609440,890951790,465381484,455521327,106733689,166510765,175291335,522389343,792724151,326503746,757302105,882910078,32561971,145228087,391081964,630030944,775536208,91457469,63377450,944658141,280234617,824367662,107247254,807869422,866571100,633213125,312860580,195407224,948592638,45709282,566134603,36488371,106693358,436936677,660057750,557816252,773424494,274089251,717816877,11910819,975807723,470084019,37319084,66264899,764704369,211203205,364135234,804201475,831526781,692588802,246684534,216483582,968305571,582830540,744132498,198186866,141797859,278421813,522615496,351404030,285709789,954354684,232360295,862345746,623441357,739371448,403879705,524856405,49041503,25946799,148138047,534283945,690037946,577646667,223890417,794451014,382686393,685410034,44859194,388075134,206761575,68998845,914728772,904459955,493851573,399546591,350408552,790576423,966543402,326764871,531188075,844987937,116563436,799332730,873330629,485707431,175729189,965793872,164008007,988582065,98556015,85518443,249681280,571495408,220095070,367174765,957990899,134755592,708848480,219412337,255877361,272043071,786424226,561046017,439955735,80244629,597800959,135190616,64845346,136718097,303788681,288423005,435161646,174030101,415172329,631041313,710206078,489645780,495215579,803126740,156262966,625709449,31148574,423033842,742329944,48577416,567043086,777512410,185848073,855041896,17867645,700956159,990995163,19674253,822493124,3141232,325693544,400541017,728379128,855246822,750132238,171890200,32131962,291010994,572004373,821273987,2417690,453008483,741047639,991637314,159261523,874584852,54154200,277105535,262609358,98974215,300601686,607731833,391941919,163532402,301871109,565495219,137575401,331743609,442839759,477115308,398378150,284176655,967131286,932908057,256394674,377183027,701798911,445160788,177699156,267000059,43513490,214675776,750466654,91335983,82674835,513521661,400855168,909493783,396403251,583784192,581120479,194220188,890963476,576968757,467822796,162521529,604623924,292409250,184866908,917537870,595865126,520730950,236086703,294872691,266971826,346807885,593202637,342180084,241730571,402356856,862709476,820727306,38190868,689688008,40296309,805160927,622432139,132308418,713691210,213354367,4068148,307226700,182102371,553749870,197463825,312974638,334994917,502801065,543247,964714206,658385215,428907343,723171837,576817361,530551580,914980181,845214813,789356644,951899313,74261355,229102214,273353410,380829081,526482101,847376955,267290705,839353385,194588854,397991003,984603023,611592743,113943272,170540287,591217846,634011640,899371235,463654304,853971456,614080807,495008802,89115285,497475319,108184307,649521741,205443584,805832064,159902333,191213863,810782752,390008336,1038738,603082178,702272011,706462959,494018532,813653788,661729991,770683809,777806918,633295711,297278970,290103911,489442098,454717162,109397135,700434331,3252101,237928138,903760883,31509743,594901740,165888123,419868161,623020227,110466872,783988693,561038996,43659707,544725445,347716783,544708986,831604939,126583161,761114871,937775157,357172133,957945047,673937511,120955566,140007737,539142461,314216474,678775583,396051377,873154687,527289137,759446929,739306173,835396981,429609049,772245615,477697076,324039463,350568864,848502274,800562498,883391175,400534375,86624366,328562325,961946116,526044725,345840071,571874802,51133837,594837538,62771953,619955199,15385798,851341358,267925941,90976224,964970426,799391372,603293037,354703747,125891034,532082685,530969856,275882012,855563979,31519616,651500902,275953129,420397913,804565463,194079743,274392673,692383277,643248246,106541642,74886800,96016718,876157639,384596178,459205313,451709036,760853667,691022558,359984410,788440797,348336900,496203486,567847325,795555917,74531190,540704650,197222191,845379974,688085635,200495019,641259599,724194750,631972378,190528692,340260330,419569211,46864955,929589596,597996545,441224057,186666642,539120181,341916485,412197707,46050789,93829281,889136556,991779008,145867184,391178702,552290097,747715262,41173453,785163861,66653701,543181887,212938670,652837318,883846921,129810904,735469492,928587614,720741674,948952430,200012943,96291780,814913703,475813991,868729644,292085651,792042470,189004204,126520791,278716730,373845251,449015101,641870549,469890517,904491450,131743567,33586053,560675444,284011639,555828944,107371939,982089922,248630990,833411368,397363677,977338698,670576989,327170552,917048970,213645233,13921524,584286323,994611728,439275972,56850795,718632736,215803681,465659122,773500756,731808926,177234896,849030854,832914115,772554773,195602780,591898388,346847389,89133095,713397814,576580893,922393771,316179896,929072468,43890002,514326650,236556421,502622238,71951393,549189008,123450958,581604533,643319947,551365013,763003896,886596351,971426953,73060999,603532978,199490892,652173151,948641214,307353660,661043949,624975883,658893175,695174256,862653111,198467869,241424317,191038655,763749916,773079303,304236922,751034518,675239850,884624847,505707381,709895066,89721941,660033627,780765037,332033301,727910812,831304639,426984165,121278376,366801585,634990428,474554880,632828957,250795747,628645621,338237639,800501351,716320035,509108001,672463626,829258116,24051889,71980207,703514787,601102245,596585685,882535290,304202213,679161311,262759490,38182081,586939115,610219395,970136626,456046619,140397723,438361434,827863443,983781226,929248002,684921330,831018085,783602305,703302592,273047196,83602221,505086148,666449333,194123248,475532819,286959606,415139600,228433772,28254947,568514044,159480646,184645929,108251012,105414349,337315005,736639646,677086023,888957144,585556648,841117323,235058473,44327844,272653483,838559273,799665947,831394455,750877537,427508432,81281097,249362417,49092348,150893429,723706946,240257624,287499761,702943792,59719340,314288800,412496677,167600276,569666742,785442919,347352103,216427408,339419203,263241814,788289382,327180619,923868549,742459983,508034832,591227326,407693066,823089783,376763064,967910198,591388059,982108516,530914284,996053098,677903078,189673556,395739583,675065674,68794736,290363292,876467986,841175965,681959805,253808808,568536099,972635793,504040422,151314894,427462538,964198581,663765923,369306487,163223802,80093960,914663773,673619909,904683839,59779351,222380626,726862520,267655835,496118571,938071043,766966558,952449971,368138947,491726575,140774356,325941571,438277435,513748157,296947625,772926775,327090586,450759998,427208069,113096428,761586757,279509148,535364997,166041376,872343766,70619058,333483642,305254099,586827917,954787431,875472689,220716813,983291526,169896938,433844837,527657698,88087624,433987247,167110095,555631159,113399980,429185557,964825237,666699432,935294056,434269323,180942987,164027292,833702888,911202696,317008971,639090751,16973098,510182623,797363670,430582146,990547424,949816619,691813074,820083544,276795263,178313309,411484467,887528394,36769456,637976396,65964121,183556969,651691679,884706539,734443031,29750318,969871550,976547432,911446875,69989055,248399380,628762381,674613386,303375736,8025598,272630226,928229598,79085180,477534018,334143789,867108277,349371021,303776415,830429111,754426282,285633722,256526208,566740080,93668004,467509966,345707456,779353232,756127401,674382670,811967958,700233970,913233920,352665272,942649138,633206254,289062658,628029386,863831882,619594653,615987220,509661672,974592666,133468733,416873296,180915425,248006518,460775591,788341137,512252495,780395660,786399623,710086003,414085541,674382529,39755286,784159202,733711885,106928722,465253705,932733007,265549045,721739311,972209060,408199500,835377409,55743845,53686344,339594075,13885227,896092679,435104066,958019859,233345799,981117173,595732612,409741465,690733012,305461191,498330492,150721121,155851562,237264935,253440769,14495338,7572164,509320325,199794368,823137822,214492417,499360443,400641317,246631500,688860097,317107441,622435124,643767465,100185568,300857278,926282933,379180547,481079497,332697524,907807472,827293565,749683755,253424143,935441795,292722795,596791641,306365938,494348207,303292267,113455452,46600172,640908531,39044254,125325343,143565162,771556083,684771964,96602922,184047350,915829178,94985475,999742921,526782340,530081614,481964964,291897839,252680088,853032834,564325014,209571946,917147861,791358101,859755887,681905782,311689026,606939166,686018065,301350156,117204452,8712334,323645908,94210398,290973603,562738266,407399661,984480492,953314835,646410256,974547384,563048397,908438319,266818878,688409820,698092133,898027224,843810232,6543545,825455543,381473784,139276028,171440849,833307066,715339172,5520732,282500238,927902521,752473368,747209811,879439718,221433127,442772928,719939612,122136599,673933385,142809099,97697727,363076586,824776447,826370359,621329398,688176653,627330879,572519143,603536876,267387345,550994068,300701589,930054806,240093522,196244505,843489827,279069711,523798618,601423864,541616763,210930310,578048980,575707953,707819514,99531417,581294762,176160345,892649542,391228786,591707717,645001042,157259948,434211527,993216391,533997745,560358625,433084216,806049009,680107437,274695989,703938115,447494326,692576623,267303696,79060522,958715961,579168433,518003369,203163887,434654996,382026353,899863454,199614165,490700083,19052654,616244227,450053341,589151398,563513572,389594845,722744658,768534167,466749263,731599534,726903747,561556661,701575805,22803502,62829497,590056381,545016950,353604410,295005870,143617856,355228327,275462640,833648646,227851791,649734192,158141890,112578839,842587301,993912743,442660041,451331407,902191680,100670220,977196860,644495155,376150119,761047766,641436776,542007976,62233161,578974995,8931766,965755041,891062892,166346859,275336760,233614549,284879460,662634433,56009219,747066452,276384123,824651573,975577136,446332707,669193393,213241004,885088843,428379469,422478201,72840411,970840744,534875421,178657044,57934953,768267940,682662363,923624507,473617709,369462967,573600316,371623256,861216489,395459869,605295990,37208627,705140861,123723532,924454496,919287470,210498374,35919351,427766131,917377681,417364302,963153908,156895410,529592963,946502904,439881270,618298795,599044909,909017822,343397212,878331276,125813703,355352558,812127527,18284779,772931771,70463983,823139024,86857707,894312717,166059394,860731728,827470711,458438585,631000964,908066969,949661555,749926448,968194271,85032045,372643201,761421846,909904327,867010732,620346268,311471590,586988890,110915330,843854607,980979683,799679696,194173420,261099789,55183379,90184473,501821227,800895759,640370249,182997672,646827751,484718069,545493982,445686595,481779268,3925874,38538917,328062283,724965747,424708803,328782714,762477662,264354036,181133728,941582672,644867245,689494695,904974319,434834019,298763824,158323083,379955024,333536523,989553574,601084836,701165039,53482490,169900349,393671709,559082441,748677397,860741139,927058564,761118747,77014639,627821890,792121515,818730553,769125226,552114626,19685390,284368401,308783663,185535438,496948759,252672101,842065349,585732308,662240330,372617490,727262694,733153325,777561627,153149243,511448411,400034436,904742276,435429413,542922318,676326021,371702597,602662697,213315006,286616918,404672024,591675128,874433280,48546687,162715149,375044556,684717946,860623803,162672314,745776242,752004241,990245660,306613642,236193799,646694528,132491437,63144489,540975747,973212871,629704658,950101784,534898538,785266155,951271882,29833254,602059176,95834190,521245493,489292141,223664664,149620290,630232011,342131380,450287277,388851437,406235715,628126930,233109441,726988330,808089177,692766896,478817472,972248598,955119676,292112557,401060302,592057942,656373051,286048233,72986574,536814492,541135259,268678088,585003401,935430196,293882467,114338993,748632681,861833945,167176962,483653414,14216057,390874980,994040677,865656442,245592538,44253233,759353438,657100463,227906585,526228276,244569167,661662916,855249791,389926990,49873625,318290618,280269227,740776572,522272165,42156487,793293254,294524314,578904336,627268755,712723443,512409076,820094936,104975569,371738704,811654013,977990475,247231827,963490453,798136127,873279947,18421115,928639933,766196588,985241087,846376278,202372971,44369001,700093294,28555492,116061996,364172998,609747409,214566415,846886858,733661430,323939820,79155832,994660567,704075832,294221191,811320480,471057026,104331447,995840452,876146638,253460188,245437854,444384187,490436695,954608213,375871136,493945497,93455918,282543853,265348408,589134708,531080691,796625670,216955652,52863818,805205538,37297043,648717709,340930303,816127596,293363904,623658195,370940198,605772515,638551464,303202997,853752708,412399277,418947088,304804365,12097173,137818492,895296024,794659656,620930003,414672619,386984065,579819311,84072675,194656913,458979418,50824035,377021333,598844630,855117851,984946338,991461045,649681463,516215989,95835016,755436620,364935281,453041571,257192760,923861254,689066595,825805236,412721407,221445055,391820530,94193816,50442175,1093044,297200189,219145959,549579986,528971455,126880342,92909520,154502171,403017499,179576599,361941790,375635590,255506749,764523099,546934697,569477726,127622503,461790549,702210674,963297586,895196532,824090802,533824634,708676846,838907742,222907100,499775947,480897033,393487750,163641812,224157839,240767149,119638998,504339596,149505105,934036854,916119700,80809797,425447482,513386932,172177041,590053312,453044789,208949409,854089234,531791069,375110720,19835098,774347952,518954890,892772071,182426415,220026261,739017257,587993788,572045611,240798608,261300561,212947936,533361731,25163131,499800957,513484474,461501739,755930185,279588337,149444530,66090955,506896092,459032230,474935932,575776439,226920759,543236430,167024293,760276143,653820344,850057384,231825704,502079787,292689793,742896773,555886493,33134780,742274229,573445777,473350289,403542093,702383714,610981892,498156510,957449649,478064486,631921556,855885072,238769736,564219166,907130478,704617306,353423295,588909403,987531723,814654932,610684737,358355993,643306626,257170138,80078229,165598113,859425315,315624534,357436635,638804725,700922675,550574114,799763770,452718877,224393121,999713748,721209810,623747135,325795762,873040589,154778644,81652230,897039435,578538797,504529288,933120145,311937734,818538935,221945414,137496347,414433367,582761563,71443049,233635544,12324970,99132019,424969440,946512117,614555115,994745516,170481282,163089702,971285228,199456182,241867070,180706675,191257129,735259069,89996356,783397855,80756696,975860881,679558369,796457847,975331176,608298096,95421850,803777216,951484232,803794113,217097256,66197885,354414373,401876948,600052837,883806639,25187237,755156276,61616874,713099193,935946689,799443251,159388347,508898473,633642157,754821298,458317711,372362491,779024924,796906203,505303641,137024212,888432759,327823597,636253155,277006766,422989389,233496888,777626880,199673371,965917437,556180863,342201623,142386370,189228838,332331979,672963743,19738917,58964599,23396746,193836531,321802025,73826481,578975879,868861125,455887783,380189761,364746646,593523687,936955808,30810993,591180871,241622854,657193324,737686940,892543937,576854232,158869127,453393033,895257165,45972141,248385658,521635733,433579056,883833101,680713379,737515396,60272408,496267767,901043375,4707333,271387863,581493878,747340403,928169889,141259376,820298379,839778611,662099217,97890325,53578288,796277614,9611809,295315604,682050856,214240872,214884326,822819638,636993253,521337632,857083323,828422623,495966995,600712676,667206321,577796689,672540521,260160117,339847059,44751890,371097233,855375750,292223468,544252508,4524272,962384746,75258579,138281456,170801822,389131151,339694621,199754721,78772765,772219133,956848484,23561824,614829431,145661390,850609879,909418155,553300341,287126710,100646504,638325691,811328432,922205458,306624411,532668731,778585728,166163073,739972631,500664017,215395351,665024231,628221676,196530494,954839421,970398117,289630361,636780452,664780313,1943236,140012329,62711333,858567841,876894427,760630064,372440210,95490712,106439741,490014918,730291169,840768542,143711983,12967013,75393162,314358077,822305160,330039400,331636652,371243255,171664375,343515473,992430853,258596416,162127396,96640973,210074431,583677216,554736187,692361519,98990793,386583557,668906783,425236722,25383927,687783367,727203746,635883740,545216179,280545771,306574151,960558752,776235234,448426380,225788994,214200018,906228010,576117991,1950514,360657707,608734424,719810018,711993868,989969191,217272735,548871637,596303991,829554135,447112788,701713334,29740234,947387413,466649471,354384391,964898645,870973095,951050062,787716010,237973766,375431643,63957017,550499755,189985291,26641694,661730874,912530424,591302558,351974665,467845505,986473305,350374124,193689884,9587412,339038774,879903555,415363465,226932863,567342077,425484832,387083212,314934545,181679443,809694441,515040015,385920222,877976098,280308358,600337685,338914235,517183407,329890216,549589911,824437032,764768410,290998334,424183009,806415959,791797006,717410599,267113552,341858016,126836497,839930929,319257452,390678967,998023846,908709286,702792555,905443393,421020966,200301060,355307517,430609742,306093955,106866516,941877407,549728084,797379482,761559623,368856885,32728639,915699172,821898944,572482716,364611612,600957699,847639449,812854691,887860116,689628733,655719690,635948704,493424382,475433489,244385247,310233371,242936937,10619229,157108552,287449561,260699243,939421814,424936071,921011515,653180109,455772976,616285898,130835375,514343170,802004713,742154039,687597463,454989108,51192720,913361945,906152879,184474443,331249647,816313276,515454644,311672001,936784111,779036479,877284918,881240019,701185720,505900730,288804281,301012673,882807834,831286390,94556494,409917571,818787551,754285083,388005189,129141720,644969076,106509106,327918408,602701907,149569002,819671494,640922775,781443601,619100477,250166700,983171883,68902309,447574130,927376958,88478970,896863916,952894107,569490534,247908464,442557680,620061158,201532040,613403275,794695075,651379166,375408464,122271863,91304886,662383555,553588206,822523085,736623465,365761272,891921965,48448423,890987959,40760936,403839375,585878494,97870137,47843759,689436867,522103168,502594206,885452153,405703421,360569010,579066422,340367129,445406058,246760071,632040380,2753367,507635296,50053420,401574859,244103966,431070674,467953226,158316164,699064214,21958949,874922621,978025829,534398889,549921234,310686658,972735498,889696529,422582799,926097403,336289657,519489745,190892439,963218767,30252721,230469133,556983264,527537685,900718770,373481701,225661364,35554879,492669356,686184261,513794950,233731798,98264376,659418807,10511971,456681356,392427512,25169324,605537017,813163237,621055399,634652599,880078591,462179924,730211416,613124738,235935875,49849211,313481103,368116862,533534012,522291469,738192922,195601842,968542634,646723796,186857838,594641995,58622741,498005994,187639540,15489769,430002090,867734399,920291062,785169092,227968445,175369438,203346675,321999464,916531658,935851631,355628998,456464040,762177154,324505021,796366217,397906145,977550564,724490489,115510420,381760943,883649989,199280642,558227891,500017041,67572121,894242293,299011199,161007493,517248498,13920726,736334330,555023386,510088931,43548652,976080478,736688578,79885910,749130211,244239873,211554762,151909202,816810916,899787880,660337314,890944030,104942290,330729484,311727313,100925124,80437138,771736812,828544746,777386645,477149632,716856038,546236402,539514127,970972068,174545926,162732098,121179575,404552614,581694519,333835117,308573470,998422628,732064441,896297796,913741436,766500256,670934375,775693059,119446620,132655835,659637419,774361139,673138202,110976544,472099454,160317901,254345740,949851735,79961572,448477964,862333942,89933663,676989596,23381471,407258095,325881464,174299366,854344669,29198293,828547954,469816399,987027626,741886467,960417305,968724901,257059108,998632828,595289382,809940348,28597832,127035991,367831964,733804069,582745847,931011495,285174806,895613258,226701016,978394615,649346617,371447647,307022671,552193432,687353839,973015009,959756765,752660673,684127029,196186107,739116048,617550470,115225751,312360227,463030220,169467188,93037411,570030904,120057409,686277372,560422596,939736792,519409760,709493487,910919584,729005766,712361124,850965220,776666062,221488560,893767915,775214376,765758519,904139201,178752558,802057062,280217320,261252322,912789454,137655046,496162260,754124670,816380520,390598532,752859210,109871775,810874173,44136256,613161489,534117997,613479988,634772450,157915429,497386420,89914268,146883985,885825203,995518190,756452863,476663212,979340485,777115493,21641404,167097040,129932487,668504114,340454897,165754601,602887168,310892311,426144407,210087392,345619785,790982867,258757652,451109974,783458988,432385634,789966924,84846281,562691685,493733826,945279676,270815291,909271880,222830114,53119389,42588101,427623521,94785836,198318486,339335834,771642721,119136191,624207006,569014350,93895908,342045824,22792088,867443752,431499853,802236627,26653156,242034499,953719673,958118764,456183881,164565008,392418197,95610210,743186576,713160336,732323500,3301746,597512416,517358394,581802689,663713885,765167211,543037635,374153383,956248140,589052704,496358225,453321768,856037102,786217964,5771852,697589895,637325163,917756751,265057882,986702458,839878826,35426744,824884977,243517393,786434002,389381850,797316877,989365609,4114327,839277877,300729343,135198737,926895319,946743322,801980098,981712107,765659924,403500597,892988472,137243053,843223519,596255997,601018919,391511828,717281570,869970359,825614203,547163921,912915892,827347153,412483088,565870667,26004342,431136104,868168428,665937816,672549613,450611158,555655736,323607974,123154004,560004231,337670320,197844320,286046279,2711,806134948,196101315,923536167,360380198,486747388,570022954,836947849,977987294,742898365,494321115,670919073,592919272,901056741,196457992,709759444,249588063,381101011,848705923,3087675,675861887,154343276,355968785,460808426,563708117,213535652,353366753,176843790,33802085,688590355,697902848,607788098,236474749,942051966,421036499,276666920,884784967,48963636,891366478,632534256,548298293,946046038,998010395,924545794,732963199,477771970,793348800,132328240,648811576,901839996,466293699,487642292,390391783,259223603,217931365,824111535,194731635,108466355,10646912,599200604,93269276,773811918,549849192,479994376,105770579,708353686,851369565,562749697,321866316,227019080,484184087,271302667,21214704,235977924,205512804,14203635,557199737,703014797,45419823,723499253,142158788,299734051,128565102,596975270,976467984,846989217,256114404,213332523,99259989,412717755,608432248,866530999,355274047,477262660,322033115,508116714,531882820,92238791,606458379,988157398,593057793,173407591,383542984,461106943,197744149,435650867,970801990,820319812,906380196,124162109,511311771,155712564,341226307,527640489,769898359,324870338,280446128,120166670,506476636,156787053,952079488,432937152,220941934,327953365,123324672,262022065,10196292,724414994,57025381,378741599,198229255,676292743,653515246,239426385,962079266,530269991,943395977,476293547,946257978,936958152,686591069,855513228,959099107,754530659,913157715,624475022,803929011,25455474,325517118,409621591,557540439,501736466,232812662,89773307,793959803,179071210,772204943,526067946,441266802,185753815,577693385,302520061,639490312,813979484,673620510,444974587,317762803,491839671,294663812,931485549,561688220,330530169,100384970,839968614,76830474,61971708,579225120,966573724,637948551,247698225,385356894,95213576,621714477,858899819,260253478,869028792,355071867,799599970,212862447,725248599,309712118,879355533,316919854,446580003,599626755,285786591,485972645,692792381,335337848,33496695,484656148,414983233,298791919,489106026,545986152,795525766,23968259,128156675,289908286,498157771,381222200,328214150,804026616,978701146,140476653,651375129,864553385,466697668,417212068,222320507,360931105,481220296,847925101,789598945,332479895,602321817,178858705,405322553,407259588,899997405,703577148,201215934,565197929,607669200,660590355,527763366,860992522,102743532,900676475,714968540,736253004,376248816,285051921,659639029,237074554,371081938,802890573,564445741,138893763,111790646,135676519,936444616,712085247,669330201,834662397,72181290,98734836,817718356,74255779,697098337,365818969,126153379,351828791,979771717,542174463,838064479,734162144,131321464,736534412,533744422,676289725,148200726,706013997,610624073,621415669,779725397,183960292,456164724,856551435,517010869,188646655,556664474,936477528,143464030,828704185,179794084,708262071,577608889,764655109,771206850,333926283,512658066,675800356,755378150,369015440,377169064,27777697,340682290,66782408,560202895,713492938,474487906,535255484,859688503,682663433,570129417,976602612,86032208,979946661,475830725,38636021,640510273,993674890,969448038,917460866,583527155,619163166,901855117,155652298,335493368,888373051,33420325,539456601,476439112,697362413,927392141,401876085,343681475,229710009,118207639,267508110,797450215,488353822,216536730,48981403,453753775,244828094,865378211,584638044,895591525,492922064,695117856,753748022,196224109,862554744,137526773,51571869,282940002,113273926,996907638,762501501,162441821,998736398,133830122,242350221,80333696,477925444,486299621,994698561,659078323,423506479,908863181,725071783,202615438,707733728,416121411,63518298,711865183,621543538,392212205,901163138,149200016,693833581,456381921,468238752,182317566,183804720,28827323,106526690,320653555,887289080,738110003,541442953,206172677,747162782,604097324,246374811,481533932,240668944,95688057,483979330,379842433,893879607,449813644,827766428,329788238,136952871,875026927,501117294,192748126,916877847,538115955,877686315,968830621,653382154,85803162,221432855,196640438,842278282,454547463,554848545,688753811,312174212,581281735,480786465,423849241,999929017,521327605,959483627,28459288,903941128,998130567,565807016,724441585,100426353,866396420,162564610,561081020,319094367,904602918,397572164,530136478,197742525,929054416,126364944,33209685,244073683,754097554,344493557,148944700,675625971,882803618,484364716,275699866,658075123,948369807,977443160,660560185,893504807,9418430,450526192,976362029,317242164,275649558,38401747,379646033,332222944,668085744,237990699,502200985,263226885,977758865,557666818,782343204,848420651,403689264,317386121,682032411,474334234,424038932,883135963,873670404,213662791,611766903,849724589,757139501,643911666,64707407,964588934,38978727,622897669,134452734,598120398,182139084,524150753,298920142,954516573,944341313,27252117,885089464,199604231,941783172,810828585,712109897,909692413,221089593,249736635,74519997,519041423,55104561,657885928,704068802,577922544,462406509,443891988,96092744,624215904,608355626,343713314,256425252,906486858,727296378,959079901,662245920,295753299,456761787,142948634,875016425,568251199,383714834,978374513,191304833,872480756,230057735,597331028,568034232,841129059,392519731,912269567,946710712,467832585,908202302,247244263,189943741,638147278,775781116,747732870,639184613,403329502,895405147,71790430,527463462,797654453,910066988,934150950,28687237,67062028,781377848,295680321,32048914,862824560,392434975,432201820,624610904,89208188,447160726,894001198,696278177,570570885,717138169,464638813,477213300,389457010,699886201,31587228,988641886,857845885,968619250,196836797,482025946,767197991,628780547,473162535,221011441,128908443,672770020,693544895,236230470,612198388,423348488,136439190,92104085,342710917,506644505,232169652,51614354,127658507,607870455,370675061,272751021,319003324,78852243,751836273,85726159,206085935,388043817,670961154,516627286,459420767,266881388,137385465,875905249,382420000,375846081,776117769,302895801,930271956,817341696,210038104,7275414,104913710,207544939,140611910,115771015,525198486,139613980,45376696,491825522,733827960,754543659,975413620,693321492,134083964,152022067,103235533,63145524,134188854,270351922,214954925,};
int fact(int n){
long z=factbl[n/D];
for(int i=n/D*D;++i<=n;){
z=(z*i)%MD;
}
return z;
}
int inverse(int a){
int b=MD;
int u=1;
int v=0;
int s,t;
while(b){
t=a/b;
s=b; b=a-t*b; a=s;
s=v; v=u-t*v; u=s;
}
if(u<0){
u+=MD;
}
return u;
}
main(){
char rbuf[16];
read(0,rbuf,sizeof rbuf);
char*rp=rbuf;
int n=0;
int c;
while(c=*rp++-48,c>=0){
n=n*10+c;
if(n>MD){
puts("0");
exit(0);
}
}
--n;
int f=n%D<(MD-1-n)%D?n&1?MD-fact(n):fact(n):MD-inverse(fact(MD-1-n));
printf("%d\n",f);
}