1000
264704197 120999146 998244353
136987924 40280999 998244353
438515315 805152546 998244353
234164454 129099933 998244353
971852321 983937488 998244353
410134225 668461222 998244353
574343409 885417013 998244353
394300887 86086437 998244353
570981511 221329455 998244353
57893312 584381871 998244353
154204049 738660729 998244353
728257729 551666498 998244353
540440394 165573287 998244353
512342480 452470821 998244353
669622703 340240729 998244353
965382636 953292241 998244353
144902419 86035524 998244353
289571086 987645468 998244353
423893886 928104871 998244353
464748969 105872436 998244353
123582647 242780928 998244353
505538017 199537013 998244353
745991283 983136444 998244353
65304379 842202106 998244353
646596193 140145001 998244353
630412665 134706415 998244353
170189559 917006962 998244353
498351627 78228861 998244353
784928508 545206283 998244353
276287905 127534371 998244353
580361498 602636875 998244353
833497706 569752320 998244353
168745739 687931378 998244353
25556222 401296664 998244353
903079778 244718550 998244353
696658577 923575834 998244353
20801451 728508574 998244353
144327567 355924229 998244353
987918030 767675763 998244353
39770237 690017157 998244353
35094958 619519152 998244353
803294929 322191158 998244353
334280933 412368057 998244353
946079172 696252934 998244353
727024412 429649275 998244353
739609644 879769415 998244353
84017875 429336930 998244353
578822041 559811577 998244353
192014409 783587083 998244353
235524450 277645214 998244353
641105035 776026757 998244353
478219070 115129181 998244353
14794716 647713890 998244353
894892898 720571222 998244353
16609338 29190516 998244353
796633468 940732244 998244353
641040997 243193942 998244353
968755343 956678858 998244353
9273458 747543114 998244353
522400393 605708171 998244353
235611799 713122606 998244353
952769734 230441676 998244353
782661943 119932537 998244353
618863044 263420409 998244353
832590609 341598454 998244353
889752736 346283651 998244353
906815307 693782514 998244353
787563199 656787150 998244353
558988762 325699987 998244353
408388854 484659329 998244353
514686813 546683978 998244353
168335178 925036722 998244353
876453250 928472013 998244353
452720553 11844689 998244353
152089336 237462880 998244353
322160445 768682370 998244353
968998501 643437693 998244353
43682975 50514865 998244353
225072892 729100215 998244353
432384534 267319887 998244353
944916772 470850912 998244353
634063725 30265497 998244353
170224154 233237753 998244353
310521575 363661868 998244353
30383316 169764888 998244353
450267291 509435980 998244353
637917173 871736242 998244353
398793145 910647926 998244353
108164902 535373865 998244353
729080956 796833592 998244353
454223174 403988143 998244353
945062274 621479206 998244353
158107041 272551814 998244353
767759721 136585361 998244353
638455939 61417522 998244353
286340474 221735821 998244353
57584824 684185411 998244353
747165460 140519367 998244353
201499817 652532397 998244353
746971523 597836965 998244353
403721689 956715523 998244353
163056092 661594742 998244353
716321675 768003151 998244353
590039320 568646343 998244353
716350006 451084111 998244353
528630621 313480942 998244353
118564698 359276034 998244353
829011041 701887370 998244353
725160671 666415978 998244353
738132895 114167505 998244353
659739773 31924187 998244353
55285186 560410488 998244353
920735596 860283017 998244353
130521101 634454758 998244353
758692855 367621879 998244353
37543666 929265562 998244353
700477795 673784691 998244353
852411165 71823458 998244353
547390766 338428922 998244353
269296694 866684149 998244353
689572434 918907490 998244353
292588975 817571123 998244353
959281983 237458599 998244353
110596904 240580147 998244353
243465869 754150540 998244353
417951469 281530082 998244353
3734782 837883412 998244353
802111064 342905930 998244353
634546070 489807159 998244353
227640803 152130560 998244353
715231872 928498199 998244353
246388488 150318222 998244353
849120860 925374177 998244353
144892127 398434867 998244353
729447157 621850442 998244353
452366143 469546842 998244353
539193693 387659516 998244353
713639740 534692970 998244353
516992535 857296504 998244353
338125822 866018073 998244353
835065313 510544637 998244353
841323884 623928018 998244353
263447616 97154821 998244353
157189035 626682906 998244353
850977848 865147377 998244353
547354125 291373786 998244353
244996624 939186671 998244353
470490191 110958524 998244353
736419272 379219571 998244353
498680309 361856442 998244353
100482924 442510270 998244353
773429065 207078157 998244353
857344783 659400969 998244353
841728390 692474075 998244353
187583662 175274604 998244353
203919131 521450008 998244353
542450577 561050789 998244353
483834181 666635165 998244353
281236448 744939400 998244353
606001978 339209101 998244353
825332344 409340060 998244353
105053325 334942889 998244353
701010888 52772808 998244353
89618199 62382450 998244353
312651094 267282041 998244353
738280309 813796994 998244353
153189966 976016018 998244353
645498866 305360396 998244353
624826185 89137985 998244353
804282524 278984850 998244353
215551309 168847257 998244353
594398943 553423322 998244353
316656379 938695783 998244353
362188486 979254770 998244353
615808805 280079020 998244353
162058869 734380867 998244353
181183810 369453245 998244353
10097001 370504521 998244353
99611572 71283549 998244353
375804845 690139394 998244353
298702528 556804228 998244353
57525845 328898093 998244353
541889825 375688946 998244353
127439949 637860162 998244353
88758221 860742112 998244353
825399220 195532272 998244353
296560866 898263825 998244353
226507934 152656046 998244353
744845166 27581792 998244353
599790352 363219948 998244353
766909962 998994842 998244353
542625171 231657310 998244353
545144535 908129469 998244353
857808700 828842600 998244353
58937965 640541108 998244353
137921815 28350886 998244353
652508654 643869973 998244353
722021608 678993723 998244353
841257574 133264624 998244353
93113222 542874973 998244353
243438394 898920791 998244353
87870405 571326178 998244353
595882116 80857922 998244353
669576241 881037234 998244353
751107032 508469231 998244353
307671666 507999415 998244353
520756793 745631224 998244353
52014388 230352221 998244353
525650738 660315722 998244353
503767010 204996751 998244353
276291221 664210989 998244353
151320875 599909211 998244353
925460171 408720654 998244353
240375863 829642972 998244353
167269687 511882951 998244353
651482680 361674598 998244353
595158462 843234786 998244353
901936204 785745600 998244353
501130119 423181627 998244353
966641925 366621967 998244353
608618061 936072922 998244353
771638072 796521561 998244353
282814428 707172910 998244353
649949343 222508649 998244353
870914963 453849073 998244353
301814340 446156727 998244353
275123659 405340166 998244353
639133553 908796254 998244353
624069800 989896706 998244353
739052214 367907666 998244353
419326829 798705655 998244353
949998257 404075252 998244353
381212131 844178042 998244353
667444605 85885665 998244353
866208268 221166146 998244353
963673720 431514130 998244353
572154241 589291507 998244353
484046818 76028159 998244353
331125923 943448847 998244353
963269306 950314008 998244353
454860215 671912499 998244353
631376617 421669677 998244353
686364693 493511239 998244353
243776850 33178914 998244353
771394023 705494253 998244353
780656564 950203751 998244353
401551808 911153562 998244353
222352670 713096228 998244353
4873554 522951161 998244353
898293860 876305539 998244353
713583463 169501973 998244353
692354474 590425869 998244353
138797942 423932057 998244353
89855279 953274951 998244353
36055194 583694890 998244353
284557380 125583279 998244353
109265482 517158975 998244353
679505068 899086402 998244353
30153826 152428854 998244353
400940805 814102622 998244353
387312147 863423383 998244353
522109047 930181370 998244353
411641248 441522916 998244353
638436687 157747928 998244353
462976946 602205583 998244353
324007774 608422754 998244353
241156717 927009838 998244353
525235777 26330288 998244353
350816998 324804570 998244353
64281672 458859964 998244353
757421184 484881735 998244353
231860715 741853637 998244353
100094374 413476035 998244353
861509035 466379692 998244353
737395667 473100877 998244353
485500327 883936894 998244353
566698676 853582737 998244353
771426223 335434231 998244353
892162908 637795835 998244353
374816020 216075739 998244353
255716655 839738025 998244353
818202475 636086218 998244353
292502906 760752795 998244353
323432900 319170370 998244353
627815219 116770363 998244353
270748787 848522386 998244353
566176918 269382538 998244353
760197523 716607965 998244353
269854968 452119349 998244353
216095588 551878799 998244353
561995103 605114428 998244353
347367663 585069043 998244353
796207312 976644436 998244353
168236723 526468099 998244353
39759609 169964459 998244353
665264332 85791246 998244353
322395252 811953378 998244353
920480819 73868602 998244353
901430342 642875472 998244353
819534976 497343164 998244353
142912010 159574371 998244353
817081938 260807988 998244353
569032646 461284519 998244353
931522758 357440133 998244353
92109771 695786347 998244353
988662715 997640683 998244353
88222446 901367480 998244353
731742988 163841780 998244353
795671284 106337837 998244353
806399633 527279853 998244353
85692509 825600827 998244353
187824050 978085038 998244353
662394583 493339852 998244353
956562731 339381673 998244353
526029630 893915970 998244353
998671142 145225888 998244353
807361520 843153344 998244353
237366813 493349993 998244353
584803239 594170986 998244353
919760600 109872641 998244353
162436711 479524148 998244353
339756055 612937461 998244353
118527668 98267328 998244353
610994557 89281857 998244353
974945370 695401048 998244353
488129989 515133051 998244353
652937312 917441227 998244353
877139 82935094 998244353
369633655 948184250 998244353
720802111 364262472 998244353
537818844 418022911 998244353
244117671 184035561 998244353
902811118 654967618 998244353
916469760 642095996 998244353
634175117 537000401 998244353
384222483 441025849 998244353
754252108 675523106 998244353
32679843 818238629 998244353
282410430 47210910 998244353
316296338 827369309 998244353
740322912 858165232 998244353
7145962 834245142 998244353
355398069 447978048 998244353
322237571 280944444 998244353
129467789 533468369 998244353
896433231 245263616 998244353
269187614 653873631 998244353
804440053 301129599 998244353
224523527 859394320 998244353
625589344 151351159 998244353
485191725 34390845 998244353
720556424 552205755 998244353
302378597 558013827 998244353
702629473 596451847 998244353
589022172 635637210 998244353
166517029 880745027 998244353
229409044 663049001 998244353
485274459 244268086 998244353
135905818 523871556 998244353
712303460 234812541 998244353
875650875 400756756 998244353
940668164 520949196 998244353
119219626 375497475 998244353
770641585 893349700 998244353
810194255 206506864 998244353
518646675 94307197 998244353
284576740 839760004 998244353
944915557 426487833 998244353
651422108 245042497 998244353
588680664 112770657 998244353
54022602 253354221 998244353
890134815 540428524 998244353
563498599 286157085 998244353
765106037 766458105 998244353
830410082 156562027 998244353
526645190 830082524 998244353
224135858 975930688 998244353
151352644 730750936 998244353
891331027 393297837 998244353
424882569 183509738 998244353
935502917 236199293 998244353
961675598 210839789 998244353
724016131 163052826 998244353
12296602 783841626 998244353
498039791 72802301 998244353
186391175 532449389 998244353
213899035 848004693 998244353
530340286 5263801 998244353
204683471 395997628 998244353
488334502 616630150 998244353
269207415 693423687 998244353
281726246 20506370 998244353
54478886 507281136 998244353
160954027 734642588 998244353
690886710 963151748 998244353
554242922 969184968 998244353
734914985 834765732 998244353
790446548 418129336 998244353
669525757 769724940 998244353
653214462 340192294 998244353
446159633 818417818 998244353
541094465 50958912 998244353
318296181 69311348 998244353
723009320 18516670 998244353
406755068 326864968 998244353
390541367 407070587 998244353
121389775 685191434 998244353
280341374 108644580 998244353
375423282 227166411 998244353
938363350 750969264 998244353
999845708 374953701 998244353
492206462 481127343 998244353
729265460 953031114 998244353
854789452 237031361 998244353
955067289 866248813 998244353
228444667 649244495 998244353
324406271 120797077 998244353
314646544 58959399 998244353
3288366 854622117 998244353
468356745 979235013 998244353
661217923 520611197 998244353
686358881 517707400 998244353
338566459 58201392 998244353
815107772 907610260 998244353
767597128 499736218 998244353
545302930 627063788 998244353
460040357 184461369 998244353
606809522 728341852 998244353
668869817 577081132 998244353
222858265 591152692 998244353
879521451 403609733 998244353
818954775 373903993 998244353
993650663 67520448 998244353
295570354 99912702 998244353
862739997 395323616 998244353
677553429 52838932 998244353
40899335 74571117 998244353
987025786 980274186 998244353
972506541 274079910 998244353
688510330 857273476 998244353
67448884 946779393 998244353
59277318 994160143 998244353
742529501 981347101 998244353
343974824 696929226 998244353
335495729 610436273 998244353
714037097 57759471 998244353
388800742 589706421 998244353
973148751 250362369 998244353
835072764 745491860 998244353
446644573 679685394 998244353
366181981 920499234 998244353
641446830 637634625 998244353
917033537 350931057 998244353
376037334 429588715 998244353
227044621 774188754 998244353
428291718 883994450 998244353
138116461 365355333 998244353
881966517 720462542 998244353
891208039 897541378 998244353
792786923 740165942 998244353
736566640 308601023 998244353
720142076 316224772 998244353
518309911 968134725 998244353
516682261 194774701 998244353
375083203 581689790 998244353
172010851 974083704 998244353
139773573 46131932 998244353
614258835 451778839 998244353
85044254 54841683 998244353
371155842 32688198 998244353
227359267 627867173 998244353
218086483 259886832 998244353
87690949 552123679 998244353
790431707 365164248 998244353
993199867 999389665 998244353
214438533 525514196 998244353
717361563 275267118 998244353
498031960 922279250 998244353
640263313 55184923 998244353
853033845 892457772 998244353
840592168 1497454 998244353
939173026 200095662 998244353
386617574 250518793 998244353
905424128 291020254 998244353
318554790 182317674 998244353
868171036 759958543 998244353
743402101 964108290 998244353
272590670 145210301 998244353
558711506 6431291 998244353
576740159 346371626 998244353
708335123 108782814 998244353
886683076 639620797 998244353
635280149 495628851 998244353
708843881 925044897 998244353
751828618 361829421 998244353
307252380 296901157 998244353
277039009 806187232 998244353
966648629 827868799 998244353
435384030 946003994 998244353
230111596 254914868 998244353
825033134 500859488 998244353
180162076 361262826 998244353
920210341 260278945 998244353
365764956 488480807 998244353
345594555 468285234 998244353
624776852 303886936 998244353
611534100 579438333 998244353
656556351 483966138 998244353
265187640 107309654 998244353
428717427 198663185 998244353
157908235 442044028 998244353
640996606 436201726 998244353
193439789 190420492 998244353
261241586 665487283 998244353
534264383 957831147 998244353
301089289 11767269 998244353
791758022 583708953 998244353
460867723 414240861 998244353
67023643 983581695 998244353
276760071 500438783 998244353
234987801 108274186 998244353
130434554 545097741 998244353
390697210 365340919 998244353
145063248 498558262 998244353
282226328 239181386 998244353
296809897 904454862 998244353
127684268 41286107 998244353
674661093 291235376 998244353
320030778 184913596 998244353
92560479 952676999 998244353
55253119 180546445 998244353
30812789 554302058 998244353
695132519 517189915 998244353
703388469 974859180 998244353
117868168 270053958 998244353
896327490 376709502 998244353
673632190 767149833 998244353
881704834 964880104 998244353
302535903 602001468 998244353
546861009 97060264 998244353
671912025 148983304 998244353
344455096 411219983 998244353
53355848 906949892 998244353
653950149 722415925 998244353
511757107 374955009 998244353
463044908 59330876 998244353
192234027 159152727 998244353
172889411 299328356 998244353
294774001 285003714 998244353
515236887 163104722 998244353
932018058 50222750 998244353
333718353 896048300 998244353
599823310 192971476 998244353
229094308 271233381 998244353
987654110 312395025 998244353
663010848 656290079 998244353
992357741 513466248 998244353
402349816 663823780 998244353
261409511 586869300 998244353
369789943 902069349 998244353
14172062 753661660 998244353
95943082 571827529 998244353
617837612 647268509 998244353
830257029 890038098 998244353
169851886 565844725 998244353
776190216 598197634 998244353
503245086 625559816 998244353
547964489 272209697 998244353
138529390 513923574 998244353
654534785 205615967 998244353
943138496 658568557 998244353
630241852 437709671 998244353
18347837 764150335 998244353
345049736 764563407 998244353
562873877 924757857 998244353
767271797 264847882 998244353
208590218 695763092 998244353
486722998 753780893 998244353
411412053 683615559 998244353
654504861 495572504 998244353
863462759 81649353 998244353
156360972 656212310 998244353
344347487 522532087 998244353
674322957 772754401 998244353
382504813 283637444 998244353
113056838 818598886 998244353
161653117 403319679 998244353
472162214 482206539 998244353
819855435 965366074 998244353
270305618 568219033 998244353
784120490 765660275 998244353
766570706 164475300 998244353
355126344 699482278 998244353
495447045 444955096 998244353
489464749 219112219 998244353
65713591 838097133 998244353
251937582 322001531 998244353
256848551 188960288 998244353
767550036 272345340 998244353
479200957 87352390 998244353
99012961 445287289 998244353
168314448 275664509 998244353
563514901 167159908 998244353
779883195 346397947 998244353
392992668 25760189 998244353
702020838 30079278 998244353
192996196 631509811 998244353
272423795 815534631 998244353
210025365 491905563 998244353
584976434 936207830 998244353
123234176 654588759 998244353
460569576 107590098 998244353
269179541 547297558 998244353
574313044 925044428 998244353
784355441 679223879 998244353
923769665 568020502 998244353
365573722 354787353 998244353
675678625 51127089 998244353
57523374 694331547 998244353
375671543 462603446 998244353
186200699 242959815 998244353
477423230 676517257 998244353
783662211 680333413 998244353
292201635 276548710 998244353
926598897 374772176 998244353
345015913 359835451 998244353
484644311 514191513 998244353
75812147 106726487 998244353
792961294 986069221 998244353
811470504 326844789 998244353
483541822 167890485 998244353
878580049 728115681 998244353
630441652 323511842 998244353
405749267 889386649 998244353
70867570 828112442 998244353
987828243 881979169 998244353
734115513 986794047 998244353
415836684 608512906 998244353
225712447 920571729 998244353
778530011 40036682 998244353
443105047 641823414 998244353
119124429 982571066 998244353
221325391 163891898 998244353
793163035 805231750 998244353
97992718 293525566 998244353
39546955 571072741 998244353
776098692 407240324 998244353
488427067 649107179 998244353
316884442 945783492 998244353
444543766 24383556 998244353
648574126 577182746 998244353
397938019 842501265 998244353
368297355 222133398 998244353
727082060 603229813 998244353
233905817 126624795 998244353
741115301 686285480 998244353
849230288 792349797 998244353
74151035 319412349 998244353
760025767 431058587 998244353
402283708 989951581 998244353
951623217 942880054 998244353
7787522 96318278 998244353
141797036 824698886 998244353
284610016 324189710 998244353
201229468 287270550 998244353
77076299 579587745 998244353
11806335 202688136 998244353
909091606 446724464 998244353
346389051 875774799 998244353
506786030 555523731 998244353
343186917 458821880 998244353
737177059 508439840 998244353
388173401 537904214 998244353
697289446 140344383 998244353
321567162 167271824 998244353
739604997 704612620 998244353
559705514 560600261 998244353
816650958 119129315 998244353
315716520 315098105 998244353
429778464 309576236 998244353
719226127 111911609 998244353
890698203 293353875 998244353
605073599 724820109 998244353
182903306 651402209 998244353
634001180 886580303 998244353
993429671 83052065 998244353
890423862 921250461 998244353
273032776 999181717 998244353
81049760 797700534 998244353
960899906 580958888 998244353
774143041 547283135 998244353
755976733 432350378 998244353
998709381 52630965 998244353
412219035 785236117 998244353
725905096 17940348 998244353
319555704 397193188 998244353
406578863 964729909 998244353
264285397 243856996 998244353
398903836 138192750 998244353
775798178 952040907 998244353
139766927 42555255 998244353
983120980 354637607 998244353
822016968 715987073 998244353
123236486 723820453 998244353
749169788 815937448 998244353
578290717 654556320 998244353
153256330 305417025 998244353
491086025 52147732 998244353
842087012 659078479 998244353
738686662 324940706 998244353
196853892 844563438 998244353
421152620 727595757 998244353
532781024 676989925 998244353
337918799 38453609 998244353
921667613 939183211 998244353
509076112 267396961 998244353
926756361 383999439 998244353
565923289 778615180 998244353
301446091 253506461 998244353
586064396 12390763 998244353
631001458 817994465 998244353
127418462 948760710 998244353
961866289 376861418 998244353
344868689 700995628 998244353
837948064 530851682 998244353
670096313 921140174 998244353
467511046 303845907 998244353
363435738 803126080 998244353
414153414 206085347 998244353
606879792 873465775 998244353
202584227 751458982 998244353
572167891 907604234 998244353
627825851 403751021 998244353
603757491 582561767 998244353
538929085 532514767 998244353
918832442 273793674 998244353
439545813 208706984 998244353
650308057 784517284 998244353
63499080 259686246 998244353
889404673 38090460 998244353
745132770 235645616 998244353
134235085 551615214 998244353
614422193 113289856 998244353
110144583 189393771 998244353
222851359 404385813 998244353
17742111 167061525 998244353
290312090 717898759 998244353
115758646 98534195 998244353
761939082 141885121 998244353
775404672 108358750 998244353
447055924 461909077 998244353
490104749 929540101 998244353
890571488 391884765 998244353
711111526 652668063 998244353
678065313 994928440 998244353
646336495 464605337 998244353
609375769 504389061 998244353
661507256 110207769 998244353
929363722 963643910 998244353
724816031 638043775 998244353
542264669 634463236 998244353
848811704 170548120 998244353
260099213 675805453 998244353
14597411 413462606 998244353
191777371 152629222 998244353
778401429 435531976 998244353
848079839 431864925 998244353
524711881 654388006 998244353
378722728 842459397 998244353
674004065 477003614 998244353
582311124 130496785 998244353
409301425 855179348 998244353
898250815 27643657 998244353
768502103 170437508 998244353
835244956 140741261 998244353
282874134 357330746 998244353
296842355 887401070 998244353
676944985 836878078 998244353
682266768 906940953 998244353
317727664 305555510 998244353
385229877 410794445 998244353
413596785 371349392 998244353
312595583 525802823 998244353
351488546 581842461 998244353
193108793 513172959 998244353
742969097 197479318 998244353
513466672 684540552 998244353
581667856 281666870 998244353
308886926 353283426 998244353
279331980 73384035 998244353
392235728 962276984 998244353
816070716 47319047 998244353
276169551 718888801 998244353
828061975 292807821 998244353
744971877 558208713 998244353
141260723 586827608 998244353
194094446 943252358 998244353
905959970 65358326 998244353
428198132 934715415 998244353
160532221 249299128 998244353
823914025 981118344 998244353
404704422 940210457 998244353
281536249 620515663 998244353
565924034 435329080 998244353
674511619 843556311 998244353
872397059 336766924 998244353
925952432 672152033 998244353
701182368 898111849 998244353
395125956 477218909 998244353
64204492 902835592 998244353
103056075 45460000 998244353
316754519 774717766 998244353
18165494 111285461 998244353
690113157 161806378 998244353
182269284 262075956 998244353
939517373 875305212 998244353
415615129 476865129 998244353
701947666 530261884 998244353
833033641 229045521 998244353
733397390 293132279 998244353
480186135 339716824 998244353
960114322 418090298 998244353
480575771 156894870 998244353
268102167 727480484 998244353
641859318 423543470 998244353
775549946 567829123 998244353
940694796 624872739 998244353
534188976 432894823 998244353
207766044 730050753 998244353
474815408 260996697 998244353
494933045 81449830 998244353
971073125 322360557 998244353
519744743 541967202 998244353
997354483 302555859 998244353
656407788 516330370 998244353
33506266 231664691 998244353
932131618 318648158 998244353
213370101 39511963 998244353
573890351 65352386 998244353
555437698 833399181 998244353
999950187 146843857 998244353
569930289 137108021 998244353
524991054 533187589 998244353
944979618 738997324 998244353
400083704 597809251 998244353
37316259 36161176 998244353
491053045 469690918 998244353
404379331 541722440 998244353
132172132 667553250 998244353
943298810 703102786 998244353
560416375 690675834 998244353
642943558 984149269 998244353
136256556 350360900 998244353
191999255 961634401 998244353
213042967 969692567 998244353
892659049 997465186 998244353
123588691 35748414 998244353
556016968 975983091 998244353
50024237 842461653 998244353
188767486 119626811 998244353
791397635 460587862 998244353
113127673 261448246 998244353
565680427 577967594 998244353
657882869 100506446 998244353
948502219 295922599 998244353
965195635 884480793 998244353
593377270 473570914 998244353
74669237 472369932 998244353
808785330 233291624 998244353
966128928 884299751 998244353
825125468 231390215 998244353
546928945 305921876 998244353
542112407 308752051 998244353
106017393 245157535 998244353
564546573 417932628 998244353
34894532 815036193 998244353
608877724 120577986 998244353
655897903 66919316 998244353
689645237 606602531 998244353
269399628 120871574 998244353
44487597 894559263 998244353
514901843 967867598 998244353
232915852 722799697 998244353
346343196 27297099 998244353
476080436 964176179 998244353
15229895 566178879 998244353
819354782 435864459 998244353
840362267 281184041 998244353
545919899 315806632 998244353
962431831 357488356 998244353
648928609 180031299 998244353
336355841 194137048 998244353
228498976 75400441 998244353
564574044 531077556 998244353
489585016 111677669 998244353
11461595 260081353 998244353
208783720 901894367 998244353
382445488 883192942 998244353
375550774 230799997 998244353
329992443 386451291 998244353
348130595 441109663 998244353
320876101 197577352 998244353
155540460 468601844 998244353
230673560 935363795 998244353
791479583 975232443 998244353
321142871 345360381 998244353
280984139 64126458 998244353
479913128 603726262 998244353
917453573 631638042 998244353
941432199 911452460 998244353
73990283 975144117 998244353
36722761 670374011 998244353
212353694 70187766 998244353
619094713 858278401 998244353
479087663 173023464 998244353
337057372 557671684 998244353
760196002 685265662 998244353
118989339 231032472 998244353
389757267 71849023 998244353
379914549 873131289 998244353
49964074 184329926 998244353
787023735 98497972 998244353
180449832 160212249 998244353
110070651 912719038 998244353
406212392 155963235 998244353
637901680 3244866 998244353
9611948 493936432 998244353
701827589 348063204 998244353
826123612 974896259 998244353
117960591 795700896 998244353
407813943 84569876 998244353
452584810 2611725 998244353
277132776 94992637 998244353
96457191 325034220 998244353
761351604 215097964 998244353
335413396 17904914 998244353
446529241 307341439 998244353
67354819 391065991 998244353
39591635 451098500 998244353
625300851 785395967 998244353
424924584 229345829 998244353
18604129 112605131 998244353
930722335 375120520 998244353
266777004 599784041 998244353
446586182 278134439 998244353
494890163 472107521 998244353
436064367 229006058 998244353
311673964 804624004 998244353
812345409 394252349 998244353
659570032 467555993 998244353
738136526 444494497 998244353
493275233 398696524 998244353
321864047 87047267 998244353
960688052 680724165 998244353
866554511 95161217 998244353
75629141 814337306 998244353
3776284 586946581 998244353
409739953 511015714 998244353
467802009 431806324 998244353
425341654 795335667 998244353
840495237 818448109 998244353
155135801 487872273 998244353
269087989 485549703 998244353
462335130 993482074 998244353
42176726 675091629 998244353
892977218 889017283 998244353
978315325 123833309 998244353
365969421 89979165 998244353
706923528 54471278 998244353
93171431 935933743 998244353
994882576 281864615 998244353
277145756 216845010 998244353
938886903 139494156 998244353
75603613 515021573 998244353
34438996 702190980 998244353
150372707 52635270 998244353
757693432 872319049 998244353
171697723 820366044 998244353
941351475 340925843 998244353
255576788 6254788 998244353
137898968 477057142 998244353
420384260 374006933 998244353
333397217 219113444 998244353
510747719 396295906 998244353
372093459 898980725 998244353
436147482 441829178 998244353
950601441 631200816 998244353
750123729 902914519 998244353
111895213 860752610 998244353
961302668 994914344 998244353
51436440 638234037 998244353
591035354 953925490 998244353
831483645 619094158 998244353
397093576 479609567 998244353
658850278 982160371 998244353
547980418 359848584 998244353
374779445 814226230 998244353
155634182 719633048 998244353
266881150 54782200 998244353
58609363 14362184 998244353