結果
| 問題 | No.3394 Big Binom |
| コンテスト | |
| ユーザー |
 回転
|
| 提出日時 | 2025-12-01 01:40:01 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 69 ms / 2,000 ms |
| コード長 | 63,358 bytes |
| 記録 | |
| コンパイル時間 | 255 ms |
| コンパイル使用メモリ | 86,632 KB |
| 実行使用メモリ | 76,800 KB |
| 最終ジャッジ日時 | 2025-12-14 19:59:34 |
| 合計ジャッジ時間 | 2,728 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 22 |
ソースコード
d = {0:1, 316227:406394710,632454:761486477,948681:677224384,1264908:540103656,1581135:215355360,1897362:23566195,2213589:560544100,2529816:393757246,2846043:285108505,3162270:818325958,3478497:66301256,3794724:232674785,4110951:121293611,4427178:497396499,4743405:316795617,5059632:806554427,5375859:475343789,5692086:156795995,6008313:65494850,6324540:179371710,6640767:497736255,6956994:470435359,7273221:827329397,7589448:208292626,7905675:171788583,8221902:286194687,8538129:267904949,8854356:45084098,9170583:448436180,9486810:745181957,9803037:358209154,10119264:787542854,10435491:770681345,10751718:368263666,11067945:602315985,11384172:605742597,11700399:255171903,12016626:439284233,12332853:586497136,12649080:709721097,12965307:683931628,13281534:957784607,13597761:341443644,13913988:448557730,14230215:418993806,14546442:920918964,14862669:850246271,15178896:124587153,15495123:103783587,15811350:406149618,16127577:393974597,16443804:531682399,16760031:339622467,17076258:732133364,17392485:346161001,17708712:214953745,18024939:372971249,18341166:692661106,18657393:876914138,18973620:817111735,19289847:867321164,19606074:989628918,19922301:226593558,20238528:929270036,20554755:927232354,20870982:252618607,21187209:918184688,21503436:390304027,21819663:80444981,22135890:728345048,22452117:518180643,22768344:780075884,23084571:790244589,23400798:144719151,23717025:374151494,24033252:673946868,24349479:865099470,24665706:687555129,24981933:17765526,25298160:715906783,25614387:926339829,25930614:524781716,26246841:693137449,26563068:357195846,26879295:369843839,27195522:110025212,27511749:582311571,27827976:98139234,28144203:244464393,28460430:915728717,28776657:349497119,29092884:89883789,29409111:236173136,29725338:301291382,30041565:596464394,30357792:441024075,30674019:263202768,30990246:819467150,31306473:353697736,31622700:950721155,31938927:21175784,32255154:274251771,32571381:985943560,32887608:930732262,33203835:705616336,33520062:186328063,33836289:366346156,34152516:731947405,34468743:890101040,34784970:52405163,35101197:312545264,35417424:934243866,35733651:402150609,36049878:408734695,36366105:499735012,36682332:519461296,36998559:124105385,37314786:812764730,37631013:733973909,37947240:559632510,38263467:8239627,38579694:560534187,38895921:741392436,39212148:513222843,39528375:429554179,39844602:66977179,40160829:642493853,40477056:600447201,40793283:921527117,41109510:165807495,41425737:626479874,41741964:102217643,42058191:271114527,42374418:985038136,42690645:300823019,43006872:657456784,43323099:375770225,43639326:554891837,43955553:678084645,44271780:102887627,44588007:558152759,44904234:745410841,45220461:450489708,45536688:880019284,45852915:929453298,46169142:705452862,46485369:485659426,46801596:570122597,47117823:365197517,47434050:270059986,47750277:197276247,48066504:47227611,48382731:361329912,48698958:268526492,49015185:523691656,49331412:613663123,49647639:500760907,49963866:442835617,50280093:22402765,50596320:939946864,50912547:926607573,51228774:531139653,51545001:246831811,51861228:52479112,52177455:400568850,52493682:146353197,52809909:32125891,53126136:388137346,53442363:4023120,53758590:543633100,54074817:273764135,54391044:377097073,54707271:473170216,55023498:949736640,55339725:25833043,55655952:329914867,55972179:286814695,56288406:188604026,56604633:17344691,56920860:773804766,57237087:869315549,57553314:421141199,57869541:998189806,58185768:554355410,58501995:992581371,58818222:282922558,59134449:499190922,59450676:46025215,59766903:339281141,60083130:852121027,60399357:201817327,60715584:833437212,61031811:877596879,61348038:714410651,61664265:42102089,61980492:535295167,62296719:324553056,62612946:196354495,62929173:565380454,63245400:932844668,63561627:863805240,63877854:768527727,64194081:478847003,64510308:29781041,64826535:571520232,65142762:697791990,65458989:449657206,65775216:646508359,66091443:810762462,66407670:585757565,66723897:761005294,67040124:792215443,67356351:266530180,67672578:92417917,67988805:440489491,68305032:739225604,68621259:226079663,68937486:14700877,69253713:629657386,69569940:520538768,69886167:252502209,70202394:458037641,70518621:299294944,70834848:225990918,71151075:985212617,71467302:249751610,71783529:918889151,72099756:120003878,72415983:950256475,72732210:313825451,73048437:177942598,73364664:204315599,73680891:637007770,73997118:196156768,74313345:240164722,74629572:165270684,74945799:465577946,75262026:406197708,75578253:545381664,75894480:665579747,76210707:268952550,76526934:279337517,76843161:279628378,77159388:387402710,77475615:318624680,77791842:256360175,78108069:387159757,78424296:88583027,78740523:820772065,79056750:366566745,79372977:301168622,79689204:116110615,80005431:944687373,80321658:965515371,80637885:224688362,80954112:383886813,81270339:804062422,81586566:772269366,81902793:973045694,82219020:858334849,82535247:799155555,82851474:391569485,83167701:123154425,83483928:252891475,83800155:588652476,84116382:773882335,84432609:282715089,84748836:536260942,85065063:533538961,85381290:312444050,85697517:509038425,86013744:836070686,86329971:794395270,86646198:269849209,86962425:387958448,87278652:421588134,87594879:244787179,87911106:443847541,88227333:386310739,88543560:507134850,88859787:163757313,89176014:326139520,89492241:505460687,89808468:341682391,90124695:520887388,90440922:982467255,90757149:203319876,91073376:328831811,91389603:775923461,91705830:590061641,92022057:883163279,92338284:388358764,92654511:886759556,92970738:21910076,93286965:325295325,93603192:256209463,93919419:832716238,94235646:693054334,94551873:544741197,94868100:622975643,95184327:802624773,95500554:920301223,95816781:652134258,96133008:658965983,96449235:440586754,96765462:719911345,97081689:592233854,97397916:203502416,97714143:2857811,98030370:309959729,98346597:557642223,98662824:720995799,98979051:753620304,99295278:411954416,99611505:365276024,99927732:305754327,100243959:340805424,100560186:366494530,100876413:824125442,101192640:511917852,101508867:587143711,101825094:660801071,102141321:447938017,102457548:902039118,102773775:581504545,103090002:722836926,103406229:99645663,103722456:865001610,104038683:544659729,104354910:148632171,104671137:819384263,104987364:634427396,105303591:296171786,105619818:600626571,105936045:37432014,106252272:22514628,106568499:821956296,106884726:260045779,107200953:405986478,107517180:566220412,107833407:375857193,108149634:334390912,108465861:787000505,108782088:621142189,109098315:78381178,109414542:253565842,109730769:870064644,110046996:744944214,110363223:765157823,110679450:375785022,110995677:780524882,111311904:624206336,111628131:601694418,111944358:769313717,112260585:251898897,112576812:955794194,112893039:149378923,113209266:142061357,113525493:304122228,113841720:182100562,114157947:502244726,114474174:462115832,114790401:328539383,115106628:655248883,115422855:108350558,115739082:250461857,116055309:69957061,116371536:538728149,116687763:926500657,117003990:822044248,117320217:977910135,117636444:353567402,117952671:359557227,118268898:573364018,118585125:583951551,118901352:285569196,119217579:991914819,119533806:853911271,119850033:703177744,120166260:61678917,120482487:909285029,120798714:776585821,121114941:452590331,121431168:993902901,121747395:571727590,122063622:117473198,122379849:705463833,122696076:296764102,123012303:545565400,123328530:197448350,123644757:39892975,123960984:453987592,124277211:409747466,124593438:739254607,124909665:852554259,125225892:109858837,125542119:972252952,125858346:660861756,126174573:315480217,126490800:493699633,126807027:482940803,127123254:505274310,127439481:594528015,127755708:60190342,128071935:95295983,128388162:76445146,128704389:194263193,129020616:642442081,129336843:30942414,129653070:182532594,129969297:582069500,130285524:159311395,130601751:69492020,130917978:178256494,131234205:302843403,131550432:989628500,131866659:779422122,132182886:353926807,132499113:488592001,132815340:216681467,133131567:345692734,133447794:996711591,133764021:575771239,134080248:157923356,134396475:126004729,134712702:60274594,135028929:937739212,135345156:849891677,135661383:594228134,135977610:418507579,136293837:118519378,136610064:631775901,136926291:305225812,137242518:202105303,137558745:955675111,137874972:606478538,138191199:585802625,138507426:461612407,138823653:394714794,139139880:113436768,139456107:266780807,139772334:402016182,140088561:172517472,140404788:201870706,140721015:218035468,141037242:95740509,141353469:94750023,141669696:161242663,141985923:55226810,142302150:18220337,142618377:230056600,142934604:540718374,143250831:489408078,143567058:177480073,143883285:231267029,144199512:458486868,144515739:356730159,144831966:676305938,145148193:645283778,145464420:954191655,145780647:811280903,146096874:499794331,146413101:450844045,146729328:278111246,147045555:726914741,147361782:263088571,147678009:784832933,147994236:678542041,148310463:519735254,148626690:253404230,148942917:985042828,149259144:219491885,149575371:695731200,149891598:664668668,150207825:275797435,150524052:145485153,150840279:784602365,151156506:186173574,151472733:614196029,151788960:22283832,152105187:211810854,152421414:86705286,152737641:826837050,153053868:797865924,153370095:788764024,153686322:792698929,154002549:356906629,154318776:412043343,154635003:408487305,154951230:774967427,155267457:723560907,155583684:459401317,155899911:470259194,156216138:126144242,156532365:933299952,156848592:292966132,157164819:386655679,157481046:121405925,157797273:719528368,158113500:795577008,158429727:224512663,158745954:660896495,159062181:226985309,159378408:275182640,159694635:511679586,160010862:522179131,160327089:942807341,160643316:89612920,160959543:815622921,161275770:225075236,161591997:418346844,161908224:912001395,162224451:267692695,162540678:559362499,162856905:924041384,163173132:342874768,163489359:754540853,163805586:193271305,164121813:166160138,164438040:855423022,164754267:859123717,165070494:732037881,165386721:529500908,165702948:778265960,166019175:515177932,166335402:872237495,166651629:574208808,166967856:288139454,167284083:194652980,167600310:760085178,167916537:488318115,168232764:812291507,168548991:333090541,168865218:265410558,169181445:169086456,169497672:271909196,169813899:448715992,170130126:716719094,170446353:398475753,170762580:884059,171078807:500106926,171395034:561748933,171711261:87218896,172027488:400422525,172343715:435273863,172659942:105246580,172976169:849968396,173292396:664508152,173608623:714571058,173924850:604172630,174241077:265522554,174557304:934712108,174873531:914153139,175189758:199171410,175505985:38258359,175822212:95203341,176138439:250084349,176454666:846992293,176770893:438690825,177087120:3579429,177403347:903513286,177719574:246871339,178035801:491257525,178352028:427139265,178668255:287253248,178984482:91056841,179300709:822619605,179616936:878781469,179933163:47550532,180249390:228666806,180565617:521003396,180881844:332981322,181198071:280769646,181514298:189592501,181830525:167299193,182146752:695170626,182462979:716658157,182779206:803439985,183095433:219078604,183411660:72038303,183727887:591118414,184044114:25750537,184360341:487745997,184676568:892251916,184992795:41911176,185309022:61702965,185625249:182133792,185941476:165387641,186257703:857299682,186573930:967552741,186890157:101064364,187206384:677671321,187522611:71705701,187838838:363757388,188155065:730458792,188471292:900920120,188787519:148104285,189103746:939292523,189419973:443959975,189736200:929975723,190052427:547507410,190368654:790611025,190684881:606192209,191001108:307652276,191317335:331219609,191633562:529475702,191949789:773070788,192266016:629258106,192582243:506192956,192898470:698989698,193214697:670432444,193530924:160281140,193847151:630025492,194163378:285043746,194479605:507209596,194795832:997388393,195112059:652914479,195428286:596919135,195744513:37730416,196060740:352948083,196376967:69044382,196693194:879686134,197009421:161014957,197325648:327612428,197641875:468915683,197958102:422485763,198274329:390942924,198590556:627993048,198906783:374047973,199223010:333874609,199539237:620480382,199855464:901334688,200171691:416342956,200487918:777347464,200804145:408555741,201120372:968933939,201436599:720487256,201752826:774988805,202069053:286944347,202385280:849061934,202701507:119440758,203017734:66154074,203333961:171413722,203650188:616581668,203966415:249660500,204282642:551184991,204598869:972683463,204915096:772217083,205231323:196916346,205547550:935562368,205863777:268623937,206180004:859834962,206496231:69949113,206812458:117027975,207128685:168236417,207444912:921958417,207761139:116436974,208077366:218303127,208393593:27224108,208709820:482807344,209026047:400534985,209342274:703728299,209658501:569051525,209974728:9466901,210290955:539726935,210607182:151378149,210923409:311598074,211239636:294673731,211555863:67953627,211872090:508563912,212188317:577428213,212504544:341392525,212820771:620468185,213136998:799307625,213453225:648116115,213769452:614535457,214085679:681279536,214401906:663227385,214718133:984056239,215034360:783799295,215350587:35275990,215666814:118310011,215983041:993131494,216299268:228786071,216615495:87268710,216931722:438221373,217247949:71062834,217564176:764071056,217880403:780414930,218196630:758323484,218512857:331585740,218829084:18356674,219145311:953489306,219461538:745058479,219777765:800589806,220093992:966565939,220410219:930956477,220726446:918875447,221042673:925632376,221358900:268470552,221675127:193114243,221991354:987471275,222307581:272387249,222623808:184599760,222940035:498547800,223256262:866098465,223572489:186413864,223888716:27512420,224204943:429745243,224521170:330874591,224837397:655655942,225153624:529098645,225469851:450589817,225786078:920720435,226102305:480088594,226418532:460800887,226734759:367058897,227050986:747181309,227367213:145368911,227683440:94836389,227999667:290428440,228315894:668132719,228632121:984988889,228948348:1906819,229264575:765864191,229580802:371126974,229897029:276589451,230213256:6688813,230529483:29566877,230845710:910084393,231161937:1436602,231478164:124940136,231794391:414623630,232110618:237157537,232426845:426178214,232743072:187976668,233059299:952986431,233375526:642693615,233691753:78924077,234007980:150500266,234324207:853587228,234640434:211021994,234956661:325667198,235272888:752569563,235589115:306306989,235905342:711293061,236221569:410003174,236537796:442202197,236854023:818904522,237170250:40106059,237486477:353715570,237802704:942104336,238118931:48019599,238435158:893530357,238751385:733804477,239067612:534933824,239383839:93535386,239700066:715490172,240016293:742178402,240332520:84902668,240648747:667993659,240964974:532958668,241281201:451958187,241597428:569923934,241913655:677419775,242229882:794181715,242546109:705221165,242862336:341141610,243178563:681545423,243494790:47687168,243811017:204448461,244127244:469710508,244443471:637707736,244759698:720645442,245075925:433929810,245392152:200451707,245708379:949882133,246024606:261288185,246340833:922305664,246657060:14910110,246973287:690771935,247289514:84520709,247605741:522135507,247921968:61066703,248238195:607455538,248554422:155270962,248870649:86731524,249186876:956285137,249503103:98546220,249819330:53386242,250135557:921632730,250451784:699172513,250768011:39585130,251084238:821200197,251400465:652171836,251716692:812132476,252032919:431255405,252349146:304064214,252665373:911542947,252981600:428723343,253297827:315504303,253614054:995368784,253930281:554009453,254246508:969402236,254562735:744454977,254878962:809019736,255195189:837437480,255511416:148393949,255827643:539532933,256143870:587182946,256460097:203156669,256776324:203401471,257092551:342851903,257408778:250386242,257725005:141126627,258041232:740831569,258357459:400277936,258673686:826942543,258989913:189504200,259306140:740152872,259622367:347251313,259938594:379119243,260254821:780828736,260571048:390091207,260887275:18158231,261203502:775754925,261519729:689153683,261835956:247708768,262152183:279594237,262468410:547066654,262784637:264824834,263100864:725733714,263417091:77796660,263733318:249402162,264049545:680649423,264365772:515756645,264681999:923482461,264998226:444630262,265314453:575191632,265630680:638510908,265946907:642980049,266263134:554751902,266579361:147800187,266895588:464582321,267211815:508211779,267528042:929822202,267844269:671284596,268160496:450630425,268476723:712991686,268792950:191955901,269109177:411947821,269425404:357046242,269741631:941552380,270057858:931666364,270374085:292907614,270690312:627796090,271006539:457088810,271322766:281963284,271638993:789795787,271955220:448618377,272271447:533853585,272587674:466117347,272903901:935273324,273220128:878909999,273536355:667965859,273852582:336690568,274168809:346884621,274485036:151804004,274801263:314334943,275117490:331143312,275433717:203989581,275749944:687618679,276066171:840675811,276382398:406883535,276698625:35358139,277014852:123271029,277331079:312361052,277647306:559686151,277963533:330755807,278279760:793122222,278595987:551696730,278912214:544750763,279228441:67366899,279544668:834242366,279860895:506258453,280177122:594978103,280493349:524887832,280809576:202342737,281125803:334740793,281442030:708923990,281758257:44117355,282074484:576378334,282390711:659459324,282706938:558081657,283023165:430302061,283339392:391755392,283655619:444668051,283971846:486254869,284288073:507946616,284604300:728575559,284920527:109462510,285236754:143897896,285552981:987830146,285869208:402977582,286185435:650478402,286501662:719436440,286817889:933361898,287134116:262917231,287450343:332436169,287766570:599155071,288082797:915221840,288399024:415596440,288715251:353577909,289031478:547652789,289347705:274817950,289663932:647299797,289980159:211892916,290296386:465188780,290612613:814405328,290928840:850036479,291245067:569201996,291561294:427143514,291877521:541982102,292193748:593100396,292509975:281347358,292826202:881551658,293142429:96777222,293458656:453469241,293774883:291143397,294091110:316613419,294407337:578334578,294723564:695765384,295039791:611821634,295356018:307072112,295672245:422013450,295988472:491615219,296304699:347705522,296620926:735247269,296937153:52534845,297253380:442147375,297569607:812470150,297885834:266556729,298202061:404911974,298518288:355629649,298834515:558387302,299150742:97393557,299466969:121184522,299783196:433110584,300099423:892304752,300415650:525709105,300731877:220782295,301048104:685967199,301364331:420039022,301680558:90288272,301996785:925082813,302313012:482005692,302629239:185784323,302945466:32384777,303261693:670874278,303577920:143715742,303894147:691190625,304210374:352761408,304526601:740223438,304842828:830931148,305159055:87988055,305475282:250619697,305791509:802651559,306107736:855810831,306423963:506260891,306740190:968985801,307056417:310348414,307372644:452589678,307688871:59565548,308005098:323196167,308321325:529112573,308637552:912033146,308953779:656201055,309270006:590842388,309586233:481778365,309902460:394796647,310218687:53826564,310534914:738572268,310851141:699864265,311167368:2383622,311483595:337884172,311799822:480123567,312116049:536272800,312432276:143990091,312748503:523606662,313064730:101410595,313380957:559817352,313697184:885977622,314013411:364039392,314329638:518574700,314645865:843757128,314962092:480971799,315278319:665831098,315594546:521779021,315910773:274724801,316227000:298944266,316543227:534695611,316859454:761007625,317175681:340422993,317491908:352407406,317808135:668317802,318124362:81998823,318440589:451849277,318756816:547991612,319073043:933162559,319389270:706137110,319705497:740647396,320021724:415711775,320337951:45485788,320654178:421788570,320970405:29549767,321286632:701781302,321602859:792104442,321919086:295831415,322235313:419226517,322551540:974415830,322867767:319846283,323183994:831172637,323500221:890354593,323816448:707802737,324132675:327870517,324448902:118534228,324765129:919390841,325081356:608562892,325397583:150878119,325713810:621907619,326030037:460845281,326346264:236108754,326662491:12053226,326978718:543132681,327294945:523234420,327611172:759124883,327927399:327183310,328243626:147408363,328559853:329344545,328876080:81257543,329192307:104314782,329508534:414882263,329824761:800542133,330140988:610203285,330457215:16221824,330773442:106000238,331089669:664421747,331405896:943988002,331722123:796917656,332038350:568389071,332354577:429229044,332670804:325771040,332987031:313479575,333303258:268112681,333619485:61199590,333935712:887039480,334251939:493878974,334568166:295572122,334884393:958283498,335200620:687154638,335516847:399906010,335833074:7064903,336149301:666110859,336465528:497998777,336781755:249880522,337097982:688298183,337414209:151863092,337730436:344368658,338046663:344887095,338362890:156523691,338679117:841904484,338995344:748655608,339311571:575989604,339627798:355339972,339944025:711943301,340260252:169052290,340576479:322259004,340892706:718045800,341208933:132773535,341525160:754798992,341841387:445871502,342157614:952533277,342473841:552482838,342790068:988540732,343106295:269894956,343422522:533964246,343738749:58583317,344054976:79482778,344371203:227453178,344687430:743078233,345003657:751069072,345319884:828133753,345636111:444371370,345952338:528092895,346268565:30040407,346584792:128986013,346901019:311991627,347217246:87255154,347533473:659642330,347849700:551440937,348165927:627068221,348482154:921857179,348798381:733241410,349114608:130828126,349430835:88103210,349747062:422718288,350063289:328223577,350379516:412193712,350695743:684015686,351011970:489917361,351328197:111212058,351644424:438973892,351960651:853693466,352276878:580996650,352593105:520626350,352909332:446689009,353225559:321796109,353541786:351636140,353858013:433588195,354174240:427860915,354490467:700307400,354806694:455376382,355122921:439340989,355439148:565223952,355755375:65399224,356071602:443810224,356387829:296880611,356704056:594923995,357020283:141826387,357336510:149433980,357652737:249093031,357968964:183716870,358285191:989276216,358601418:965141349,358917645:603499725,359233872:665602365,359550099:471071363,359866326:533265982,360182553:702276089,360498780:220891583,360815007:535689232,361131234:630459247,361447461:631825455,361763688:225037493,362079915:867103177,362396142:909577705,362712369:46254587,363028596:86204021,363344823:95372457,363661050:377742961,363977277:932269317,364293504:222658283,364609731:774026193,364925958:39604283,365242185:763289090,365558412:954698370,365874639:898697583,366190866:365880698,366507093:682658129,366823320:340667606,367139547:854615192,367455774:817856933,367772001:401375500,368088228:460022405,368404455:814749629,368720682:419080256,369036909:330363458,369353136:967754986,369669363:32798527,369985590:212117167,370301817:874464447,370618044:983705107,370934271:477154390,371250498:229334432,371566725:228764789,371882952:582822366,372199179:843881891,372515406:132865905,372831633:158805274,373147860:812054959,373464087:954226433,373780314:293178297,374096541:853482159,374412768:217151292,374728995:629002988,375045222:712896910,375361449:829832866,375677676:596844143,375993903:359905394,376310130:912315877,376626357:449428221,376942584:680902056,377258811:232919053,377575038:212412420,377891265:516590741,378207492:170075832,378523719:879888061,378839946:409808601,379156173:226994425,379472400:850405273,379788627:730007438,380104854:392529549,380421081:930167682,380737308:368512791,381053535:512556720,381369762:100895202,381685989:741676772,382002216:176643171,382318443:282876258,382634670:669655154,382950897:192499394,383267124:377437896,383583351:800277755,383899578:911934733,384215805:28453996,384532032:551461193,384848259:159265036,385164486:638929144,385480713:167632125,385796940:652544346,386113167:355016935,386429394:580328531,386745621:304928684,387061848:484932928,387378075:340556864,387694302:936893375,388010529:42603960,388326756:103865321,388642983:92916483,388959210:747866720,389275437:748939336,389591664:890830610,389907891:148313780,390224118:80401495,390540345:77893860,390856572:712450432,391172799:295502440,391489026:419554240,391805253:466251951,392121480:124053700,392437707:157193853,392753934:584220231,393070161:480588281,393386388:994247614,393702615:333580441,394018842:845383462,394335069:571850646,394651296:162534614,394967523:145062526,395283750:858909788,395599977:755879573,395916204:809718617,396232431:279424297,396548658:325038955,396864885:18197114,397181112:1789058,397497339:424099125,397813566:687986991,398129793:61515941,398446020:715778323,398762247:401675142,399078474:28850801,399394701:710680816,399710928:234775347,400027155:261017684,400343382:360153703,400659609:53730835,400975836:752404436,401292063:892517305,401608290:636119536,401924517:93041922,402240744:15543725,402556971:958662976,402873198:333814984,403189425:570472432,403505652:937231705,403821879:69264662,404138106:965752810,404454333:427559475,404770560:528640001,405086787:861948006,405403014:15667074,405719241:983711291,406035468:860106914,406351695:816428864,406667922:376865647,406984149:63097737,407300376:958467587,407616603:751005368,407932830:488842060,408249057:666284258,408565284:887504402,408881511:653172883,409197738:144867134,409513965:122131244,409830192:219710614,410146419:681085987,410462646:443309752,410778873:197833103,411095100:223538263,411411327:20616415,411727554:412196728,412043781:925817381,412360008:442628709,412676235:319420110,412992462:303276567,413308689:781337619,413624916:682875469,413941143:915038134,414257370:681976704,414573597:837771058,414889824:800097369,415206051:834317815,415522278:622922145,415838505:783839882,416154732:302782648,416470959:42990656,416787186:884017610,417103413:327899389,417419640:721736732,417735867:291366993,418052094:770595343,418368321:64945300,418684548:773992950,419000775:180974168,419317002:923192576,419633229:181873738,419949456:973069555,420265683:132126441,420581910:750611218,420898137:396217734,421214364:42812631,421530591:826751442,421846818:210285666,422163045:283167384,422479272:485812590,422795499:310264269,423111726:889336636,423427953:82466688,423744180:665422503,424060407:305697594,424376634:563648476,424692861:997992842,425009088:149140948,425325315:185500655,425641542:702286891,425957769:101856147,426273996:155605129,426590223:356139765,426906450:700465178,427222677:72259184,427538904:305451577,427855131:555501888,428171358:461770292,428487585:177610961,428803812:537643720,429120039:10819956,429436266:724606498,429752493:709569143,430068720:317540531,430384947:695139408,430701174:218687785,431017401:791869612,431333628:498911013,431649855:397760311,431966082:183445463,432282309:916051644,432598536:624586335,432914763:864936638,433230990:743346704,433547217:358870476,433863444:359331244,434179671:115558435,434495898:129523960,434812125:278738816,435128352:225720933,435444579:943612871,435760806:828839976,436077033:638381621,436393260:669811742,436709487:675927812,437025714:229858074,437341941:689152246,437658168:354585365,437974395:85918253,438290622:792008366,438606849:923706717,438923076:537627503,439239303:258169658,439555530:703109388,439871757:190781082,440187984:967525760,440504211:376373446,440820438:524845559,441136665:907172935,441452892:82546975,441769119:584444272,442085346:246276722,442401573:901869115,442717800:880460211,443034027:397057358,443350254:164841347,443666481:149982039,443982708:116832977,444298935:245223366,444615162:897846254,444931389:102246043,445247616:570257499,445563843:969087464,445880070:565684730,446196297:50996279,446512524:223509417,446828751:957274236,447144978:216703260,447461205:103318742,447777432:324689193,448093659:549906310,448409886:517720288,448726113:292191975,449042340:603711130,449358567:255489285,449674794:915255067,449991021:926319992,450307248:764917784,450623475:542161413,450939702:844350973,451255929:367107565,451572156:623076489,451888383:972351766,452204610:534267694,452520837:131011641,452837064:990559350,453153291:546844450,453469518:901224570,453785745:467617919,454101972:982710689,454418199:598639084,454734426:826753771,455050653:950173367,455366880:991566781,455683107:939646408,455999334:952226736,456315561:427985575,456631788:284754310,456948015:772988030,457264242:380166731,457580469:105165752,457896696:438423587,458212923:197664179,458529150:140979368,458845377:441625857,459161604:608406314,459477831:121639885,459794058:780764090,460110285:426947819,460426512:236379207,460742739:796163728,461058966:492816422,461375193:665113284,461691420:455146168,462007647:912342081,462323874:280002024,462640101:431014170,462956328:507567505,463272555:45250978,463588782:392136836,463905009:260217813,464221236:246618648,464537463:543768804,464853690:918293385,465169917:614039160,465486144:971996694,465802371:17672139,466118598:956774810,466434825:392316811,466751052:572604466,467067279:555758395,467383506:606759863,467699733:632594894,468015960:79162139,468332187:279396832,468648414:477017225,468964641:760014428,469280868:539834813,469597095:366475241,469913322:893835433,470229549:615731899,470545776:343484194,470862003:587256896,471178230:842783620,471494457:86581153,471810684:806250978,472126911:28346503,472443138:770593104,472759365:594629294,473075592:509709930,473391819:886247643,473708046:463915546,474024273:252309113,474340500:727731538,474656727:338027011,474972954:276544599,475289181:393134703,475605408:324523585,475921635:730965486,476237862:362407134,476554089:478758875,476870316:525181297,477186543:421226351,477502770:38182108,477818997:693747787,478135224:124419793,478451451:791483856,478767678:369629825,479083905:860434629,479400132:54260184,479716359:713701804,480032586:523799100,480348813:106683476,480665040:461942225,480981267:752031127,481297494:531015842,481613721:844708526,481929948:45834212,482246175:994021956,482562402:890816115,482878629:369045796,483194856:341497808,483511083:571290697,483827310:373180852,484143537:86442449,484459764:237377912,484775991:648101316,485092218:992461756,485408445:389159259,485724672:595030194,486040899:615296432,486357126:149796756,486673353:71560291,486989580:110521575,487305807:74758964,487622034:40277679,487938261:860852603,488254488:847306533,488570715:962063058,488886942:213184640,489203169:93835134,489519396:108850379,489835623:20636675,490151850:63541762,490468077:814916884,490784304:937656944,491100531:477926697,491416758:648030131,491732985:383328169,492049212:845163982,492365439:632612596,492681666:520412627,492997893:263190929,493314120:71672123,493630347:629245019,493946574:722009096,494262801:565099052,494579028:795287287,494895255:722205741,495211482:241484337,495527709:78333186,495843936:820206640,496160163:931445902,496476390:574429319,496792617:809843388,497108844:447909487,497425071:789708565,497741298:138765919,498057525:298869448,498373752:988515130,498689979:24770464,499006206:682521387,499322433:902662578,499638660:828128803,499954887:278883184,500271114:853838092,500587341:976275659,500903568:1921038,501219795:343893919,501536022:467752532,501852249:193053304,502168476:729149686,502484703:283199530,502800930:691788882,503117157:811775207,503433384:503895870,503749611:198501858,504065838:769276551,504382065:638947939,504698292:160438465,505014519:859126034,505330746:637281242,505646973:769231178,505963200:37358656,506279427:629173392,506595654:949209601,506911881:267070817,507228108:492115104,507544335:264306288,507860562:657535896,508176789:219484478,508493016:34167460,508809243:136801539,509125470:179854267,509441697:952197303,509757924:850471677,510074151:242617911,510390378:165644682,510706605:964746398,511022832:187715624,511339059:902825370,511655286:311905526,511971513:745460976,512287740:771521672,512603967:251656462,512920194:789703882,513236421:917105710,513552648:204456164,513868875:154330531,514185102:466316889,514501329:548791709,514817556:167216223,515133783:143390860,515450010:781583470,515766237:936579647,516082464:322401769,516398691:389498792,516714918:200984172,517031145:871620559,517347372:337030054,517663599:940482911,517979826:222305046,518296053:143831141,518612280:986679369,518928507:803476902,519244734:235206906,519560961:166614130,519877188:560516158,520193415:116232117,520509642:214181936,520825869:137655241,521142096:768147964,521458323:333234263,521774550:263313458,522090777:210853191,522407004:516234745,522723231:607515519,523039458:606764575,523355685:83538734,523671912:516590899,523988139:966575719,524304366:836314046,524620593:822860769,524936820:779229005,525253047:804937129,525569274:1919519,525885501:821101847,526201728:362552297,526517955:657203425,526834182:264316538,527150409:90084517,527466636:796623657,527782863:745077515,528099090:726706775,528415317:355098944,528731544:571995441,529047771:911433377,529363998:15306345,529680225:56922573,529996452:79781754,530312679:542886210,530628906:47005384,530945133:461640174,531261360:117845291,531577587:622244824,531893814:893334889,532210041:123149575,532526268:651293897,532842495:550587156,533158722:488768378,533474949:570183942,533791176:546512905,534107403:589598911,534423630:77699872,534739857:808333478,535056084:654511990,535372311:937651815,535688538:820499630,536004765:589130575,536320992:982262769,536637219:736002216,536953446:692313457,537269673:47437993,537585900:723166265,537902127:293054538,538218354:840834215,538534581:332990651,538850808:218795833,539167035:957347703,539483262:247163677,539799489:594046862,540115716:266357691,540431943:743813014,540748170:64207077,541064397:279356367,541380624:23985098,541696851:594704165,542013078:794521228,542329305:760823755,542645532:591945544,542961759:221466799,543277986:530450177,543594213:379090495,543910440:255934746,544226667:632288911,544542894:371893286,544859121:933938601,545175348:687915444,545491575:955425490,545807802:111516520,546124029:295607571,546440256:223478427,546756483:206978004,547072710:723364116,547388937:784038767,547705164:187118878,548021391:782920527,548337618:564354133,548653845:224484423,548970072:696796810,549286299:743013087,549602526:277162711,549918753:28803648,550234980:41331744,550551207:227309055,550867434:262702006,551183661:124182171,551499888:452717255,551816115:760106663,552132342:972641534,552448569:636070070,552764796:368057438,553081023:605945376,553397250:104980917,553713477:804849025,554029704:453488514,554345931:825673359,554662158:900330129,554978385:726993664,555294612:699217378,555610839:396268253,555927066:853761551,556243293:276359406,556559520:146381297,556875747:821684691,557191974:712457083,557508201:510674431,557824428:995444789,558140655:9112247,558456882:286748012,558773109:713571822,559089336:665302632,559405563:677172806,559721790:375068524,560038017:665048888,560354244:288192500,560670471:878702011,560986698:951094671,561302925:309313925,561619152:757380783,561935379:98388260,562251606:929826969,562567833:886855659,562884060:794372420,563200287:217976837,563516514:3678533,563832741:460411317,564148968:637639963,564465195:799996957,564781422:3844930,565097649:881276968,565413876:960998043,565730103:7432869,566046330:395545225,566362557:105805737,566678784:317067562,566995011:289059767,567311238:37990128,567627465:81215237,567943692:195146701,568259919:726996561,568576146:253915525,568892373:688377393,569208600:676124456,569524827:221813108,569841054:473625091,570157281:603715984,570473508:716406839,570789735:971151859,571105962:361487542,571422189:233415897,571738416:239053973,572054643:883189019,572370870:692317784,572687097:355415060,573003324:670374280,573319551:920819035,573635778:705009981,573952005:852245891,574268232:379705930,574584459:632053045,574900686:142457560,575216913:309612324,575533140:40539899,575849367:437391454,576165594:503124140,576481821:463187123,576798048:824085670,577114275:460900787,577430502:977953101,577746729:909498316,578062956:34029375,578379183:424766377,578695410:805305593,579011637:291399092,579327864:434456830,579644091:19153326,579960318:784089229,580276545:282494960,580592772:486123166,580908999:703023098,581225226:862934110,581541453:779182796,581857680:789461985,582173907:114600933,582490134:36168144,582806361:351599190,583122588:881201440,583438815:184548439,583755042:485364920,584071269:806737443,584387496:900879300,584703723:809767322,585019950:301050604,585336177:323274540,585652404:414318870,585968631:890174186,586284858:739414842,586601085:542950407,586917312:187471097,587233539:880546424,587549766:944134543,587865993:231592794,588182220:556761718,588498447:679629349,588814674:722210144,589130901:82788734,589447128:4140036,589763355:40429880,590079582:758834472,590395809:146504530,590712036:618899643,591028263:635573788,591344490:81607584,591660717:470906276,591976944:51147402,592293171:215444260,592609398:491183504,592925625:81934412,593241852:158384768,593558079:692431882,593874306:694395621,594190533:734394553,594506760:386559716,594822987:74276385,595139214:322818432,595455441:818041955,595771668:566331393,596087895:593372579,596404122:779044464,596720349:638421751,597036576:386825595,597352803:725435798,597669030:971490815,597985257:760296206,598301484:876328934,598617711:818261693,598933938:758361572,599250165:38594838,599566392:271333119,599882619:692276684,600198846:482764999,600515073:967394691,600831300:836593404,601147527:850969553,601463754:708226299,601779981:18018475,602096208:1039592,602412435:584670253,602728662:502942534,603044889:667827312,603361116:823025002,603677343:205878634,603993570:118272216,604309797:102297901,604626024:787615255,604942251:672483486,605258478:648469816,605574705:296685483,605890932:854351902,606207159:154348478,606523386:960668719,606839613:283506667,607155840:22536457,607472067:250050479,607788294:354524124,608104521:854826706,608420748:685980364,608736975:531624633,609053202:795913407,609369429:74026978,609685656:874103257,610001883:224269651,610318110:433946028,610634337:224450368,610950564:636438852,611266791:476852893,611583018:21104193,611899245:272999083,612215472:120019501,612531699:986213244,612847926:565955368,613164153:327087465,613480380:474668485,613796607:47154472,614112834:364736944,614429061:843696396,614745288:282548075,615061515:783786579,615377742:47419277,615693969:472426403,616010196:865451170,616326423:108866889,616642650:893129171,616958877:668355058,617275104:121676216,617591331:579395404,617907558:480388939,618223785:260442955,618540012:983001747,618856239:544821484,619172466:516567757,619488693:975003698,619804920:372688798,620121147:191155609,620437374:198631294,620753601:21000411,621069828:624227880,621386055:405403123,621702282:645991106,622018509:24705561,622334736:159563668,622650963:209295533,622967190:289971969,623283417:49027140,623599644:555707301,623915871:41051269,624232098:971023837,624548325:61015127,624864552:454946127,625180779:874912805,625497006:888797578,625813233:672683610,626129460:396365951,626445687:181109584,626761914:668497648,627078141:314942779,627394368:26591718,627710595:746797846,628026822:40873443,628343049:720485326,628659276:450105351,628975503:907507410,629291730:270211409,629607957:467185239,629924184:899213518,630240411:764790271,630556638:865014635,630872865:638523755,631189092:831940940,631505319:507977025,631821546:743524786,632137773:389224090,632454000:69270997,632770227:605193690,633086454:466964147,633402681:793637561,633718908:179800868,634035135:926736762,634351362:481612172,634667589:127282996,634983816:848635953,635300043:559500749,635616270:225814751,635932497:800341649,636248724:37369492,636564951:811190574,636881178:336106309,637197405:580139137,637513632:474288644,637829859:581128256,638146086:886278421,638462313:975940818,638778540:675649294,639094767:622876141,639410994:692516014,639727221:713604128,640043448:972328641,640359675:354272035,640675902:367088187,640992129:520593214,641308356:115127349,641624583:389282370,641940810:344120165,642257037:948775956,642573264:286739785,642889491:592292213,643205718:747986728,643521945:313040696,643838172:435936045,644154399:99536277,644470626:98126186,644786853:731731219,645103080:440222966,645419307:127379620,645735534:430526884,646051761:310192804,646367988:357432457,646684215:683936580,647000442:582063640,647316669:52955846,647632896:473594375,647949123:132128476,648265350:499482651,648581577:8925599,648897804:575483768,649214031:193446292,649530258:890313380,649846485:652875234,650162712:840588589,650478939:741010149,650795166:326633111,651111393:28643272,651427620:686360996,651743847:977087746,652060074:714060569,652376301:648221087,652692528:613115110,653008755:46580729,653324982:929568987,653641209:38173397,653957436:864863112,654273663:629068588,654589890:487475177,654906117:758310232,655222344:155993061,655538571:675405873,655854798:601370153,656171025:260202241,656487252:919872546,656803479:845140473,657119706:398667144,657435933:283329744,657752160:522241850,658068387:530682233,658384614:399164062,658700841:252077702,659017068:786297111,659333295:791673045,659649522:303661692,659965749:880056305,660281976:14638418,660598203:904954630,660914430:819287436,661230657:731113187,661546884:824206865,661863111:650049956,662179338:365631037,662495565:9568154,662811792:590395871,663128019:62588135,663444246:463134749,663760473:567204335,664076700:134023582,664392927:79353795,664709154:938379879,665025381:900260974,665341608:212332947,665657835:376083213,665974062:36912036,666290289:831668371,666606516:225460565,666922743:277293880,667238970:60202865,667555197:565931073,667871424:703963931,668187651:791218461,668503878:473196940,668820105:732660816,669136332:552325598,669452559:257782412,669768786:320427683,670085013:380925513,670401240:759006722,670717467:174005707,671033694:78678899,671349921:897766938,671666148:313640463,671982375:27551312,672298602:18634627,672614829:212114599,672931056:17145439,673247283:327861258,673563510:509883692,673879737:567123,674195964:905974880,674512191:16580269,674828418:885843266,675144645:176436203,675460872:925950314,675777099:994664520,676093326:983711094,676409553:32766814,676725780:515572681,677042007:191606691,677358234:498391742,677674461:197641060,677990688:354081865,678306915:536882203,678623142:884785181,678939369:808876978,679255596:571710280,679571823:863766091,679888050:704269108,680204277:39606542,680520504:408135273,680836731:673391761,681152958:588267682,681469185:146921626,681785412:739865944,682101639:543947981,682417866:146444398,682734093:468670002,683050320:659535999,683366547:258549210,683682774:184371566,683999001:373081636,684315228:387985491,684631455:474647538,684947682:541214636,685263909:911907646,685580136:431922744,685896363:237936332,686212590:962976207,686528817:142665159,686845044:668310331,687161271:923303985,687477498:667371213,687793725:482379525,688109952:673371148,688426179:770540995,688742406:433533189,689058633:553924826,689374860:497616728,689691087:902612459,690007314:9978215,690323541:153085108,690639768:149560444,690955995:700981912,691272222:436548346,691588449:488665504,691904676:401743860,692220903:944948519,692537130:140239315,692853357:644373464,693169584:133245000,693485811:975988600,693802038:817637517,694118265:973342513,694434492:549724899,694750719:730391083,695066946:917661453,695383173:856680044,695699400:996877664,696015627:92034490,696331854:859875885,696648081:575339905,696964308:616878698,697280535:434689456,697596762:279310928,697912989:453339894,698229216:707277938,698545443:869491136,698861670:499195392,699177897:336552306,699494124:241334521,699810351:334226207,700126578:180709802,700442805:560178489,700759032:80749799,701075259:829447964,701391486:408829331,701707713:52332356,702023940:28772966,702340167:599675275,702656394:579660323,702972621:832245374,703288848:165640458,703605075:429579883,703921302:432166095,704237529:282061565,704553756:609951770,704869983:326178071,705186210:42030460,705502437:493177444,705818664:686068365,706134891:493152162,706451118:136414112,706767345:968681958,707083572:953048065,707399799:990926419,707716026:790918522,708032253:699957265,708348480:696727154,708664707:5183246,708980934:43489822,709297161:938001367,709613388:474118221,709929615:155168121,710245842:474243222,710562069:501422133,710878296:117872636,711194523:971339509,711510750:502561050,711826977:226097122,712143204:38925266,712459431:810417769,712775658:609446437,713091885:617072932,713408112:442336700,713724339:335947597,714040566:276550049,714356793:940517123,714673020:239053360,714989247:127835381,715305474:181248936,715621701:224426894,715937928:378027356,716254155:623237671,716570382:474362746,716886609:96327374,717202836:223082406,717519063:347075103,717835290:162191485,718151517:50869363,718467744:479783397,718783971:9478171,719100198:383336454,719416425:923757238,719732652:819535401,720048879:5033801,720365106:243741801,720681333:604724884,720997560:599258504,721313787:614411289,721630014:705290604,721946241:136361137,722262468:657628606,722578695:489807910,722894922:502055867,723211149:678952992,723527376:653533904,723843603:342765152,724159830:205397752,724476057:488908362,724792284:717280942,725108511:702929656,725424738:688692307,725740965:516726482,726057192:284246435,726373419:574767280,726689646:510472767,727005873:622754500,727322100:530861601,727638327:507195417,727954554:621116037,728270781:6625018,728587008:686097394,728903235:648486843,729219462:405981105,729535689:120589360,729851916:359857583,730168143:206909999,730484370:855780630,730800597:596224234,731116824:295749378,731433051:161881897,731749278:905584,732065505:787140861,732381732:760553497,732697959:692437785,733014186:127741976,733330413:546528365,733646640:457762690,733962867:281571587,734279094:809373928,734595321:50831388,734911548:963125852,735227775:760520778,735544002:114957960,735860229:42712740,736176456:950080791,736492683:243280719,736808910:12227785,737125137:364246214,737441364:484941357,737757591:28083091,738073818:749774558,738390045:86958462,738706272:964041303,739022499:122945927,739338726:780199829,739654953:346413362,739971180:757677412,740287407:650900265,740603634:862110267,740919861:661974233,741236088:209880525,741552315:873617971,741868542:132003533,742184769:330901127,742500996:964440766,742817223:217529296,743133450:785220951,743449677:771268556,743765904:348661026,744082131:822553483,744398358:191762436,744714585:707173120,745030812:275088635,745347039:87533544,745663266:510884920,745979493:878642584,746295720:502948390,746611947:349254490,746928174:690305399,747244401:29217470,747560628:723233430,747876855:818147180,748193082:654830818,748509309:73885553,748825536:784521188,749141763:857280107,749457990:125067806,749774217:272652223,750090444:501273947,750406671:32634001,750722898:434328156,751039125:596026665,751355352:846049548,751671579:295729671,751987806:299199448,752304033:935044850,752620260:403513514,752936487:890366578,753252714:169820194,753568941:179783985,753885168:356716835,754201395:584699032,754517622:561808093,754833849:958650232,755150076:944990909,755466303:364400330,755782530:163701880,756098757:194459669,756414984:583609478,756731211:726985975,757047438:118936287,757363665:333509829,757679892:87326261,757996119:158135557,758312346:919217824,758628573:249290441,758944800:187576127,759261027:831078938,759577254:913392844,759893481:896350147,760209708:189907410,760525935:269934355,760842162:463196400,761158389:645158316,761474616:796106609,761790843:339155216,762107070:269079850,762423297:791400691,762739524:706710596,763055751:401293957,763371978:919413977,763688205:265778546,764004432:317297995,764320659:388490604,764636886:177200169,764953113:978686018,765269340:785556634,765585567:489244524,765901794:910038983,766218021:258056262,766534248:709753306,766850475:354733626,767166702:237632727,767482929:73889084,767799156:303095049,768115383:617223495,768431610:616411671,768747837:746022010,769064064:658646118,769380291:75233435,769696518:872222090,770012745:634088604,770328972:781332430,770645199:412913580,770961426:65677949,771277653:785230329,771593880:989060668,771910107:708188728,772226334:434069522,772542561:292412242,772858788:747287790,773175015:597912013,773491242:46765934,773807469:585122696,774123696:945547885,774439923:472312288,774756150:545012724,775072377:947803543,775388604:534850496,775704831:93127221,776021058:437170130,776337285:779934222,776653512:967039205,776969739:702254330,777285966:396406383,777602193:888691570,777918420:927948258,778234647:234481816,778550874:238060642,778867101:652047706,779183328:107497701,779499555:494128956,779815782:470393704,780132009:188487194,780448236:306115530,780764463:602810840,781080690:551448461,781396917:303661048,781713144:255640245,782029371:285916494,782345598:812503603,782661825:33130476,782978052:98674252,783294279:714935567,783610506:779957456,783926733:144374842,784242960:629276533,784559187:977154537,784875414:645065688,785191641:304684869,785507868:792534254,785824095:641538481,786140322:613883775,786456549:798593906,786772776:409140187,787089003:222860913,787405230:978431510,787721457:250807817,788037684:704484723,788353911:393554270,788670138:208486547,788986365:41955026,789302592:42778881,789618819:805873793,789935046:654121865,790251273:791273286,790567500:230312851,790883727:866123343,791199954:199742390,791516181:624539928,791832408:243481904,792148635:129093212,792464862:12316506,792781089:345000748,793097316:344835072,793413543:698695616,793729770:634745036,794045997:573499914,794362224:979266144,794678451:492330761,794994678:947935840,795310905:651304197,795627132:40265881,795943359:990286861,796259586:888071407,796575813:848844869,796892040:51961070,797208267:382081848,797524494:503093719,797840721:300993026,798156948:83053564,798473175:116077407,798789402:671332485,799105629:181713042,799421856:392416050,799738083:967495287,800054310:254430233,800370537:784524175,800686764:135930373,801002991:367830510,801319218:993837168,801635445:251220977,801951672:808262710,802267899:267059710,802584126:577315440,802900353:486802247,803216580:340256691,803532807:745020384,803849034:279682646,804165261:476462475,804481488:140052913,804797715:876634363,805113942:656715743,805430169:485071569,805746396:874645597,806062623:229096789,806378850:205653705,806695077:881544721,807011304:393780979,807327531:496996247,807643758:537621024,807959985:50552296,808276212:638871020,808592439:156619901,808908666:288163589,809224893:690227206,809541120:917268844,809857347:3977714,810173574:794841857,810489801:423470742,810806028:895421559,811122255:196437579,811438482:790561027,811754709:713691709,812070936:432669702,812387163:629843754,812703390:840337864,813019617:55428427,813335844:317382782,813652071:824430892,813968298:928616691,814284525:615796972,814600752:870104338,814916979:986979821,815233206:325027689,815549433:547117882,815865660:491260351,816181887:694486302,816498114:605946811,816814341:867281536,817130568:329647737,817446795:829862102,817763022:416639090,818079249:96746657,818395476:224718211,818711703:439758013,819027930:205944516,819344157:821762307,819660384:760461656,819976611:128210749,820292838:605411730,820609065:297544487,820925292:35187668,821241519:605389981,821557746:648242079,821873973:395314326,822190200:759657695,822506427:370954613,822822654:397572201,823138881:910764866,823455108:846420975,823771335:847057942,824087562:871557338,824403789:415443734,824720016:866182426,825036243:368933387,825352470:910635956,825668697:605540741,825984924:718743547,826301151:953918455,826617378:450389440,826933605:261820874,827249832:2002711,827566059:150572461,827882286:734921161,828198513:93720850,828514740:384051636,828830967:503075993,829147194:898697994,829463421:832944558,829779648:953238445,830095875:496501167,830412102:363559082,830728329:916067710,831044556:554537143,831360783:306420479,831677010:431107457,831993237:965403951,832309464:662369743,832625691:215552658,832941918:315827671,833258145:341467847,833574372:226203143,833890599:197451279,834206826:289333572,834523053:930364681,834839280:775643738,835155507:571197770,835471734:361357573,835787961:525144883,836104188:197717676,836420415:399645177,836736642:991824809,837052869:520234686,837369096:976560873,837685323:841758950,838001550:266287452,838317777:582053902,838634004:200391133,838950231:801873755,839266458:38011960,839582685:982256130,839898912:292247818,840215139:212926771,840531366:973674899,840847593:808767116,841163820:786614012,841480047:610921024,841796274:735107767,842112501:137448082,842428728:198581906,842744955:446950886,843061182:743964841,843377409:855226250,843693636:681837485,844009863:478193155,844326090:484691184,844642317:629642252,844958544:436369881,845274771:266747977,845590998:164087681,845907225:693853133,846223452:486047828,846539679:868363725,846855906:650198427,847172133:255579371,847488360:312148847,847804587:463707648,848120814:643925466,848437041:973687211,848753268:482141585,849069495:900511540,849385722:379985155,849701949:316131608,850018176:438388159,850334403:811965521,850650630:395386791,850966857:533874947,851283084:731368884,851599311:656309680,851915538:733023383,852231765:438131044,852547992:813561364,852864219:954483333,853180446:559671901,853496673:556255490,853812900:56355334,854129127:987787637,854445354:432753190,854761581:502422943,855077808:106075208,855394035:621519097,855710262:749022174,856026489:384949524,856342716:766323671,856658943:298987124,856975170:620933863,857291397:335714824,857607624:546111485,857923851:305642982,858240078:592379461,858556305:435114228,858872532:741486664,859188759:741500202,859504986:713635542,859821213:805947603,860137440:466083058,860453667:923739199,860769894:345515120,861086121:136822262,861402348:579277800,861718575:192946877,862034802:972119858,862351029:652601238,862667256:996671270,862983483:173588943,863299710:861315858,863615937:96333660,863932164:542937405,864248391:156212720,864564618:119094883,864880845:504972898,865197072:682496088,865513299:78125919,865829526:624652684,866145753:615525685,866461980:480961685,866778207:200372749,867094434:464103639,867410661:343512256,867726888:93188880,868043115:626018642,868359342:553208680,868675569:500161731,868991796:871085239,869308023:975727334,869624250:666931950,869940477:350587760,870256704:293129956,870572931:739466998,870889158:59736912,871205385:551303460,871521612:724496797,871837839:551580133,872154066:128080316,872470293:600538742,872786520:143909397,873102747:816963704,873418974:537170793,873735201:652753588,874051428:504546325,874367655:821963656,874683882:671286454,875000109:621310618,875316336:408636970,875632563:610157226,875948790:858944791,876265017:290089137,876581244:105026123,876897471:674448920,877213698:683893972,877529925:336393699,877846152:893694746,878162379:472485007,878478606:676734373,878794833:132736169,879111060:338124442,879427287:642124757,879743514:77983247,880059741:703581419,880375968:41760874,880692195:841834303,881008422:635929232,881324649:850803364,881640876:639059695,881957103:402973737,882273330:432006989,882589557:591579007,882905784:256507564,883222011:459904884,883538238:268344868,883854465:750068808,884170692:800554558,884486919:148947497,884803146:35755924,885119373:518699008,885435600:270745084,885751827:136659515,886068054:393219559,886384281:224844240,886700508:140267545,887016735:310181234,887332962:659853621,887649189:521741177,887965416:65463730,888281643:57242233,888597870:223368080,888914097:845044675,889230324:3662789,889546551:88216215,889862778:430522789,890179005:805842448,890495232:493880442,890811459:941390932,891127686:856761850,891443913:640828440,891760140:655881456,892076367:766141305,892392594:761825251,892708821:433714426,893025048:32563159,893341275:648653537,893657502:160909178,893973729:973755715,894289956:6216245,894606183:228648184,894922410:38464797,895238637:376750505,895554864:463983372,895871091:496439902,896187318:742110865,896503545:48629004,896819772:489951472,897135999:871714782,897452226:414266250,897768453:957396061,898084680:285524264,898400907:783746096,898717134:124458295,899033361:495936664,899349588:675462326,899665815:231402782,899982042:129684964,900298269:567031525,900614496:341081253,900930723:293179958,901246950:833890235,901563177:108337993,901879404:643076011,902195631:910625054,902511858:701788138,902828085:307368589,903144312:220055268,903460539:604758218,903776766:844772976,904092993:688159180,904409220:388316702,904725447:440277752,905041674:930337309,905357901:532728745,905674128:483534215,905990355:470668021,906306582:256081526,906622809:449382190,906939036:128068730,907255263:800458716,907571490:650852196,907887717:837838133,908203944:222712800,908520171:892045134,908836398:523361965,909152625:793085870,909468852:678637600,909785079:891602488,910101306:983168923,910417533:553216432,910733760:222286950,911049987:197120193,911366214:636265441,911682441:792261366,911998668:653066024,912314895:416348073,912631122:409557856,912947349:767206642,913263576:645567442,913579803:474591919,913896030:539049648,914212257:308274091,914528484:395143202,914844711:294181406,915160938:512928399,915477165:958250133,915793392:460533022,916109619:792575682,916425846:854893502,916742073:307753643,917058300:752529776,917374527:642456550,917690754:417728963,918006981:137914042,918323208:433750650,918639435:541124171,918955662:590631148,919271889:185994696,919588116:493699315,919904343:397854833,920220570:879457218,920536797:607075627,920853024:67733703,921169251:847009779,921485478:992584263,921801705:5203478,922117932:967644879,922434159:806705789,922750386:337532569,923066613:661481566,923382840:972836345,923699067:803171858,924015294:710337783,924331521:972088441,924647748:686080978,924963975:424742812,925280202:598766465,925596429:742540617,925912656:241397178,926228883:378204272,926545110:750000246,926861337:79856473,927177564:861313543,927493791:362974635,927810018:994827749,928126245:334794324,928442472:636084112,928758699:990133532,929074926:51339939,929391153:48379400,929707380:295632929,930023607:383423857,930339834:363454414,930656061:517142143,930972288:617331975,931288515:383409312,931604742:798969887,931920969:683260308,932237196:8174818,932553423:923301395,932869650:241928484,933185877:346067229,933502104:529399765,933818331:147721725,934134558:159156737,934450785:221038270,934767012:338797173,935083239:265976059,935399466:414153878,935715693:510537740,936031920:279285047,936348147:580626243,936664374:834708040,936980601:560790029,937296828:724879102,937613055:125156669,937929282:309691695,938245509:844350458,938561736:812823936,938877963:715865736,939194190:90372960,939510417:852961205,939826644:838138944,940142871:173590749,940459098:960431535,940775325:108393426,941091552:357066252,941407779:744077158,941724006:569521915,942040233:674252305,942356460:262161228,942672687:221069302,942988914:674214640,943305141:469898845,943621368:238688126,943937595:907522120,944253822:860053922,944570049:178631764,944886276:275868171,945202503:448276032,945518730:373813111,945834957:850327536,946151184:861567593,946467411:831314884,946783638:409520882,947099865:667628006,947416092:932315143,947732319:870973801,948048546:271186979,948364773:568813433,948681000:705560846,948997227:589340386,949313454:770457213,949629681:595454465,949945908:222645609,950262135:839071127,950578362:30374396,950894589:828289777,951210816:459606700,951527043:714646878,951843270:822352550,952159497:640140074,952475724:951610506,952791951:318231492,953108178:354100057,953424405:582700418,953740632:137951998,954056859:543143012,954373086:982354926,954689313:861372250,955005540:237112039,955321767:191338827,955637994:320617703,955954221:26975548,956270448:470882101,956586675:731600838,956902902:693334224,957219129:890389309,957535356:255243401,957851583:245414030,958167810:889623720,958484037:911226844,958800264:128937145,959116491:768275883,959432718:42056984,959748945:509412168,960065172:138016206,960381399:371213445,960697626:109087888,961013853:871677443,961330080:249209861,961646307:171185932,961962534:986462919,962278761:882701145,962594988:930332689,962911215:277978774,963227442:667393604,963543669:149414837,963859896:880017286,964176123:732292380,964492350:496328265,964808577:543730155,965124804:193016289,965441031:73857565,965757258:527919098,966073485:1043409,966389712:489057542,966705939:619358359,967022166:374186755,967338393:134112424,967654620:447373255,967970847:962358696,968287074:736386801,968603301:49055933,968919528:643137524,969235755:965731508,969551982:949219215,969868209:388644090,970184436:819634382,970500663:299334270,970816890:232042181,971133117:695886870,971449344:525553075,971765571:383482655,972081798:563319056,972398025:970988217,972714252:23826066,973030479:879313346,973346706:640920235,973662933:231216925,973979160:39300303,974295387:113143168,974611614:173623305,974927841:295641831,975244068:167660016,975560295:621333987,975876522:151040270,976192749:313126750,976508976:224816508,976825203:689566808,977141430:738583519,977457657:863953079,977773884:989628001,978090111:690036166,978406338:692411202,978722565:115805854,979038792:207670106,979355019:410140081,979671246:480491376,979987473:317227307,980303700:78461662,980619927:662575285,980936154:473548431,981252381:234264382,981568608:899597976,981884835:406305458,982201062:860148101,982517289:454838265,982833516:67152442,983149743:577138259,983465970:82553719,983782197:132210992,984098424:883674994,984414651:879931748,984730878:431843813,985047105:119655256,985363332:196178778,985679559:45675891,985995786:256165899,986312013:811105489,986628240:239217623,986944467:409033435,987260694:626200969,987576921:729514066,987893148:276201952,988209375:180119113,988525602:628641633,988841829:18020038,989158056:785224558,989474283:590947785,989790510:610002275,990106737:828117868,990422964:217706527,990739191:426020380,991055418:93662836,991371645:134549864,991687872:500641523,992004099:750036420,992320326:264088054,992636553:81711118,992952780:365577699,993269007:898431635,993585234:219107066,993901461:960147617,994217688:525812663,994533915:974257598,994850142:241643199,995166369:370289385,995482596:446721750,995798823:51346317,996115050:175225974,996431277:721977379,996747504:528612624,997063731:931908752,997379958:797901405,997696185:358053622,998012412:122028895,998328639:0,998644866:0,998961093:0,999277320:0,999593547:0,999909774:0}
MOD=998244353
a=sorted(d.items())
N,K=list(map(int,input().split()))
if(K > N-K):K = N-K
if(K<=2*10**6):
bunshi=1
for i in range(K):
bunshi*=N-i
bunshi%=MOD
if(bunshi == 0):
print(0)
exit()
bunbo=1
for i in range(1,K+1):
bunbo*=i
bunbo%=MOD
print(bunshi*pow(bunbo,-1,MOD)%MOD)
else:
def get_bikkuri(n):
ok,ng=0,len(a)
while(ng-ok>1):
mid=(ok+ng)//2
if(a[mid][0]<=n):
ok=mid
else:
ng=mid
ret=a[ok][1]
for i in range(a[ok][0]+1,n+1):
ret*=i
ret%=MOD
return ret
r=get_bikkuri(K)
n_minus_r=get_bikkuri(N-K)
n=get_bikkuri(N)
if(n_minus_r == 0 or r == 0):
print(0)
exit()
print(n*pow(n_minus_r,-1,MOD)*pow(r,-1,MOD)%MOD)