#1137972 (C++17) No.3394 Big Binom

• 問題: No.3394 Big Binom
• ユーザー: The Forsaking
• 提出日時: 2025-12-02 16:20:56
• 言語: C++17 (gcc 13.3.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 12 ms / 2,000 ms
• コード長: 48,947 bytes
• コンパイル時間: 1,905 ms
• コンパイル使用メモリ: 243,432 KB
• 実行使用メモリ: 7,848 KB
• 最終ジャッジ日時: 2025-12-14 20:02:56
• 合計ジャッジ時間: 3,054 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
sample	AC * 4
other	AC * 22

コンパイルメッセージ

main.cpp: In function ‘int main()’:
main.cpp:31:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   31 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~

ソースコード

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
const int N = 2000010, MOD = 998244353, INF = 0x3f3f3f3f;
int n, m, w[N];

const pii fac[] = { {0, 1}, {1000000, 373341033}, {2000000, 45596018}, {3000000, 834980587}, {4000000, 623627864}, {5000000, 428937595}, {6000000, 442819817}, {7000000, 499710224}, {8000000, 833655840}, {9000000, 83857087}, {10000000, 295201906}, {11000000, 788488293}, {12000000, 671639287}, {13000000, 849315549}, {14000000, 597398273}, {15000000, 813259672}, {16000000, 732727656}, {17000000, 244038325}, {18000000, 122642896}, {19000000, 310517972}, {20000000, 160030060}, {21000000, 483239722}, {22000000, 683879839}, {23000000, 712910418}, {24000000, 384710263}, {25000000, 433880730}, {26000000, 844360005}, {27000000, 513089677}, {28000000, 101492974}, {29000000, 959253371}, {30000000, 957629942}, {31000000, 678615452}, {32000000, 34035221}, {33000000, 56734233}, {34000000, 524027922}, {35000000, 31729117}, {36000000, 102311167}, {37000000, 330331487}, {38000000, 8332991}, {39000000, 832392662}, {40000000, 545208507}, {41000000, 594075875}, {42000000, 318497156}, {43000000, 859275605}, {44000000, 300738984}, {45000000, 767818091}, {46000000, 864118508}, {47000000, 878131539}, {48000000, 316588744}, {49000000, 812496962}, {50000000, 213689172}, {51000000, 584871249}, {52000000, 980836133}, {53000000, 54096741}, {54000000, 417876813}, {55000000, 363266670}, {56000000, 335481797}, {57000000, 730839588}, {58000000, 393495668}, {59000000, 435793297}, {60000000, 760025067}, {61000000, 811438469}, {62000000, 720976283}, {63000000, 650770098}, {64000000, 586537547}, {65000000, 117371703}, {66000000, 566486504}, {67000000, 749562308}, {68000000, 708205284}, {69000000, 932912293}, {70000000, 939830261}, {71000000, 983699513}, {72000000, 206579820}, {73000000, 301188781}, {74000000, 593164676}, {75000000, 770845925}, {76000000, 247687458}, {77000000, 41047791}, {78000000, 266419267}, {79000000, 937835947}, {80000000, 506268060}, {81000000, 6177705}, {82000000, 936268003}, {83000000, 166873118}, {84000000, 443834893}, {85000000, 328979964}, {86000000, 470135404}, {87000000, 954410105}, {88000000, 117565665}, {89000000, 832761782}, {90000000, 39806322}, {91000000, 478922755}, {92000000, 394880724}, {93000000, 821825588}, {94000000, 468705875}, {95000000, 512554988}, {96000000, 232240472}, {97000000, 876497899}, {98000000, 356048018}, {99000000, 895187265}, {100000000, 808258749}, {101000000, 575505950}, {102000000, 68190615}, {103000000, 939065335}, {104000000, 552199946}, {105000000, 694814243}, {106000000, 385460530}, {107000000, 529769387}, {108000000, 640377761}, {109000000, 916128300}, {110000000, 440133909}, {111000000, 362216114}, {112000000, 826373774}, {113000000, 502324157}, {114000000, 457648395}, {115000000, 385510728}, {116000000, 904737188}, {117000000, 78988746}, {118000000, 454565719}, {119000000, 623828097}, {120000000, 686156489}, {121000000, 713476044}, {122000000, 63602402}, {123000000, 570334625}, {124000000, 681055904}, {125000000, 222059821}, {126000000, 477211096}, {127000000, 343363294}, {128000000, 833792655}, {129000000, 461853093}, {130000000, 741797144}, {131000000, 74731896}, {132000000, 930484262}, {133000000, 268372735}, {134000000, 941222802}, {135000000, 677432735}, {136000000, 474842829}, {137000000, 700451655}, {138000000, 400176109}, {139000000, 697644778}, {140000000, 390377694}, {141000000, 790010794}, {142000000, 360642718}, {143000000, 505712943}, {144000000, 946647976}, {145000000, 339045014}, {146000000, 715797300}, {147000000, 251680896}, {148000000, 70091750}, {149000000, 40517433}, {150000000, 12629586}, {151000000, 850635539}, {152000000, 110877109}, {153000000, 571935891}, {154000000, 695965747}, {155000000, 634938288}, {156000000, 69072133}, {157000000, 155093216}, {158000000, 749696762}, {159000000, 963086402}, {160000000, 544711799}, {161000000, 724471925}, {162000000, 334646013}, {163000000, 574791029}, {164000000, 722417626}, {165000000, 377929821}, {166000000, 743946412}, {167000000, 988034679}, {168000000, 405207112}, {169000000, 18063742}, {170000000, 104121967}, {171000000, 638607426}, {172000000, 607304611}, {173000000, 751377777}, {174000000, 35834555}, {175000000, 313632531}, {176000000, 18058363}, {177000000, 656121134}, {178000000, 40763559}, {179000000, 562910912}, {180000000, 495867250}, {181000000, 48767038}, {182000000, 210864657}, {183000000, 659137294}, {184000000, 715390025}, {185000000, 865854329}, {186000000, 324322857}, {187000000, 388911184}, {188000000, 286059202}, {189000000, 636456178}, {190000000, 421290700}, {191000000, 832276048}, {192000000, 726437551}, {193000000, 526417714}, {194000000, 252522639}, {195000000, 386147469}, {196000000, 674313019}, {197000000, 274769381}, {198000000, 226519400}, {199000000, 272047186}, {200000000, 117153405}, {201000000, 712896591}, {202000000, 486826649}, {203000000, 119444874}, {204000000, 338909703}, {205000000, 18536028}, {206000000, 41814114}, {207000000, 245606459}, {208000000, 140617938}, {209000000, 250512392}, {210000000, 57084755}, {211000000, 157807456}, {212000000, 261113192}, {213000000, 40258068}, {214000000, 194807105}, {215000000, 325341339}, {216000000, 884328111}, {217000000, 896332013}, {218000000, 880836012}, {219000000, 737358206}, {220000000, 202713771}, {221000000, 785454372}, {222000000, 399586250}, {223000000, 485457499}, {224000000, 640827004}, {225000000, 546969497}, {226000000, 749602473}, {227000000, 159788463}, {228000000, 159111724}, {229000000, 218592929}, {230000000, 675932866}, {231000000, 314795475}, {232000000, 811539323}, {233000000, 246883213}, {234000000, 696818315}, {235000000, 759880589}, {236000000, 4302336}, {237000000, 353070689}, {238000000, 477909706}, {239000000, 559289160}, {240000000, 79781699}, {241000000, 878094972}, {242000000, 840903973}, {243000000, 367416824}, {244000000, 973366814}, {245000000, 848259019}, {246000000, 462421750}, {247000000, 667227759}, {248000000, 897917455}, {249000000, 81800722}, {250000000, 956276337}, {251000000, 942686845}, {252000000, 420541799}, {253000000, 417005912}, {254000000, 272641764}, {255000000, 941778993}, {256000000, 217214373}, {257000000, 192220616}, {258000000, 267901132}, {259000000, 50530621}, {260000000, 652678397}, {261000000, 354880856}, {262000000, 164289049}, {263000000, 781023184}, {264000000, 105376215}, {265000000, 315094878}, {266000000, 607856504}, {267000000, 733905911}, {268000000, 457743498}, {269000000, 992735713}, {270000000, 35212756}, {271000000, 231822660}, {272000000, 276036750}, {273000000, 734558079}, {274000000, 424180850}, {275000000, 433186147}, {276000000, 308380947}, {277000000, 18333316}, {278000000, 12935086}, {279000000, 351491725}, {280000000, 655645460}, {281000000, 535812389}, {282000000, 521902115}, {283000000, 67016984}, {284000000, 48682076}, {285000000, 64748124}, {286000000, 489360447}, {287000000, 361275315}, {288000000, 786336279}, {289000000, 805161272}, {290000000, 468129309}, {291000000, 645091350}, {292000000, 887284732}, {293000000, 913004502}, {294000000, 358814684}, {295000000, 281295633}, {296000000, 328970139}, {297000000, 395955130}, {298000000, 164840186}, {299000000, 820902807}, {300000000, 761699708}, {301000000, 246274415}, {302000000, 592331769}, {303000000, 913846362}, {304000000, 866682684}, {305000000, 600130702}, {306000000, 903837674}, {307000000, 529462989}, {308000000, 90612675}, {309000000, 526540127}, {310000000, 533047427}, {311000000, 110008879}, {312000000, 674279751}, {313000000, 801920753}, {314000000, 645226926}, {315000000, 676886948}, {316000000, 752481486}, {317000000, 474034007}, {318000000, 457790341}, {319000000, 166813684}, {320000000, 287671032}, {321000000, 188118664}, {322000000, 244731384}, {323000000, 404032157}, {324000000, 269766986}, {325000000, 423996017}, {326000000, 182948540}, {327000000, 356801634}, {328000000, 737863144}, {329000000, 652014069}, {330000000, 206068022}, {331000000, 504569410}, {332000000, 919894484}, {333000000, 593398649}, {334000000, 963768176}, {335000000, 882517476}, {336000000, 702523597}, {337000000, 949028249}, {338000000, 128957299}, {339000000, 171997372}, {340000000, 50865043}, {341000000, 20937461}, {342000000, 690959202}, {343000000, 581356488}, {344000000, 369182214}, {345000000, 993580422}, {346000000, 193500140}, {347000000, 540665426}, {348000000, 365786018}, {349000000, 743731625}, {350000000, 144980423}, {351000000, 979536721}, {352000000, 773259009}, {353000000, 617053935}, {354000000, 247670131}, {355000000, 843705280}, {356000000, 30419459}, {357000000, 985463402}, {358000000, 261585206}, {359000000, 237885042}, {360000000, 111276893}, {361000000, 488166208}, {362000000, 137660292}, {363000000, 720784236}, {364000000, 244467770}, {365000000, 26368504}, {366000000, 792857103}, {367000000, 666885724}, {368000000, 670313309}, {369000000, 905683034}, {370000000, 259415897}, {371000000, 512017253}, {372000000, 826265493}, {373000000, 111960112}, {374000000, 633652060}, {375000000, 918048438}, {376000000, 516432938}, {377000000, 386972415}, {378000000, 996212724}, {379000000, 610073831}, {380000000, 444094191}, {381000000, 72480267}, {382000000, 665038087}, {383000000, 11584804}, {384000000, 301029012}, {385000000, 723617861}, {386000000, 113763819}, {387000000, 778259899}, {388000000, 937766095}, {389000000, 535448641}, {390000000, 593907889}, {391000000, 783573565}, {392000000, 673298635}, {393000000, 599533244}, {394000000, 655712590}, {395000000, 173350007}, {396000000, 868198597}, {397000000, 169013813}, {398000000, 585161712}, {399000000, 697502214}, {400000000, 573994984}, {401000000, 285943986}, {402000000, 675831407}, {403000000, 3134056}, {404000000, 965907646}, {405000000, 401920943}, {406000000, 665949756}, {407000000, 236277883}, {408000000, 612745912}, {409000000, 813282113}, {410000000, 892454686}, {411000000, 901222267}, {412000000, 624900982}, {413000000, 927122298}, {414000000, 686321335}, {415000000, 84924870}, {416000000, 927606072}, {417000000, 506664166}, {418000000, 353631992}, {419000000, 165913238}, {420000000, 566073550}, {421000000, 816674343}, {422000000, 864877926}, {423000000, 171259407}, {424000000, 908752311}, {425000000, 874007723}, {426000000, 803597299}, {427000000, 613676466}, {428000000, 880336545}, {429000000, 282280109}, {430000000, 128761001}, {431000000, 58852065}, {432000000, 474075900}, {433000000, 434816091}, {434000000, 364856903}, {435000000, 149123648}, {436000000, 388854780}, {437000000, 314693916}, {438000000, 423183826}, {439000000, 419733481}, {440000000, 888483202}, {441000000, 238933227}, {442000000, 336564048}, {443000000, 757103493}, {444000000, 100189123}, {445000000, 855479832}, {446000000, 51370348}, {447000000, 403061033}, {448000000, 496971759}, {449000000, 831753030}, {450000000, 251718753}, {451000000, 272779384}, {452000000, 683379259}, {453000000, 488844621}, {454000000, 881783783}, {455000000, 659478190}, {456000000, 445719559}, {457000000, 740782647}, {458000000, 546525906}, {459000000, 985524427}, {460000000, 548033568}, {461000000, 333772553}, {462000000, 331916427}, {463000000, 752533273}, {464000000, 730387628}, {465000000, 93829695}, {466000000, 655989476}, {467000000, 930661318}, {468000000, 334885743}, {469000000, 466041862}, {470000000, 428105027}, {471000000, 888238707}, {472000000, 232218076}, {473000000, 769865249}, {474000000, 730641039}, {475000000, 616996159}, {476000000, 231721356}, {477000000, 326973501}, {478000000, 426068899}, {479000000, 722403656}, {480000000, 742756734}, {481000000, 663270261}, {482000000, 364187931}, {483000000, 350431704}, {484000000, 671823672}, {485000000, 633125919}, {486000000, 226166717}, {487000000, 386814657}, {488000000, 237594135}, {489000000, 451479365}, {490000000, 546182474}, {491000000, 119366536}, {492000000, 465211069}, {493000000, 605313606}, {494000000, 728508871}, {495000000, 249619035}, {496000000, 663053607}, {497000000, 900453742}, {498000000, 48293872}, {499000000, 229958401}, {500000000, 62402409}, {501000000, 69570431}, {502000000, 71921532}, {503000000, 960467929}, {504000000, 537087913}, {505000000, 514588945}, {506000000, 513856225}, {507000000, 415497414}, {508000000, 286592050}, {509000000, 645469437}, {510000000, 102052166}, {511000000, 163298189}, {512000000, 873938719}, {513000000, 617583886}, {514000000, 986843080}, {515000000, 962390239}, {516000000, 580971332}, {517000000, 665147020}, {518000000, 88900164}, {519000000, 89866970}, {520000000, 826426395}, {521000000, 616059995}, {522000000, 443012312}, {523000000, 659160562}, {524000000, 229855967}, {525000000, 687413213}, {526000000, 59809521}, {527000000, 398599610}, {528000000, 325666688}, {529000000, 154765991}, {530000000, 159186619}, {531000000, 210830877}, {532000000, 386454418}, {533000000, 84493735}, {534000000, 974220646}, {535000000, 820097297}, {536000000, 2191828}, {537000000, 481459931}, {538000000, 729073424}, {539000000, 551556379}, {540000000, 926316039}, {541000000, 151357011}, {542000000, 808637654}, {543000000, 218058015}, {544000000, 786112034}, {545000000, 850407126}, {546000000, 84202800}, {547000000, 94214098}, {548000000, 30019651}, {549000000, 121701603}, {550000000, 176055335}, {551000000, 865461951}, {552000000, 553631971}, {553000000, 286620803}, {554000000, 984061713}, {555000000, 888573766}, {556000000, 302767023}, {557000000, 977070668}, {558000000, 110954576}, {559000000, 83922475}, {560000000, 51568171}, {561000000, 60949367}, {562000000, 19533020}, {563000000, 510592752}, {564000000, 615419476}, {565000000, 341370469}, {566000000, 912573425}, {567000000, 286207526}, {568000000, 206707897}, {569000000, 384156962}, {570000000, 414163604}, {571000000, 193301813}, {572000000, 749570167}, {573000000, 366933789}, {574000000, 11470970}, {575000000, 600191572}, {576000000, 391667731}, {577000000, 328736286}, {578000000, 30645366}, {579000000, 215162519}, {580000000, 604947226}, {581000000, 236199953}, {582000000, 718439098}, {583000000, 411423177}, {584000000, 803407599}, {585000000, 632441623}, {586000000, 766760224}, {587000000, 263006576}, {588000000, 757681534}, {589000000, 61082578}, {590000000, 681666415}, {591000000, 947466395}, {592000000, 12206799}, {593000000, 659767098}, {594000000, 933746852}, {595000000, 978860867}, {596000000, 59215985}, {597000000, 161179205}, {598000000, 439197472}, {599000000, 259779111}, {600000000, 511621808}, {601000000, 145770512}, {602000000, 882749888}, {603000000, 943124465}, {604000000, 872053396}, {605000000, 631078482}, {606000000, 166861622}, {607000000, 743415395}, {608000000, 772287179}, {609000000, 602427948}, {610000000, 924112080}, {611000000, 385643091}, {612000000, 794973480}, {613000000, 883782693}, {614000000, 869723371}, {615000000, 805963889}, {616000000, 313106351}, {617000000, 262132854}, {618000000, 400034567}, {619000000, 488248149}, {620000000, 265769800}, {621000000, 791715397}, {622000000, 408753255}, {623000000, 468381897}, {624000000, 415812467}, {625000000, 172922144}, {626000000, 64404368}, {627000000, 281500398}, {628000000, 512318142}, {629000000, 288791777}, {630000000, 955559118}, {631000000, 242484726}, {632000000, 536413695}, {633000000, 205340854}, {634000000, 707803527}, {635000000, 576699812}, {636000000, 218525078}, {637000000, 875554190}, {638000000, 46283078}, {639000000, 833841915}, {640000000, 763148293}, {641000000, 807722138}, {642000000, 788080170}, {643000000, 556901372}, {644000000, 150896699}, {645000000, 253151120}, {646000000, 97856807}, {647000000, 918256774}, {648000000, 771557187}, {649000000, 582547026}, {650000000, 472709375}, {651000000, 911615063}, {652000000, 743371401}, {653000000, 641382840}, {654000000, 446540967}, {655000000, 184639537}, {656000000, 157247760}, {657000000, 775930891}, {658000000, 939702814}, {659000000, 499082462}, {660000000, 19536133}, {661000000, 548753627}, {662000000, 593243221}, {663000000, 563850263}, {664000000, 185475971}, {665000000, 687419227}, {666000000, 396799323}, {667000000, 657976136}, {668000000, 864535682}, {669000000, 433009242}, {670000000, 860830935}, {671000000, 33107339}, {672000000, 517661450}, {673000000, 467651311}, {674000000, 812398757}, {675000000, 202133852}, {676000000, 431839017}, {677000000, 709549400}, {678000000, 99643620}, {679000000, 773282878}, {680000000, 290471030}, {681000000, 61134552}, {682000000, 129206504}, {683000000, 929147251}, {684000000, 837008968}, {685000000, 422332597}, {686000000, 353775281}, {687000000, 469563025}, {688000000, 62265336}, {689000000, 835064501}, {690000000, 851685235}, {691000000, 21197005}, {692000000, 264793769}, {693000000, 326416680}, {694000000, 118842991}, {695000000, 84257200}, {696000000, 763248924}, {697000000, 687559609}, {698000000, 150907932}, {699000000, 401832452}, {700000000, 242726978}, {701000000, 766752066}, {702000000, 959173604}, {703000000, 390269102}, {704000000, 992293822}, {705000000, 744816299}, {706000000, 476631694}, {707000000, 177284763}, {708000000, 702429415}, {709000000, 374065901}, {710000000, 169855231}, {711000000, 629007616}, {712000000, 719169602}, {713000000, 564737074}, {714000000, 475119050}, {715000000, 714502830}, {716000000, 40993711}, {717000000, 820235888}, {718000000, 749063595}, {719000000, 239329111}, {720000000, 612759169}, {721000000, 18591377}, {722000000, 419142436}, {723000000, 442202439}, {724000000, 941600951}, {725000000, 158013406}, {726000000, 637073231}, {727000000, 471564060}, {728000000, 447222237}, {729000000, 701248503}, {730000000, 599797734}, {731000000, 577221870}, {732000000, 69656699}, {733000000, 51052704}, {734000000, 6544303}, {735000000, 10958310}, {736000000, 554955500}, {737000000, 943192237}, {738000000, 192526269}, {739000000, 897983911}, {740000000, 961628039}, {741000000, 240232720}, {742000000, 627280533}, {743000000, 710239542}, {744000000, 70255649}, {745000000, 261743865}, {746000000, 228474833}, {747000000, 776408079}, {748000000, 304180483}, {749000000, 63607040}, {750000000, 953297493}, {751000000, 758058902}, {752000000, 395529997}, {753000000, 156010331}, {754000000, 825833840}, {755000000, 539880795}, {756000000, 234683685}, {757000000, 52626619}, {758000000, 751843490}, {759000000, 116909119}, {760000000, 62806842}, {761000000, 574857555}, {762000000, 353417551}, {763000000, 40061330}, {764000000, 822203768}, {765000000, 681051568}, {766000000, 490913702}, {767000000, 9322961}, {768000000, 766631257}, {769000000, 124794668}, {770000000, 37844313}, {771000000, 163524507}, {772000000, 729108319}, {773000000, 490867505}, {774000000, 47035168}, {775000000, 682765157}, {776000000, 53842115}, {777000000, 817965276}, {778000000, 757179922}, {779000000, 339238384}, {780000000, 909741023}, {781000000, 150530547}, {782000000, 158444563}, {783000000, 140949492}, {784000000, 993302799}, {785000000, 551621442}, {786000000, 137578883}, {787000000, 475122706}, {788000000, 443869843}, {789000000, 605400098}, {790000000, 689361523}, {791000000, 769596520}, {792000000, 801661499}, {793000000, 474900284}, {794000000, 586624857}, {795000000, 349960501}, {796000000, 134084537}, {797000000, 650564083}, {798000000, 877097974}, {799000000, 379857427}, {800000000, 887890124}, {801000000, 159436401}, {802000000, 133274277}, {803000000, 986182139}, {804000000, 729720334}, {805000000, 568925901}, {806000000, 459461496}, {807000000, 499309445}, {808000000, 493171177}, {809000000, 460958750}, {810000000, 380694152}, {811000000, 168836226}, {812000000, 840160881}, {813000000, 141116880}, {814000000, 225064950}, {815000000, 109618190}, {816000000, 842341383}, {817000000, 85305729}, {818000000, 759273275}, {819000000, 97369807}, {820000000, 669317759}, {821000000, 766247510}, {822000000, 829017039}, {823000000, 550323884}, {824000000, 261274540}, {825000000, 918239352}, {826000000, 29606025}, {827000000, 870793828}, {828000000, 293683814}, {829000000, 378510746}, {830000000, 367270918}, {831000000, 481292028}, {832000000, 813097823}, {833000000, 798448487}, {834000000, 230791733}, {835000000, 899305835}, {836000000, 504040630}, {837000000, 162510533}, {838000000, 479367951}, {839000000, 275282274}, {840000000, 806951470}, {841000000, 462774647}, {842000000, 56473153}, {843000000, 184659008}, {844000000, 905122161}, {845000000, 664034750}, {846000000, 109726629}, {847000000, 59372704}, {848000000, 325795100}, {849000000, 486860143}, {850000000, 843736533}, {851000000, 924723613}, {852000000, 880348000}, {853000000, 801252478}, {854000000, 616515290}, {855000000, 776142608}, {856000000, 284803450}, {857000000, 583439582}, {858000000, 274826676}, {859000000, 6018349}, {860000000, 377403437}, {861000000, 244041569}, {862000000, 527081707}, {863000000, 544763288}, {864000000, 708818585}, {865000000, 354033051}, {866000000, 904309832}, {867000000, 589922898}, {868000000, 673933870}, {869000000, 682858433}, {870000000, 945260111}, {871000000, 899893421}, {872000000, 515264973}, {873000000, 911685911}, {874000000, 9527148}, {875000000, 239480646}, {876000000, 524126897}, {877000000, 48259065}, {878000000, 578214879}, {879000000, 118677219}, {880000000, 786127243}, {881000000, 869205770}, {882000000, 923276513}, {883000000, 937928886}, {884000000, 802186160}, {885000000, 12198440}, {886000000, 638784295}, {887000000, 34200904}, {888000000, 758925811}, {889000000, 185027790}, {890000000, 80918046}, {891000000, 120604699}, {892000000, 610456697}, {893000000, 573601211}, {894000000, 208296321}, {895000000, 49743354}, {896000000, 653691911}, {897000000, 490750754}, {898000000, 674335312}, {899000000, 887877110}, {900000000, 875880304}, {901000000, 308360096}, {902000000, 414636410}, {903000000, 886100267}, {904000000, 8525751}, {905000000, 636257427}, {906000000, 558338775}, {907000000, 500159951}, {908000000, 696213291}, {909000000, 97268896}, {910000000, 364983542}, {911000000, 937928436}, {912000000, 641582714}, {913000000, 586211304}, {914000000, 345265657}, {915000000, 994704486}, {916000000, 443549763}, {917000000, 207259440}, {918000000, 302122082}, {919000000, 166055224}, {920000000, 623250998}, {921000000, 239642551}, {922000000, 476337075}, {923000000, 283167364}, {924000000, 211328914}, {925000000, 68064804}, {926000000, 950202136}, {927000000, 187552679}, {928000000, 18938709}, {929000000, 646784245}, {930000000, 598764068}, {931000000, 538505481}, {932000000, 610424991}, {933000000, 864445053}, {934000000, 390248689}, {935000000, 278395191}, {936000000, 686098470}, {937000000, 935957187}, {938000000, 868529577}, {939000000, 329970687}, {940000000, 804930040}, {941000000, 84992079}, {942000000, 474569269}, {943000000, 810762228}, {944000000, 573258936}, {945000000, 756464212}, {946000000, 155080225}, {947000000, 286966169}, {948000000, 283614605}, {949000000, 19283401}, {950000000, 24257676}, {951000000, 871831819}, {952000000, 612689791}, {953000000, 846988741}, {954000000, 617120754}, {955000000, 971716517}, {956000000, 979541482}, {957000000, 297910784}, {958000000, 991087897}, {959000000, 783825907}, {960000000, 214821357}, {961000000, 689498189}, {962000000, 405026419}, {963000000, 946731704}, {964000000, 609346370}, {965000000, 707669156}, {966000000, 457703127}, {967000000, 957341187}, {968000000, 980735523}, {969000000, 649367684}, {970000000, 791011898}, {971000000, 82098966}, {972000000, 234729712}, {973000000, 105002711}, {974000000, 130614285}, {975000000, 291032164}, {976000000, 193188049}, {977000000, 363211260}, {978000000, 58108651}, {979000000, 100756444}, {980000000, 954947696}, {981000000, 346032213}, {982000000, 863300806}, {983000000, 36876722}, {984000000, 622610957}, {985000000, 289232396}, {986000000, 667938985}, {987000000, 734886266}, {988000000, 395881057}, {989000000, 417188702}, {990000000, 183092975}, {991000000, 887586469}, {992000000, 83334648}, {993000000, 797819763}, {994000000, 100176902}, {995000000, 781587414}, {996000000, 841864935}, {997000000, 371674670}, {998000000, 18247584}, {999000000, 0}, {1000000000, 0} };
const pii inv[] = { {0, 1}, {1000000, 490058372}, {2000000, 51625059}, {3000000, 695462981}, {4000000, 728187357}, {5000000, 310402238}, {6000000, 477429414}, {7000000, 342092605}, {8000000, 830693344}, {9000000, 921885471}, {10000000, 759799589}, {11000000, 450923463}, {12000000, 61251247}, {13000000, 457998033}, {14000000, 209179915}, {15000000, 671789491}, {16000000, 398879408}, {17000000, 862658278}, {18000000, 602923260}, {19000000, 311915383}, {20000000, 867498551}, {21000000, 623622051}, {22000000, 650441514}, {23000000, 236862811}, {24000000, 618741947}, {25000000, 166075741}, {26000000, 548822955}, {27000000, 30594482}, {28000000, 504195635}, {29000000, 614532293}, {30000000, 554082439}, {31000000, 289558849}, {32000000, 538046429}, {33000000, 877167104}, {34000000, 693380715}, {35000000, 560352203}, {36000000, 84403822}, {37000000, 20104390}, {38000000, 441132239}, {39000000, 743705033}, {40000000, 935077313}, {41000000, 739477278}, {42000000, 359392423}, {43000000, 800213193}, {44000000, 198957241}, {45000000, 740332423}, {46000000, 733997151}, {47000000, 916566167}, {48000000, 967904538}, {49000000, 209257758}, {50000000, 190826693}, {51000000, 936781731}, {52000000, 905696722}, {53000000, 226555701}, {54000000, 260941903}, {55000000, 449608418}, {56000000, 859615378}, {57000000, 246920569}, {58000000, 982880909}, {59000000, 178336254}, {60000000, 797071813}, {61000000, 244544021}, {62000000, 206353262}, {63000000, 836764978}, {64000000, 284284558}, {65000000, 582618058}, {66000000, 933673725}, {67000000, 928466077}, {68000000, 644453789}, {69000000, 64003842}, {70000000, 561288278}, {71000000, 263235848}, {72000000, 278199525}, {73000000, 67453668}, {74000000, 805881946}, {75000000, 627190275}, {76000000, 386525071}, {77000000, 126412649}, {78000000, 48822620}, {79000000, 319395907}, {80000000, 574600270}, {81000000, 326842553}, {82000000, 543035789}, {83000000, 442691886}, {84000000, 911743593}, {85000000, 224258052}, {86000000, 855495771}, {87000000, 692675205}, {88000000, 729378868}, {89000000, 218462105}, {90000000, 319060424}, {91000000, 483766453}, {92000000, 940595774}, {93000000, 189520139}, {94000000, 107935512}, {95000000, 128380276}, {96000000, 976429470}, {97000000, 192458155}, {98000000, 451933029}, {99000000, 266899928}, {100000000, 178367884}, {101000000, 882150833}, {102000000, 805051089}, {103000000, 633668957}, {104000000, 380401293}, {105000000, 974084029}, {106000000, 25083679}, {107000000, 279109331}, {108000000, 45916545}, {109000000, 595825577}, {110000000, 780342347}, {111000000, 381594760}, {112000000, 103440970}, {113000000, 439051085}, {114000000, 928254970}, {115000000, 348364645}, {116000000, 617538401}, {117000000, 351012488}, {118000000, 336956144}, {119000000, 640286060}, {120000000, 918748953}, {121000000, 165372833}, {122000000, 558174544}, {123000000, 488153918}, {124000000, 552980873}, {125000000, 583866018}, {126000000, 852182893}, {127000000, 74766398}, {128000000, 412908687}, {129000000, 462616893}, {130000000, 716049421}, {131000000, 542834726}, {132000000, 902008482}, {133000000, 908654976}, {134000000, 480288057}, {135000000, 130494106}, {136000000, 638777488}, {137000000, 327658121}, {138000000, 320813675}, {139000000, 846447044}, {140000000, 372477309}, {141000000, 93060100}, {142000000, 386043722}, {143000000, 768867815}, {144000000, 282491685}, {145000000, 481147696}, {146000000, 457008508}, {147000000, 144769154}, {148000000, 109310411}, {149000000, 622684903}, {150000000, 926009008}, {151000000, 855421273}, {152000000, 962189011}, {153000000, 659337524}, {154000000, 440817225}, {155000000, 877567135}, {156000000, 981271110}, {157000000, 303318898}, {158000000, 638530432}, {159000000, 746784183}, {160000000, 970706036}, {161000000, 180961719}, {162000000, 364026354}, {163000000, 211562221}, {164000000, 360848035}, {165000000, 638624725}, {166000000, 204567479}, {167000000, 426966849}, {168000000, 15719242}, {169000000, 230020082}, {170000000, 46268720}, {171000000, 696426924}, {172000000, 949147901}, {173000000, 556011519}, {174000000, 697879051}, {175000000, 120927051}, {176000000, 243531237}, {177000000, 856355807}, {178000000, 721732549}, {179000000, 455339902}, {180000000, 291844170}, {181000000, 452925772}, {182000000, 532234348}, {183000000, 281866315}, {184000000, 548615073}, {185000000, 596015915}, {186000000, 105121890}, {187000000, 308552771}, {188000000, 78148056}, {189000000, 701617901}, {190000000, 621032546}, {191000000, 435163180}, {192000000, 283193532}, {193000000, 311192590}, {194000000, 554300776}, {195000000, 577196227}, {196000000, 98392753}, {197000000, 448899853}, {198000000, 836559289}, {199000000, 21004038}, {200000000, 365971928}, {201000000, 257634636}, {202000000, 686753882}, {203000000, 360118662}, {204000000, 353803260}, {205000000, 917869163}, {206000000, 886329157}, {207000000, 818495374}, {208000000, 677375709}, {209000000, 101159856}, {210000000, 20133513}, {211000000, 787903223}, {212000000, 290729943}, {213000000, 232494258}, {214000000, 742341694}, {215000000, 374788769}, {216000000, 899058030}, {217000000, 853081907}, {218000000, 388195490}, {219000000, 285890477}, {220000000, 738809835}, {221000000, 925026339}, {222000000, 242850738}, {223000000, 468204234}, {224000000, 811533162}, {225000000, 948348044}, {226000000, 961393970}, {227000000, 744757868}, {228000000, 426234283}, {229000000, 520204343}, {230000000, 190257326}, {231000000, 836409614}, {232000000, 708530994}, {233000000, 592893905}, {234000000, 510294871}, {235000000, 909475234}, {236000000, 169046741}, {237000000, 127981018}, {238000000, 806398157}, {239000000, 885348248}, {240000000, 877196715}, {241000000, 294816833}, {242000000, 816555672}, {243000000, 991103573}, {244000000, 739199557}, {245000000, 859944460}, {246000000, 186542420}, {247000000, 337349517}, {248000000, 980845798}, {249000000, 682490089}, {250000000, 761319181}, {251000000, 413444587}, {252000000, 965722990}, {253000000, 828337125}, {254000000, 799980361}, {255000000, 820611505}, {256000000, 388455773}, {257000000, 15526898}, {258000000, 76403843}, {259000000, 178856283}, {260000000, 552775398}, {261000000, 12006827}, {262000000, 718062902}, {263000000, 376166999}, {264000000, 352451202}, {265000000, 915700473}, {266000000, 436315792}, {267000000, 409030036}, {268000000, 608551894}, {269000000, 198541470}, {270000000, 159336557}, {271000000, 515714894}, {272000000, 306311664}, {273000000, 260982554}, {274000000, 777573284}, {275000000, 61484435}, {276000000, 803320773}, {277000000, 333982693}, {278000000, 210584941}, {279000000, 964725509}, {280000000, 326545967}, {281000000, 702793569}, {282000000, 969435285}, {283000000, 317648543}, {284000000, 963711226}, {285000000, 608571548}, {286000000, 754232497}, {287000000, 273199735}, {288000000, 252073094}, {289000000, 978390087}, {290000000, 248000896}, {291000000, 916145481}, {292000000, 670398772}, {293000000, 261751428}, {294000000, 393363965}, {295000000, 17094531}, {296000000, 639442533}, {297000000, 888009888}, {298000000, 454721730}, {299000000, 960828782}, {300000000, 691050464}, {301000000, 325020674}, {302000000, 308150581}, {303000000, 325978338}, {304000000, 337064152}, {305000000, 238322632}, {306000000, 961953093}, {307000000, 482735870}, {308000000, 786902928}, {309000000, 826018256}, {310000000, 108831724}, {311000000, 727717050}, {312000000, 403268027}, {313000000, 213178703}, {314000000, 258222569}, {315000000, 511191443}, {316000000, 475167843}, {317000000, 192218693}, {318000000, 224503614}, {319000000, 975555803}, {320000000, 266913096}, {321000000, 103655767}, {322000000, 374319549}, {323000000, 156105717}, {324000000, 221014461}, {325000000, 714595462}, {326000000, 613830633}, {327000000, 701216391}, {328000000, 983404583}, {329000000, 151603819}, {330000000, 254038565}, {331000000, 340379036}, {332000000, 469472556}, {333000000, 673342894}, {334000000, 847735786}, {335000000, 849952908}, {336000000, 684139911}, {337000000, 868154197}, {338000000, 68290362}, {339000000, 880423759}, {340000000, 683343831}, {341000000, 533142765}, {342000000, 309309258}, {343000000, 860574373}, {344000000, 328482367}, {345000000, 953839587}, {346000000, 980900311}, {347000000, 895403335}, {348000000, 43844647}, {349000000, 409722130}, {350000000, 586709838}, {351000000, 28125613}, {352000000, 328686686}, {353000000, 13046452}, {354000000, 533100799}, {355000000, 283750812}, {356000000, 551232164}, {357000000, 289846018}, {358000000, 318545130}, {359000000, 66892473}, {360000000, 858843854}, {361000000, 780618987}, {362000000, 373829832}, {363000000, 482254216}, {364000000, 809891451}, {365000000, 588938033}, {366000000, 106000870}, {367000000, 702596616}, {368000000, 387209685}, {369000000, 785353757}, {370000000, 773279646}, {371000000, 446385635}, {372000000, 116210837}, {373000000, 82537134}, {374000000, 73158530}, {375000000, 717980033}, {376000000, 228951774}, {377000000, 295432936}, {378000000, 843877865}, {379000000, 554722242}, {380000000, 722009235}, {381000000, 365148272}, {382000000, 964835783}, {383000000, 816359259}, {384000000, 64947036}, {385000000, 377775169}, {386000000, 456435128}, {387000000, 728467109}, {388000000, 561713174}, {389000000, 398882884}, {390000000, 990779119}, {391000000, 275009804}, {392000000, 911302858}, {393000000, 553052490}, {394000000, 190147105}, {395000000, 303284848}, {396000000, 694477833}, {397000000, 24736139}, {398000000, 193791653}, {399000000, 478462763}, {400000000, 719646401}, {401000000, 452866369}, {402000000, 118292293}, {403000000, 498638989}, {404000000, 980549025}, {405000000, 905007131}, {406000000, 844103519}, {407000000, 794625886}, {408000000, 993432441}, {409000000, 981862987}, {410000000, 252907357}, {411000000, 197267147}, {412000000, 727893838}, {413000000, 977006125}, {414000000, 763846452}, {415000000, 899304792}, {416000000, 129010197}, {417000000, 749508965}, {418000000, 577769565}, {419000000, 323987639}, {420000000, 840074893}, {421000000, 753049763}, {422000000, 451220160}, {423000000, 1318910}, {424000000, 612066960}, {425000000, 451804416}, {426000000, 962233034}, {427000000, 27400581}, {428000000, 714690622}, {429000000, 949318184}, {430000000, 400450951}, {431000000, 611276049}, {432000000, 134997846}, {433000000, 320103424}, {434000000, 515722521}, {435000000, 932821526}, {436000000, 805477672}, {437000000, 283501418}, {438000000, 503093199}, {439000000, 744707409}, {440000000, 579105471}, {441000000, 502854617}, {442000000, 422921074}, {443000000, 278516703}, {444000000, 910623627}, {445000000, 510769776}, {446000000, 344598437}, {447000000, 504823930}, {448000000, 595929946}, {449000000, 262423548}, {450000000, 964822723}, {451000000, 563506349}, {452000000, 435762287}, {453000000, 6155038}, {454000000, 168561957}, {455000000, 242765348}, {456000000, 375315769}, {457000000, 992601681}, {458000000, 681857777}, {459000000, 95609685}, {460000000, 154902819}, {461000000, 678221149}, {462000000, 153992852}, {463000000, 378974878}, {464000000, 840910559}, {465000000, 830745715}, {466000000, 481520346}, {467000000, 980770795}, {468000000, 298127479}, {469000000, 380814273}, {470000000, 891531382}, {471000000, 642154067}, {472000000, 859888736}, {473000000, 125010935}, {474000000, 571661472}, {475000000, 908353551}, {476000000, 967269678}, {477000000, 839791051}, {478000000, 433938696}, {479000000, 147981701}, {480000000, 40579732}, {481000000, 896155874}, {482000000, 622670561}, {483000000, 362000204}, {484000000, 891941059}, {485000000, 595125901}, {486000000, 348465587}, {487000000, 315343432}, {488000000, 17898753}, {489000000, 119472709}, {490000000, 151344119}, {491000000, 80692857}, {492000000, 882570333}, {493000000, 626978361}, {494000000, 325096553}, {495000000, 978553977}, {496000000, 210929563}, {497000000, 438699101}, {498000000, 571483922}, {499000000, 949930679}, {500000000, 7870149}, {501000000, 690111920}, {502000000, 699633619}, {503000000, 361410951}, {504000000, 689994475}, {505000000, 705657697}, {506000000, 290675109}, {507000000, 218858662}, {508000000, 62146207}, {509000000, 970047392}, {510000000, 287152769}, {511000000, 906470410}, {512000000, 906100786}, {513000000, 718737604}, {514000000, 940580377}, {515000000, 566153345}, {516000000, 132479808}, {517000000, 237423271}, {518000000, 902232591}, {519000000, 757075326}, {520000000, 971936258}, {521000000, 728162205}, {522000000, 997665989}, {523000000, 56091694}, {524000000, 572750293}, {525000000, 467303297}, {526000000, 972215720}, {527000000, 806875121}, {528000000, 268578773}, {529000000, 459667712}, {530000000, 791990436}, {531000000, 616921781}, {532000000, 867427299}, {533000000, 112879421}, {534000000, 891536614}, {535000000, 61159489}, {536000000, 847269452}, {537000000, 508556859}, {538000000, 810809931}, {539000000, 180575374}, {540000000, 284114094}, {541000000, 472413320}, {542000000, 25287000}, {543000000, 172101475}, {544000000, 887429072}, {545000000, 871099196}, {546000000, 934837589}, {547000000, 264404334}, {548000000, 418447250}, {549000000, 113411959}, {550000000, 84016503}, {551000000, 211045931}, {552000000, 702666785}, {553000000, 538291579}, {554000000, 873163054}, {555000000, 130951582}, {556000000, 387919918}, {557000000, 694896982}, {558000000, 453038091}, {559000000, 871163851}, {560000000, 516168960}, {561000000, 553669394}, {562000000, 306733197}, {563000000, 179392959}, {564000000, 511929582}, {565000000, 376055773}, {566000000, 450574317}, {567000000, 695847087}, {568000000, 810209901}, {569000000, 112566908}, {570000000, 29678053}, {571000000, 225509547}, {572000000, 888017082}, {573000000, 924153631}, {574000000, 534969607}, {575000000, 508294852}, {576000000, 114839002}, {577000000, 875924098}, {578000000, 571609910}, {579000000, 849892550}, {580000000, 7835283}, {581000000, 450931813}, {582000000, 37462829}, {583000000, 239376007}, {584000000, 442167555}, {585000000, 26743981}, {586000000, 426391370}, {587000000, 740209479}, {588000000, 676027363}, {589000000, 589906446}, {590000000, 549295580}, {591000000, 286492808}, {592000000, 233679464}, {593000000, 62655683}, {594000000, 340373313}, {595000000, 148791638}, {596000000, 62844063}, {597000000, 123647139}, {598000000, 874184665}, {599000000, 56602566}, {600000000, 215464019}, {601000000, 642939907}, {602000000, 528218068}, {603000000, 264662227}, {604000000, 267010675}, {605000000, 50248932}, {606000000, 70351583}, {607000000, 917806381}, {608000000, 44452855}, {609000000, 930223710}, {610000000, 373591304}, {611000000, 624642473}, {612000000, 125062847}, {613000000, 616162641}, {614000000, 607098271}, {615000000, 394837152}, {616000000, 842524973}, {617000000, 31868584}, {618000000, 787749520}, {619000000, 837016639}, {620000000, 964051474}, {621000000, 911328209}, {622000000, 260210077}, {623000000, 35852185}, {624000000, 222964549}, {625000000, 934999251}, {626000000, 244591455}, {627000000, 413351072}, {628000000, 376767687}, {629000000, 965511120}, {630000000, 222563229}, {631000000, 438014774}, {632000000, 905793036}, {633000000, 651737119}, {634000000, 796783175}, {635000000, 204524003}, {636000000, 256643011}, {637000000, 907540960}, {638000000, 82137688}, {639000000, 575305307}, {640000000, 144084007}, {641000000, 888773383}, {642000000, 611376797}, {643000000, 713763738}, {644000000, 732684119}, {645000000, 441216070}, {646000000, 294199779}, {647000000, 732075300}, {648000000, 117250349}, {649000000, 501225987}, {650000000, 898409719}, {651000000, 447553808}, {652000000, 903031114}, {653000000, 245437007}, {654000000, 923616720}, {655000000, 267913026}, {656000000, 599162242}, {657000000, 294903197}, {658000000, 937440354}, {659000000, 137704911}, {660000000, 167958732}, {661000000, 809803864}, {662000000, 401141309}, {663000000, 585950215}, {664000000, 776472470}, {665000000, 711295460}, {666000000, 825039032}, {667000000, 437612818}, {668000000, 880291252}, {669000000, 497116532}, {670000000, 157282384}, {671000000, 18468040}, {672000000, 267932930}, {673000000, 400300789}, {674000000, 101743180}, {675000000, 246887802}, {676000000, 733852805}, {677000000, 632928371}, {678000000, 627200499}, {679000000, 684888901}, {680000000, 540157816}, {681000000, 848440782}, {682000000, 169073306}, {683000000, 666042047}, {684000000, 146645556}, {685000000, 137317030}, {686000000, 21551615}, {687000000, 388964903}, {688000000, 981277}, {689000000, 759823628}, {690000000, 23189943}, {691000000, 561691531}, {692000000, 237107466}, {693000000, 617816304}, {694000000, 722530910}, {695000000, 251287080}, {696000000, 345554828}, {697000000, 928954558}, {698000000, 477100046}, {699000000, 207802106}, {700000000, 654268249}, {701000000, 667181430}, {702000000, 109496185}, {703000000, 531771500}, {704000000, 515961727}, {705000000, 899258462}, {706000000, 549502841}, {707000000, 7905277}, {708000000, 708458902}, {709000000, 349639016}, {710000000, 376429097}, {711000000, 8025570}, {712000000, 61297255}, {713000000, 357846483}, {714000000, 630066074}, {715000000, 176750517}, {716000000, 121928783}, {717000000, 136497070}, {718000000, 418544897}, {719000000, 856960219}, {720000000, 972619373}, {721000000, 466601983}, {722000000, 132022912}, {723000000, 247577702}, {724000000, 880005481}, {725000000, 400635519}, {726000000, 740177254}, {727000000, 929935829}, {728000000, 425886024}, {729000000, 371032333}, {730000000, 702097339}, {731000000, 665365481}, {732000000, 555087337}, {733000000, 60017392}, {734000000, 787047654}, {735000000, 871496322}, {736000000, 802785896}, {737000000, 48351339}, {738000000, 582003068}, {739000000, 762865157}, {740000000, 700338334}, {741000000, 955994296}, {742000000, 545185951}, {743000000, 525952670}, {744000000, 888810175}, {745000000, 521359198}, {746000000, 263266233}, {747000000, 145744733}, {748000000, 527375087}, {749000000, 909149025}, {750000000, 642408721}, {751000000, 965912165}, {752000000, 90983062}, {753000000, 110316459}, {754000000, 116133420}, {755000000, 731885180}, {756000000, 204280570}, {757000000, 194334660}, {758000000, 856146027}, {759000000, 594713947}, {760000000, 289165782}, {761000000, 555455456}, {762000000, 769817841}, {763000000, 904419800}, {764000000, 449562574}, {765000000, 685102727}, {766000000, 6417861}, {767000000, 303781493}, {768000000, 519214738}, {769000000, 228686843}, {770000000, 894682739}, {771000000, 976056255}, {772000000, 791815569}, {773000000, 101451723}, {774000000, 508687609}, {775000000, 619955081}, {776000000, 38004714}, {777000000, 168986862}, {778000000, 998039838}, {779000000, 540441824}, {780000000, 471917511}, {781000000, 275479910}, {782000000, 501966546}, {783000000, 208931738}, {784000000, 417068054}, {785000000, 476644817}, {786000000, 309233071}, {787000000, 453050613}, {788000000, 40280286}, {789000000, 615113716}, {790000000, 371349046}, {791000000, 11210458}, {792000000, 145882692}, {793000000, 395028540}, {794000000, 688938723}, {795000000, 675536884}, {796000000, 751373797}, {797000000, 398796779}, {798000000, 466085625}, {799000000, 371857039}, {800000000, 159945797}, {801000000, 297306569}, {802000000, 315226634}, {803000000, 474489101}, {804000000, 760937515}, {805000000, 383092791}, {806000000, 579737828}, {807000000, 78758896}, {808000000, 595100041}, {809000000, 531150839}, {810000000, 638965240}, {811000000, 587409415}, {812000000, 266132673}, {813000000, 594486210}, {814000000, 839637756}, {815000000, 710794435}, {816000000, 709925290}, {817000000, 206734984}, {818000000, 629639424}, {819000000, 342722909}, {820000000, 371546781}, {821000000, 730680168}, {822000000, 984749259}, {823000000, 788369122}, {824000000, 769506990}, {825000000, 976721117}, {826000000, 873858680}, {827000000, 333319168}, {828000000, 456137649}, {829000000, 917803800}, {830000000, 853479945}, {831000000, 399714285}, {832000000, 337710895}, {833000000, 915600716}, {834000000, 672787286}, {835000000, 761953520}, {836000000, 410277031}, {837000000, 297985294}, {838000000, 860260957}, {839000000, 506292259}, {840000000, 422554714}, {841000000, 131323782}, {842000000, 787678965}, {843000000, 907970484}, {844000000, 946416634}, {845000000, 140317749}, {846000000, 511190883}, {847000000, 900122041}, {848000000, 659028537}, {849000000, 909546856}, {850000000, 567635145}, {851000000, 455481021}, {852000000, 731290044}, {853000000, 355275716}, {854000000, 94834121}, {855000000, 720208302}, {856000000, 5055419}, {857000000, 820961492}, {858000000, 963015701}, {859000000, 768039963}, {860000000, 381456294}, {861000000, 231943378}, {862000000, 357169669}, {863000000, 823865624}, {864000000, 873150297}, {865000000, 743143683}, {866000000, 62369469}, {867000000, 116606360}, {868000000, 908808647}, {869000000, 663026711}, {870000000, 348714095}, {871000000, 517625087}, {872000000, 675162017}, {873000000, 688398894}, {874000000, 645746560}, {875000000, 234357017}, {876000000, 288350945}, {877000000, 207496907}, {878000000, 648721402}, {879000000, 434914353}, {880000000, 280762859}, {881000000, 577047457}, {882000000, 985400851}, {883000000, 186679550}, {884000000, 204613985}, {885000000, 331575958}, {886000000, 813957864}, {887000000, 1586145}, {888000000, 700435369}, {889000000, 116675312}, {890000000, 570156848}, {891000000, 814143673}, {892000000, 676241746}, {893000000, 595248480}, {894000000, 851458914}, {895000000, 116672829}, {896000000, 337241663}, {897000000, 696975079}, {898000000, 20784587}, {899000000, 498945130}, {900000000, 937680149}, {901000000, 551917357}, {902000000, 701664127}, {903000000, 936384824}, {904000000, 820990155}, {905000000, 850797027}, {906000000, 97123848}, {907000000, 672473280}, {908000000, 839859775}, {909000000, 153982966}, {910000000, 119015875}, {911000000, 140943141}, {912000000, 24273135}, {913000000, 492836885}, {914000000, 624063246}, {915000000, 259360959}, {916000000, 947023421}, {917000000, 331871451}, {918000000, 732082262}, {919000000, 139986805}, {920000000, 346852980}, {921000000, 468753850}, {922000000, 394002728}, {923000000, 376255738}, {924000000, 346748682}, {925000000, 479282495}, {926000000, 63116593}, {927000000, 525329868}, {928000000, 572086031}, {929000000, 813231396}, {930000000, 871384541}, {931000000, 929558218}, {932000000, 303200974}, {933000000, 143760749}, {934000000, 118778214}, {935000000, 444605732}, {936000000, 876229308}, {937000000, 944732864}, {938000000, 538659578}, {939000000, 992199867}, {940000000, 290776851}, {941000000, 355318036}, {942000000, 976479999}, {943000000, 60996639}, {944000000, 761042887}, {945000000, 261735677}, {946000000, 254465737}, {947000000, 388454776}, {948000000, 456716559}, {949000000, 787909277}, {950000000, 987399854}, {951000000, 386173025}, {952000000, 769038337}, {953000000, 149378151}, {954000000, 855883881}, {955000000, 565856511}, {956000000, 656009317}, {957000000, 86681597}, {958000000, 64328955}, {959000000, 790589}, {960000000, 536470464}, {961000000, 642221424}, {962000000, 244136591}, {963000000, 525825797}, {964000000, 275818160}, {965000000, 280340852}, {966000000, 730028787}, {967000000, 409218170}, {968000000, 79108141}, {969000000, 954731411}, {970000000, 507872352}, {971000000, 621501399}, {972000000, 172807928}, {973000000, 561179529}, {974000000, 906928038}, {975000000, 493641155}, {976000000, 187744247}, {977000000, 279470794}, {978000000, 100360210}, {979000000, 341007263}, {980000000, 660828195}, {981000000, 595645691}, {982000000, 515948717}, {983000000, 137614342}, {984000000, 481929980}, {985000000, 176549874}, {986000000, 371052309}, {987000000, 748989437}, {988000000, 689096578}, {989000000, 568632330}, {990000000, 20296095}, {991000000, 174311889}, {992000000, 120417790}, {993000000, 928065811}, {994000000, 171703488}, {995000000, 668262639}, {996000000, 359054580}, {997000000, 936566570}, {998000000, 604119165}, {999000000, 0}, {1000000000, 0} };
int len = 1001;


ll qmi(ll a, ll b, ll c) { ll res = 1; while (b) { if (b & 1) res = res * a % c; a = a * a % c; b >>= 1; } return res; }

ll get_inv(int x) {
    if (x >= 998000000) {
        ll res = 998244352;
        for (int i = MOD - 1; i > x; i--) res = res * i % MOD;
        return res;
    } else {
        auto u = lower_bound(inv, inv + len, pii{x, -INF}) - inv;
        ll res = inv[u].second;
        for (int i = x + 1; i <= inv[u].first; i++) res = res * i % MOD;
        return res;
    }
}

int main() {
    scanf("%d%d", &n, &m);
    if (n >= MOD && max(m, n - m) < MOD) {
        puts("0");
        return 0;
    } else if (n >= MOD) {
        m = min(m, n - m);
        ll res = 1;
        for (int i = n, j = 1; j <= m; j++, i--) res = res * i % MOD;
        res = res * 51625059 % MOD;
        for (int i = 2000000; i > m; i--) res = res * i % MOD;
        printf("%lld\n", res);
        return 0;
    }
    auto u = upper_bound(fac, fac + len, pii{n, INF}) - 1 - fac;
    ll res = fac[u].second;
    for (int i = fac[u].first + 1; i <= n; i++) res = res * i % MOD;
    res = res * get_inv(m) % MOD * get_inv(n - m) % MOD;
    printf("%lld\n", res);
    return 0;
}