1000
682152023 451794314 998244353
2028037 288974909 998244353
111681588 291303632 998244353
155763712 177741457 998244353
164199418 280452914 998244353
745629015 727272894 998244353
383855815 451963117 998244353
263419161 854025925 998244353
625817844 903511050 998244353
636159790 788165373 998244353
442332844 275132246 998244353
358996390 239303569 998244353
23523747 398318281 998244353
935986353 142493592 998244353
695297770 499848367 998244353
7061287 551242323 998244353
622426888 79384002 998244353
19141560 513456960 998244353
313082157 130997331 998244353
463541289 120030523 998244353
986922531 112618850 998244353
230228300 678849560 998244353
504459522 679335110 998244353
334404235 867470925 998244353
674397136 958197434 998244353
404243924 86377174 998244353
618061916 863589554 998244353
791513591 435167767 998244353
915162678 71459492 998244353
341562698 951473804 998244353
52898442 401242089 998244353
794478014 364178763 998244353
453002785 706324970 998244353
720922658 653545259 998244353
112784412 626625485 998244353
423006839 483894301 998244353
669309742 618420173 998244353
342823400 63159789 998244353
669473697 552010351 998244353
785773594 78145328 998244353
581004064 943346726 998244353
856912692 227723599 998244353
266280591 128456734 998244353
832249497 530649785 998244353
552244092 760049622 998244353
285284864 907915613 998244353
571051694 550324427 998244353
172354129 844757180 998244353
27279851 835825143 998244353
711708323 241389523 998244353
601591618 95282135 998244353
388198169 895143571 998244353
122021473 420267989 998244353
870020617 207534299 998244353
532166635 503056550 998244353
66284175 660803648 998244353
200677819 118884818 998244353
741997440 706435381 998244353
66950056 578541378 998244353
975233884 175415879 998244353
620832440 628486949 998244353
510176861 446057125 998244353
926002845 368100055 998244353
867115953 621658024 998244353
257571540 500057709 998244353
658107225 864636173 998244353
955201485 957474455 998244353
167265452 399008442 998244353
497916596 550847494 998244353
458109739 758608226 998244353
568056529 253805046 998244353
617776915 860690631 998244353
433527490 86561732 998244353
438782170 532703055 998244353
330922633 464996346 998244353
459050659 396169942 998244353
448906708 277614808 998244353
853056579 626274617 998244353
597214909 510226327 998244353
461020001 180426754 998244353
43412191 868977854 998244353
542275936 209267734 998244353
120714502 386859145 998244353
84098970 314300240 998244353
161552223 119634118 998244353
30107399 809928697 998244353
130763529 549763654 998244353
582647216 556636623 998244353
622786608 123862180 998244353
846344645 760720366 998244353
770611024 160906495 998244353
46147265 639857947 998244353
431937569 294403014 998244353
260015621 152536706 998244353
121038459 919321994 998244353
851501934 721753845 998244353
474964155 587182878 998244353
550621781 433177566 998244353
989881169 949027832 998244353
568805827 195162271 998244353
969391498 910191630 998244353
114548429 474202086 998244353
64884460 459208762 998244353
935590236 364830411 998244353
552865817 688217587 998244353
560792314 523106616 998244353
739024885 980716431 998244353
152225730 99227632 998244353
423647480 59551364 998244353
975997760 587481860 998244353
689797242 942223509 998244353
362895767 204797314 998244353
532352218 634094070 998244353
322778310 715453291 998244353
14371406 894999939 998244353
327962270 842741243 998244353
434672391 105983829 998244353
375024120 531433894 998244353
614069541 528901509 998244353
808264285 996866914 998244353
745140973 56268139 998244353
759836600 78552171 998244353
111933668 204658092 998244353
28006754 764401593 998244353
732123932 688293139 998244353
672712383 468924696 998244353
777760359 338013330 998244353
700743486 608345215 998244353
815071559 180352086 998244353
336664642 280134951 998244353
168859884 576353231 998244353
761089112 310076619 998244353
304003094 83056178 998244353
307780515 98992432 998244353
243035791 476132273 998244353
863471204 819145862 998244353
859516181 701455874 998244353
205980989 942428387 998244353
72726621 87302527 998244353
956897892 985380244 998244353
582435991 6608577 998244353
464022604 175084790 998244353
683266391 501862907 998244353
967413623 484718004 998244353
617253574 825068049 998244353
495045358 880548117 998244353
527208105 822668040 998244353
975435310 978633468 998244353
905111292 478112150 998244353
284212393 980064651 998244353
937789476 305802577 998244353
763536091 336975230 998244353
338281497 114673431 998244353
807004526 389190500 998244353
962890489 108514522 998244353
78431292 878717496 998244353
403000081 793108760 998244353
281288305 928598933 998244353
885567777 339577893 998244353
88841466 159610396 998244353
205321258 373371890 998244353
104693224 424187352 998244353
804486637 75820195 998244353
211866651 180200905 998244353
882036385 726140430 998244353
867745814 843037105 998244353
208630878 944395334 998244353
271708931 623265243 998244353
816371134 747264388 998244353
708077556 90765576 998244353
209724128 622903804 998244353
344839669 219853290 998244353
736616736 916270961 998244353
196958284 440001410 998244353
214684343 305426945 998244353
229904901 346811905 998244353
237084800 907324872 998244353
574395368 291432308 998244353
35586196 951947000 998244353
458646504 304064857 998244353
28039240 686130638 998244353
714159284 611174939 998244353
286421937 348381126 998244353
625755426 433820206 998244353
861275723 289979777 998244353
682086095 380623619 998244353
408305347 229586856 998244353
502129048 25446519 998244353
452060401 897933554 998244353
141870084 15243388 998244353
702028202 224743464 998244353
311700320 571143618 998244353
455987627 575524419 998244353
76108177 804158521 998244353
668871654 211336246 998244353
457775452 443110257 998244353
863389868 126489395 998244353
928121060 561958531 998244353
797463832 366334868 998244353
587464493 566463001 998244353
681172143 945114716 998244353
413896427 630528597 998244353
337985086 486347378 998244353
183660185 550253103 998244353
663568049 242794950 998244353
840665883 57760879 998244353
456838764 471916299 998244353
38786344 900175864 998244353
72535530 813624950 998244353
691649051 820683815 998244353
949829213 255672671 998244353
519859899 145137747 998244353
423646247 221160680 998244353
214783203 520235535 998244353
60772917 651799233 998244353
475281636 498349028 998244353
328168952 607442521 998244353
522769178 519973516 998244353
933593593 617144201 998244353
133150763 81723895 998244353
74330508 227500971 998244353
915828242 631320900 998244353
620907419 433606847 998244353
43215746 45956407 998244353
294506745 999094384 998244353
231641038 546614342 998244353
603609299 563751999 998244353
781857813 545181668 998244353
764184675 352533199 998244353
986305865 72715382 998244353
320611471 727155376 998244353
840677449 51268766 998244353
183594893 45193281 998244353
87091168 870012864 998244353
947432470 883101076 998244353
962033506 676294055 998244353
373156934 114102533 998244353
83925882 781464519 998244353
753373998 972445777 998244353
785060110 455384569 998244353
274344623 791371508 998244353
617382207 838633726 998244353
570282763 514430966 998244353
372484525 634425797 998244353
551526698 455824776 998244353
379011543 299972613 998244353
892614481 81335454 998244353
646920332 282117799 998244353
105985216 146743806 998244353
178845514 330235168 998244353
284596920 301422341 998244353
623894365 588608851 998244353
330146608 533413148 998244353
76470245 247849260 998244353
9246293 518634012 998244353
233187234 326891103 998244353
274768935 348647640 998244353
82779480 980656692 998244353
449516480 753554428 998244353
882617980 535805318 998244353
524334374 823734889 998244353
973035208 680272033 998244353
307300651 414219239 998244353
97026390 983962743 998244353
944504216 844795215 998244353
454254099 469367460 998244353
603046378 417499075 998244353
901499443 989010486 998244353
803124886 121220623 998244353
798998019 548236217 998244353
281817041 240553645 998244353
261052324 529457076 998244353
519427722 161692015 998244353
976242165 226544419 998244353
175029763 190714064 998244353
287964252 229891547 998244353
20904054 8696408 998244353
529348415 607373762 998244353
514539007 169566498 998244353
657279947 966631504 998244353
284016191 351748042 998244353
911413982 805263381 998244353
713580376 387302907 998244353
502855668 930031589 998244353
916421738 390890643 998244353
198825250 458864423 998244353
263814886 54240430 998244353
983167857 247517286 998244353
570280523 935108008 998244353
308153722 276492234 998244353
353591171 940800475 998244353
367481590 126401822 998244353
485594138 346645790 998244353
189381340 59895031 998244353
846516944 54422822 998244353
349828943 704698251 998244353
45911057 756238549 998244353
763158411 970495810 998244353
967629623 184391923 998244353
660040477 561200155 998244353
898560071 319304770 998244353
757944538 143115213 998244353
663391954 69550558 998244353
517196077 965389227 998244353
869461847 546809021 998244353
781250678 857579872 998244353
768671327 949232966 998244353
578716138 76163112 998244353
509062848 266371939 998244353
565850082 590791380 998244353
422058884 886502527 998244353
888402029 16414169 998244353
407960965 379599081 998244353
8122209 272522925 998244353
855444945 102385502 998244353
402157115 781034555 998244353
118599642 862078786 998244353
847989979 742385707 998244353
813864068 689336981 998244353
129251103 436653166 998244353
305164406 633982232 998244353
792637559 653151242 998244353
222757680 189059423 998244353
847572863 734209400 998244353
717560536 346612591 998244353
543939555 517050858 998244353
24589830 952920737 998244353
444435482 5765982 998244353
833739360 29103290 998244353
771252696 499383243 998244353
628989318 730863911 998244353
668912710 92465847 998244353
365769391 443637556 998244353
878870393 394177327 998244353
400684388 574053282 998244353
890762012 741521257 998244353
524423569 794659667 998244353
828836522 125485645 998244353
430267061 111038877 998244353
62745536 236639111 998244353
51750372 659612221 998244353
752844565 14852799 998244353
874034905 867871519 998244353
243779566 505721960 998244353
707299722 530860711 998244353
481744957 50580741 998244353
484149522 379745349 998244353
46814191 740544648 998244353
722766541 896329310 998244353
361788372 311657544 998244353
610996108 888091496 998244353
430365405 420512486 998244353
939326259 578918892 998244353
252382134 371400837 998244353
355009277 576735036 998244353
81606971 619194106 998244353
594260859 641632566 998244353
292458897 929186387 998244353
895851276 909664680 998244353
812328304 538341043 998244353
410907375 941994331 998244353
620296175 472583135 998244353
345793905 283994406 998244353
355607742 153994991 998244353
914308831 368325515 998244353
537456926 275273408 998244353
653684611 854254304 998244353
767981759 67449960 998244353
340500187 719738719 998244353
851351537 297097408 998244353
790261126 197704876 998244353
549323752 172054250 998244353
739248108 227473335 998244353
354972145 973791991 998244353
287017167 597143956 998244353
695845980 835832999 998244353
924228916 952414871 998244353
318174198 660733491 998244353
652354802 96757942 998244353
345279394 252615446 998244353
903576476 343978817 998244353
768224079 507129553 998244353
757838074 810269014 998244353
440470426 624330802 998244353
742222123 450117276 998244353
977013510 898986217 998244353
976646162 491907006 998244353
562769062 518587755 998244353
381270183 114441560 998244353
827240641 154476295 998244353
738077341 71542195 998244353
152230062 372604976 998244353
763760239 903310376 998244353
700259064 912266932 998244353
856858638 659149431 998244353
458318474 286193931 998244353
662641044 234686172 998244353
613250184 442747050 998244353
34144278 201890138 998244353
317002777 168156013 998244353
475319310 575974608 998244353
414690587 683797231 998244353
684662482 120433262 998244353
910337844 413813309 998244353
175187201 961781164 998244353
816651631 27580293 998244353
583134523 419456212 998244353
503352024 375696989 998244353
504780461 744261654 998244353
948566844 20546462 998244353
44708484 86797739 998244353
370187103 560483621 998244353
861865499 528341411 998244353
44202244 851907148 998244353
49543740 2624641 998244353
245147211 982513114 998244353
994952889 742844587 998244353
779168174 353629233 998244353
99930807 618251865 998244353
238446186 491431305 998244353
379364414 608071386 998244353
334568773 57735655 998244353
260476618 494415944 998244353
875817069 910943462 998244353
340084278 196282012 998244353
376039495 639692848 998244353
593471189 584961746 998244353
764578 540554830 998244353
278067627 437613621 998244353
108548066 451481881 998244353
386484282 650879013 998244353
16771650 327974806 998244353
599323037 999388869 998244353
322810004 442802927 998244353
846346046 488250817 998244353
205601782 106686718 998244353
909395890 681940431 998244353
895001824 705408869 998244353
491246676 26114517 998244353
725216553 981264140 998244353
720284579 685457622 998244353
244939119 782462812 998244353
606993113 401836482 998244353
557809667 278191703 998244353
631159636 265852919 998244353
4893381 823009355 998244353
967949958 936113153 998244353
80948787 517564089 998244353
3705161 235569558 998244353
868546767 203145326 998244353
215798249 293701661 998244353
33485587 680057930 998244353
844260210 932522190 998244353
652046446 791260430 998244353
38738491 628698930 998244353
62304196 738594186 998244353
611435427 705473032 998244353
406018632 654534851 998244353
63791233 833300133 998244353
635402901 726255392 998244353
734492223 753785395 998244353
233947497 784785662 998244353
887052363 66930935 998244353
26128454 225313059 998244353
703351677 435125464 998244353
325242292 892188133 998244353
293895915 64721009 998244353
294884590 561010055 998244353
769612201 988165342 998244353
384774385 65483742 998244353
402768782 348058905 998244353
867762245 959633039 998244353
883795633 30240740 998244353
662547681 760257430 998244353
828874928 253763168 998244353
914879411 623847413 998244353
362803244 858150668 998244353
317023509 652282203 998244353
960531293 110181973 998244353
706402033 729093676 998244353
149989169 477980908 998244353
942605819 897030646 998244353
450162229 576438068 998244353
853182073 484318300 998244353
77512525 455932472 998244353
354179841 430054535 998244353
16586155 886014425 998244353
657239849 839924221 998244353
131376520 856009042 998244353
858278041 967237220 998244353
369131235 70975543 998244353
59588081 620901497 998244353
585246979 998198889 998244353
444414348 304556314 998244353
154086711 694457663 998244353
393515271 596315558 998244353
97938864 231792465 998244353
571774243 139853651 998244353
56361304 933263032 998244353
487174132 860831799 998244353
46380721 234895474 998244353
246192641 729409762 998244353
265981018 853391349 998244353
225681732 197695833 998244353
493900182 387415318 998244353
886509792 347299546 998244353
311874252 913796254 998244353
175048697 627516190 998244353
17702021 787669116 998244353
162813001 426633440 998244353
292151786 155821378 998244353
115540099 726492303 998244353
70147847 922100324 998244353
860280508 446450229 998244353
801616369 245616013 998244353
853893597 94989516 998244353
135767209 957243505 998244353
392040834 692349034 998244353
825547009 754696782 998244353
621250234 992140983 998244353
789617230 65211310 998244353
110453295 841214656 998244353
456164875 101540948 998244353
778277113 522012836 998244353
261644220 575194085 998244353
851798996 159192545 998244353
450356301 36273279 998244353
125232829 885496679 998244353
454299088 183561275 998244353
182729218 904263356 998244353
417080962 177443204 998244353
461619084 202304988 998244353
84420143 487923323 998244353
257834256 133748343 998244353
561886833 388138416 998244353
870264293 527080065 998244353
317172491 999227305 998244353
866707298 812980618 998244353
630548469 373637382 998244353
286401206 459072018 998244353
720965021 585966380 998244353
932670588 491329557 998244353
751243917 166094065 998244353
137151442 170507052 998244353
921100533 121962836 998244353
677493160 769773508 998244353
345091371 670112610 998244353
241152273 879948736 998244353
904060581 11664155 998244353
345025415 335301368 998244353
235821675 242969155 998244353
552124787 457963172 998244353
662436830 281475226 998244353
182954029 433686943 998244353
113723641 340926210 998244353
211129347 993049717 998244353
912861217 890320626 998244353
259695146 347086245 998244353
36293419 878985001 998244353
370746945 639883606 998244353
976484256 394522229 998244353
82547243 114267292 998244353
941180525 584170081 998244353
724840614 505964067 998244353
271211267 344378474 998244353
611380522 306774272 998244353
419738113 699166131 998244353
77386951 378682755 998244353
495408250 328353431 998244353
694044872 130585676 998244353
474737164 194385992 998244353
637912460 340924827 998244353
494379799 126328174 998244353
111182340 435937675 998244353
325441569 664481975 998244353
258115640 771724737 998244353
470101686 578701581 998244353
742127108 754220216 998244353
396036721 894375153 998244353
654620792 757225950 998244353
580164875 837007508 998244353
942431706 844150821 998244353
39086392 154012290 998244353
308156964 102616744 998244353
716201384 657005461 998244353
260795795 766449993 998244353
807890232 751514915 998244353
382097010 637628393 998244353
660105891 869093487 998244353
981528456 254801956 998244353
697633479 183419214 998244353
379631872 369352476 998244353
951676443 90970654 998244353
955493913 345295021 998244353
158324730 537412321 998244353
321215648 256522534 998244353
464105562 594862729 998244353
848393239 539193011 998244353
190874781 147308304 998244353
643658286 677508645 998244353
844950704 933952024 998244353
983801730 804837466 998244353
188393542 669323327 998244353
165837528 793449930 998244353
501288078 236332297 998244353
933167257 371019562 998244353
942912202 466917556 998244353
894298138 984946209 998244353
766651297 326787475 998244353
741091912 786668297 998244353
513513369 582989041 998244353
756199251 112203765 998244353
339494645 337779579 998244353
105737295 81873520 998244353
797842699 539615230 998244353
340335924 155391663 998244353
868437441 568897165 998244353
215597145 760440260 998244353
833038624 128258 998244353
176289572 257766566 998244353
639709358 729335421 998244353
172758280 633303077 998244353
916947760 489013666 998244353
685824385 469488410 998244353
775776431 154367658 998244353
356882314 835785617 998244353
353635634 723875827 998244353
56090078 279034344 998244353
955495596 895679794 998244353
703811036 731443454 998244353
735589433 681474196 998244353
881502301 245908593 998244353
513738856 255164896 998244353
929925657 353460885 998244353
914423278 631664904 998244353
395618384 330915559 998244353
72673733 848685348 998244353
305633267 200317370 998244353
994385016 598153863 998244353
358760597 275810710 998244353
948615695 82905156 998244353
503528324 324146325 998244353
667626192 982852566 998244353
4976594 972537500 998244353
273401550 173831241 998244353
96762746 795302614 998244353
509840875 42016199 998244353
952161724 699907088 998244353
701341470 499692603 998244353
335225062 507531979 998244353
160659825 207671534 998244353
183191834 652880394 998244353
359007647 240140498 998244353
82138311 221915225 998244353
729462563 545443505 998244353
324752557 94821154 998244353
682475087 81584420 998244353
367592294 341935859 998244353
768335439 182493834 998244353
770796680 993588165 998244353
912371438 697961499 998244353
112230373 740977150 998244353
866764510 150065434 998244353
82938852 721875350 998244353
509999149 715349064 998244353
50490392 354625010 998244353
8672210 589742956 998244353
218469565 769330344 998244353
843376472 458403219 998244353
861979970 502477152 998244353
563815354 169266419 998244353
54934515 423962069 998244353
590724965 734297010 998244353
735412362 276486270 998244353
491768240 187904868 998244353
894436612 458949571 998244353
587954329 689009390 998244353
337916162 866559916 998244353
727947851 157691725 998244353
300488211 490705427 998244353
654886776 110388030 998244353
224087428 679993118 998244353
975364968 922835629 998244353
642502812 655568858 998244353
225728267 351315953 998244353
373356243 113081597 998244353
138454344 537234243 998244353
816460707 916378949 998244353
161132075 821979038 998244353
171570644 755674767 998244353
825121686 114698758 998244353
961073918 627855851 998244353
847545483 22290054 998244353
473366666 252567286 998244353
737484348 288494966 998244353
121793 664563471 998244353
314068722 370243858 998244353
84374181 913930703 998244353
563755869 793183658 998244353
254405848 21718124 998244353
659512811 591776115 998244353
208575080 760637832 998244353
477365464 110209022 998244353
463569464 696565029 998244353
799099894 475323861 998244353
380306104 561246603 998244353
816037412 266258022 998244353
759875755 10920697 998244353
175549577 692811963 998244353
82634044 424431051 998244353
746647253 983551974 998244353
354673442 768917045 998244353
577769620 286333823 998244353
492817205 672653511 998244353
676648358 518936665 998244353
343165129 856009013 998244353
772538317 209047857 998244353
296976106 463732753 998244353
524122623 618914966 998244353
957521004 421537295 998244353
839928596 364803493 998244353
207387694 644306509 998244353
752298283 613757709 998244353
197276768 750915000 998244353
195108692 665595047 998244353
814320540 374106389 998244353
840989793 508871638 998244353
317900773 638083423 998244353
81505502 489612888 998244353
766408136 302921316 998244353
29544803 793640062 998244353
321789328 50108394 998244353
697284173 424634317 998244353
335393825 218136501 998244353
774076873 183985956 998244353
57965202 495551114 998244353
133737119 322838698 998244353
856751254 612159490 998244353
900322021 128998531 998244353
747048967 370431949 998244353
890858721 910267853 998244353
184371911 664979797 998244353
467553490 53258533 998244353
491816387 556316945 998244353
903575355 137710787 998244353
925480168 936463604 998244353
644512977 300614129 998244353
920936078 931217463 998244353
203570971 48544085 998244353
282775903 910037197 998244353
81941724 578579685 998244353
47788696 659003054 998244353
183416527 384230227 998244353
177716842 724129964 998244353
354690883 364273509 998244353
321516065 882417804 998244353
542339858 124096761 998244353
537534999 398263015 998244353
253507674 13383963 998244353
65901969 831348881 998244353
564669474 76826761 998244353
848142994 529735745 998244353
324544888 568633616 998244353
583455315 988063437 998244353
283386683 777709999 998244353
563133578 982458068 998244353
687075482 351206547 998244353
2188320 156211275 998244353
2923605 68611613 998244353
700439537 433732224 998244353
295725504 118328444 998244353
988154385 904353904 998244353
769067307 624502763 998244353
441964570 784205020 998244353
814327856 776138031 998244353
950801488 762666511 998244353
462022263 879757837 998244353
319623627 63994635 998244353
887319965 769136867 998244353
264389059 578747744 998244353
97785294 297680229 998244353
563709566 488383413 998244353
114921171 618079688 998244353
77039814 292716908 998244353
542900098 213986600 998244353
399434404 441537157 998244353
990258624 704595457 998244353
500955350 129858962 998244353
156760992 118854636 998244353
183490785 583866524 998244353
813448953 384135442 998244353
879965705 838241018 998244353
316399854 345170534 998244353
635085621 954980109 998244353
368390735 538142897 998244353
737200850 459089971 998244353
108667097 770698681 998244353
653326136 998279319 998244353
243042281 250840088 998244353
79115219 961125936 998244353
505410550 621160719 998244353
796460858 110910278 998244353
565080888 38990527 998244353
758579820 913070089 998244353
966762001 637670682 998244353
963781998 387127990 998244353
2639234 586457843 998244353
395829185 850822563 998244353
423874899 51037346 998244353
988990733 302521658 998244353
456388835 184724277 998244353
761926983 554630039 998244353
992031137 507972935 998244353
796874202 383275355 998244353
944971461 383101472 998244353
537796772 395243429 998244353
405084589 474295775 998244353
485477222 146933050 998244353
163479400 662105272 998244353
430395920 83931051 998244353
90729002 320661961 998244353
193845034 447236497 998244353
997373637 776739816 998244353
125027304 135381826 998244353
442223274 856817713 998244353
434270290 346899374 998244353
944794916 670408978 998244353
814643062 327005109 998244353
239215592 827148972 998244353
578543558 355141343 998244353
159235278 52141651 998244353
393452979 145510325 998244353
434146433 450694315 998244353
307604118 353069775 998244353
41393010 701290127 998244353
58250910 365511286 998244353
544660282 656416753 998244353
221830753 520020324 998244353
700827113 740371297 998244353
684591266 279037785 998244353
368966432 25212962 998244353
407268235 627109941 998244353
419201196 844276368 998244353
646545973 55778846 998244353
525065886 539807928 998244353
460712235 288395979 998244353
484265422 588638150 998244353
220713235 441767864 998244353
483790392 805211749 998244353
531022350 405047935 998244353
886345240 612416729 998244353
608160812 957322865 998244353
670217152 379076957 998244353
313042741 803349376 998244353
178027541 160574140 998244353
685742817 814557701 998244353
8069699 825309174 998244353
913768337 489130518 998244353
498856412 937889446 998244353
477092258 335236300 998244353
774127232 540161685 998244353
538460412 23737158 998244353
691874099 526104534 998244353
45907502 437162938 998244353
402934418 59462073 998244353
702135169 965064130 998244353
437455251 996436442 998244353
330077983 198997816 998244353
13803840 152114588 998244353
44016557 496291830 998244353
357266634 807406894 998244353
389043558 690277338 998244353
789521226 880535546 998244353
319424831 860348620 998244353
372972338 212529947 998244353
598754430 425466212 998244353
770739938 927566744 998244353
289282539 613009066 998244353
386921759 95526534 998244353
839905914 463183514 998244353
245802781 755160840 998244353
130003749 126401762 998244353
732278439 982142700 998244353
141510978 393406903 998244353
285866758 243693087 998244353
867095867 272861427 998244353
81467582 325530485 998244353
590887790 837796832 998244353
3950083 859796220 998244353
271711840 732888658 998244353
917832099 633602574 998244353
994403486 287201390 998244353
937688001 999095193 998244353
270388796 661902701 998244353
447176165 239976799 998244353
339604960 753148198 998244353
798338445 649599845 998244353
778239454 582868572 998244353
400503667 863519261 998244353
986698041 982316512 998244353
650600619 442967485 998244353
98032734 256540808 998244353
428699977 181726585 998244353
484276348 888602040 998244353
916817675 765119942 998244353
865234955 575117668 998244353
559960518 426837366 998244353
311485213 25720454 998244353
302730665 861019975 998244353
128138853 658832227 998244353
695519885 843017110 998244353
825595059 535372429 998244353
404756819 557946322 998244353
150803473 134496758 998244353
641624642 71637757 998244353
99599742 320403156 998244353
351386748 648749317 998244353
652732796 240310986 998244353
255793095 925308162 998244353
579496577 756492085 998244353
355631725 151651901 998244353
561223183 920056113 998244353
551879193 600197100 998244353
38875461 140078053 998244353
837794599 951542626 998244353
21197528 377356506 998244353
837358700 410740931 998244353
313784048 669944935 998244353
747815440 306804400 998244353
84537757 784806327 998244353
86792988 954016546 998244353
983683746 373865992 998244353
89960101 634750662 998244353
364609046 463411917 998244353
809714940 930471606 998244353
280324455 103669290 998244353
37551426 772588612 998244353
171394420 713335534 998244353
646336792 422110944 998244353
774126169 324192725 998244353
770447192 641214101 998244353
130694881 986479257 998244353
427036723 83062946 998244353
26656091 857907483 998244353
342029453 308215944 998244353
865849344 537585949 998244353
209476355 989312803 998244353
711955010 79951244 998244353
871413278 59336506 998244353
749198799 30675188 998244353
52919989 866615738 998244353
653977534 728120897 998244353
619028467 309277966 998244353
376997052 243217323 998244353
129640193 597216553 998244353
610756116 137700306 998244353
591029193 348438381 998244353
520573690 236249901 998244353
282268718 184012728 998244353
929943645 776532688 998244353
158223415 746008461 998244353
261748694 910268942 998244353
828836887 608294155 998244353
41723008 160248577 998244353
496064638 172517437 998244353
116218422 256748458 998244353
318070943 378511426 998244353
468724141 314116798 998244353
566898670 45742215 998244353
475115790 278131290 998244353
556911579 121551852 998244353
40625644 106313155 998244353
199175044 252241222 998244353
561139164 911083610 998244353
735324844 335108676 998244353
509215929 830680466 998244353
137909211 723275452 998244353
609667498 425888968 998244353
827442002 837869914 998244353
888891700 134512119 998244353
696737326 185707674 998244353
78499341 299460902 998244353
854589946 510579442 998244353
408804740 552063151 998244353
725715884 73341907 998244353
259092474 789756378 998244353
300046275 44417620 998244353
495689088 219242027 998244353
840088176 389095662 998244353
473846510 508287608 998244353
426359813 714716599 998244353
742191536 839814257 998244353
587471749 294520464 998244353
963640121 871850081 998244353
882527791 122612472 998244353
952974083 437826576 998244353
497875500 483778916 998244353
196046 63393520 998244353
642032320 234910533 998244353
180902473 601516217 998244353