1000
192279220 156648746 998244353
154396384 640494892 998244353
528756313 434883274 998244353
318065816 264440383 998244353
659789617 608119380 998244353
648104885 725454492 998244353
696703871 543030428 998244353
663661240 890791532 998244353
108201616 428505484 998244353
322953840 119811886 998244353
691103780 306647414 998244353
549862302 176916719 998244353
909058872 455464665 998244353
307270851 584469329 998244353
722629343 875317523 998244353
629938577 244419357 998244353
781214570 196670271 998244353
304620505 633084214 998244353
842804669 567530398 998244353
381873603 560028831 998244353
7218487 861789186 998244353
144376610 625456810 998244353
780877708 589558486 998244353
134166194 414950796 998244353
721407802 553010676 998244353
955308711 381588618 998244353
132249152 739990894 998244353
349655325 541586881 998244353
148171212 459480021 998244353
458194371 711527040 998244353
805750859 225659487 998244353
923622442 616919641 998244353
541627396 189845338 998244353
545052260 705924883 998244353
701326768 360797562 998244353
153907111 153703898 998244353
312119365 610379669 998244353
633051911 179752937 998244353
356035805 857066210 998244353
510023590 487449327 998244353
911192541 522937781 998244353
366865480 175671834 998244353
3720977 958798378 998244353
537811758 487222100 998244353
451715495 514312094 998244353
913636469 134561869 998244353
695564571 532291996 998244353
942581882 651125279 998244353
371623643 124409048 998244353
63074408 599149591 998244353
243222914 423151881 998244353
252728018 259733480 998244353
643176869 401033745 998244353
139381337 251320507 998244353
149124068 414594572 998244353
331487169 269144629 998244353
189437147 248342016 998244353
963352506 406539487 998244353
845833860 755591984 998244353
896411912 346209706 998244353
599986363 192576280 998244353
339470264 91311827 998244353
674221023 82572049 998244353
432342320 906953259 998244353
996236455 898717035 998244353
293935164 823871256 998244353
241618061 426188561 998244353
552250085 602446372 998244353
326439606 36819590 998244353
716162336 182538448 998244353
877980488 234609344 998244353
970639970 96912084 998244353
154071710 720041811 998244353
241584076 888321423 998244353
204059421 444486812 998244353
306061338 405953440 998244353
718697235 185635311 998244353
544659197 175477372 998244353
385632116 74114210 998244353
281221795 749035961 998244353
69575117 403681059 998244353
477587442 276294863 998244353
344958618 247221529 998244353
256653851 88799826 998244353
390143235 215677770 998244353
69615947 421663553 998244353
829251359 473970282 998244353
477181978 395005915 998244353
204518013 819349760 998244353
65949542 849289623 998244353
779931867 351133755 998244353
458419082 60835260 998244353
97550049 14347775 998244353
568484556 889658732 998244353
259645749 554047063 998244353
633917839 869082275 998244353
25145201 819042066 998244353
236424237 62605193 998244353
647411618 963213705 998244353
550125446 754369251 998244353
97791695 503316297 998244353
263982839 622206694 998244353
583095008 633551381 998244353
82619260 28565500 998244353
11547032 546769678 998244353
794174955 544258177 998244353
607157916 974478438 998244353
105432268 44562564 998244353
650759971 725160370 998244353
205744622 56560140 998244353
163959670 788812018 998244353
759517420 870450851 998244353
786197015 332668941 998244353
280884396 896616998 998244353
354325646 78199529 998244353
380937487 27828123 998244353
792547135 344979556 998244353
606529987 854248606 998244353
694655264 98844756 998244353
675361364 540932136 998244353
720653471 638568586 998244353
259188591 477025351 998244353
199659791 923181961 998244353
932329452 657848015 998244353
785316591 876288044 998244353
568202699 711859964 998244353
835360370 264697884 998244353
888333016 729753828 998244353
973849297 368415357 998244353
195626384 789440908 998244353
599511875 6405002 998244353
933416558 56060135 998244353
326810208 692565033 998244353
898701471 315946986 998244353
911332404 784951414 998244353
556831370 37285994 998244353
754591963 89276725 998244353
738593187 993973134 998244353
784935039 181217910 998244353
778665738 994337227 998244353
332058127 762456137 998244353
24400815 386891485 998244353
904050171 182407666 998244353
636003294 108423720 998244353
375403884 843008606 998244353
967930132 163815973 998244353
457948520 638332658 998244353
600592575 963917028 998244353
156722719 359729359 998244353
560390518 235226467 998244353
568069676 797782114 998244353
239098408 685400425 998244353
510134242 577467057 998244353
50978805 752028766 998244353
164889532 217280532 998244353
710088559 522973050 998244353
850448894 695807095 998244353
512732493 744621933 998244353
765043644 5572719 998244353
749446521 370336434 998244353
988285030 981229809 998244353
180999313 787390629 998244353
687572860 811799398 998244353
791821786 162447801 998244353
552007489 767002401 998244353
673284106 246463401 998244353
802742188 157822377 998244353
155385500 806266306 998244353
219727203 683743955 998244353
593913331 353321718 998244353
367144078 404043218 998244353
95990639 981617024 998244353
76965015 480476399 998244353
888827418 996998470 998244353
451741021 505811216 998244353
175718444 336525214 998244353
727121309 700275843 998244353
466233564 300170578 998244353
450550346 983917278 998244353
806337609 574319764 998244353
862578965 528527440 998244353
80741174 433952228 998244353
948356384 483602916 998244353
110481351 360912431 998244353
716293557 408395904 998244353
975980920 201310302 998244353
856922974 866803513 998244353
952671462 379464049 998244353
19340824 131379259 998244353
118844757 727214231 998244353
593398051 332310973 998244353
660656054 563298067 998244353
965893603 826781249 998244353
169725638 623612468 998244353
142394566 509185528 998244353
613787528 889856071 998244353
889200711 454786811 998244353
115186977 192402414 998244353
56222204 263923656 998244353
390546876 953655006 998244353
216442068 217298606 998244353
919899058 843904262 998244353
903158972 20051664 998244353
485987173 741840499 998244353
30052410 482019313 998244353
853044665 225880642 998244353
348694202 778235197 998244353
258285782 384092381 998244353
866266220 882003969 998244353
364669393 443811758 998244353
990976337 256754480 998244353
191813218 906988660 998244353
500055849 942895402 998244353
655120522 746453207 998244353
881011221 643999571 998244353
344763659 856823540 998244353
776963780 292684135 998244353
854968295 499252687 998244353
766554125 290065702 998244353
3996941 576853977 998244353
871885396 742091261 998244353
834056713 156134329 998244353
828218675 177743881 998244353
393648806 283659587 998244353
253754843 187850026 998244353
863335112 7836256 998244353
54524480 637801774 998244353
33448391 777909553 998244353
119086713 774437681 998244353
566315030 549859515 998244353
937142966 72805571 998244353
535999829 106597600 998244353
705738351 537686293 998244353
991633662 698553902 998244353
186304138 770200706 998244353
993970423 860312486 998244353
438703962 332779127 998244353
115921192 851511173 998244353
447963123 313740650 998244353
460526403 684368942 998244353
100922947 398047100 998244353
573149773 416271313 998244353
459698572 197822958 998244353
682461439 972237693 998244353
310667099 325551420 998244353
120649948 481833527 998244353
134347178 214392111 998244353
8142692 337442283 998244353
284108799 593105379 998244353
370738803 705438259 998244353
352988443 270146933 998244353
58754954 555701636 998244353
462029673 452459592 998244353
308797553 443252150 998244353
873227113 338522359 998244353
377179609 702718479 998244353
911859660 876435283 998244353
717014585 279290297 998244353
111602234 260788208 998244353
601004929 906480973 998244353
805247349 322621782 998244353
678137338 564670127 998244353
797337844 621334574 998244353
99678642 355399364 998244353
400446956 710870139 998244353
37116959 210364435 998244353
800081944 313741470 998244353
253001775 792937040 998244353
164309297 455246050 998244353
887096772 141317752 998244353
814946362 957356140 998244353
481685112 750342074 998244353
883786334 869032217 998244353
50127022 660073647 998244353
76052830 292917825 998244353
10574670 48693590 998244353
526945681 714900352 998244353
44232028 202084007 998244353
166197938 95995740 998244353
341945489 399061487 998244353
78143284 669578165 998244353
924924837 136431237 998244353
189986488 751880184 998244353
943934691 874965297 998244353
357525861 382249882 998244353
688272446 510008719 998244353
911794180 397712909 998244353
855849113 322380958 998244353
928083339 961481039 998244353
362386983 992059188 998244353
499432460 598315995 998244353
799730843 805105450 998244353
539543510 642981871 998244353
374565666 412114382 998244353
808810446 775163486 998244353
738962011 821298553 998244353
567831822 149471018 998244353
329079065 521221433 998244353
175469751 425710284 998244353
435891352 474348188 998244353
940665860 306488085 998244353
117257540 631443539 998244353
30515320 624824684 998244353
950287212 220526650 998244353
150080689 559167220 998244353
458600897 379655987 998244353
89467028 105922509 998244353
281689701 547580917 998244353
553349954 363463478 998244353
350131284 634609869 998244353
646336728 709278192 998244353
814749953 162810808 998244353
685184955 463222523 998244353
902127715 268301282 998244353
131047254 842900648 998244353
589121210 14832332 998244353
629898748 67277966 998244353
175309577 658555203 998244353
58123355 354151062 998244353
558792930 903896941 998244353
876514640 501212618 998244353
816465456 228127237 998244353
931074840 841137513 998244353
287120195 795895896 998244353
98268740 785104745 998244353
555610857 43082330 998244353
769864306 704357619 998244353
484656339 41403223 998244353
858756492 602689028 998244353
493083361 239342127 998244353
754317102 594272498 998244353
562926440 622267958 998244353
548145967 83150379 998244353
249394874 401767148 998244353
754862685 471122517 998244353
222925575 257098825 998244353
167725286 510581431 998244353
563067320 358072894 998244353
76774585 871200174 998244353
205432410 94407660 998244353
872259935 307561716 998244353
744265362 799945399 998244353
739415999 315925136 998244353
473326365 662932794 998244353
3826792 255007173 998244353
859919832 695629691 998244353
424439046 723459843 998244353
757796288 716355287 998244353
940797767 420975804 998244353
176738587 683565708 998244353
964135096 503007916 998244353
246969222 603970731 998244353
91326269 128335809 998244353
636545951 906169138 998244353
237116437 507430597 998244353
512501527 501500896 998244353
365970653 815551892 998244353
118295098 559555237 998244353
140358820 488892788 998244353
935591390 967161676 998244353
263465866 547365544 998244353
521766572 40228036 998244353
634044716 211921935 998244353
199098652 958157530 998244353
273501230 773263914 998244353
349059615 151384939 998244353
180494173 693133521 998244353
383924188 746293521 998244353
1130742 412483339 998244353
884733789 511944621 998244353
56794723 529905378 998244353
626671571 474523998 998244353
523498634 260253481 998244353
128828206 246629295 998244353
509065323 78061514 998244353
899450083 127160113 998244353
399243105 34823060 998244353
757581439 265610777 998244353
783720083 81741852 998244353
983957577 547027558 998244353
128461669 400855851 998244353
841963269 763522948 998244353
524609980 133063463 998244353
752000660 721315491 998244353
436160969 372798560 998244353
418357541 750932767 998244353
472002399 100787292 998244353
368396442 427657485 998244353
515971495 206273974 998244353
631373248 823903730 998244353
240236285 717183311 998244353
712740499 325855784 998244353
123161506 435949678 998244353
755687436 469802856 998244353
608964294 265367081 998244353
714937308 383022513 998244353
921343022 125761063 998244353
658765597 150219478 998244353
708222101 957042181 998244353
374499414 656830068 998244353
85581493 277882372 998244353
730059918 927797441 998244353
502521247 330780039 998244353
878737293 480260771 998244353
724336724 567479253 998244353
294997728 906201314 998244353
158428822 199662339 998244353
954855701 426005213 998244353
632497704 382550400 998244353
888216225 516605481 998244353
303479737 188114072 998244353
863896784 52703792 998244353
231739502 351945716 998244353
274277599 365861467 998244353
785704148 665905944 998244353
517633950 932595006 998244353
992962367 723393017 998244353
359186438 770561548 998244353
273035649 202871127 998244353
477390879 767972790 998244353
34365977 550386264 998244353
805731741 493679141 998244353
786266654 272831912 998244353
443745087 217035605 998244353
2449442 286650748 998244353
59468504 936140024 998244353
139310064 919981633 998244353
553417747 937472592 998244353
362256448 514707656 998244353
583510187 331953246 998244353
157262573 542057154 998244353
241844986 121364543 998244353
8955615 685640886 998244353
553472621 154689880 998244353
654393434 497122870 998244353
728248665 2348133 998244353
827652049 872841175 998244353
835498479 194119011 998244353
995991089 282779140 998244353
162377123 513212966 998244353
139801025 242294287 998244353
241344683 256724567 998244353
791479581 764123104 998244353
808450545 734213391 998244353
92167353 295491098 998244353
696086077 464540046 998244353
115285157 671417335 998244353
765370976 668988066 998244353
984432324 415821703 998244353
332380990 261912943 998244353
367831824 523454974 998244353
582729418 583057157 998244353
103794002 984764356 998244353
311862225 270998498 998244353
669033508 739516186 998244353
761574441 666159799 998244353
945173597 982323061 998244353
534921491 826283849 998244353
530039637 396845000 998244353
367781535 888044245 998244353
112401954 629876537 998244353
420436935 139184679 998244353
637157194 606049421 998244353
703785710 976149807 998244353
912533890 922537901 998244353
569280730 954422487 998244353
819817874 465308629 998244353
476233342 584463896 998244353
848290570 553683157 998244353
456101255 856202925 998244353
989781586 693396101 998244353
439027134 856124868 998244353
123194260 584805911 998244353
320208434 756008602 998244353
373924152 929798062 998244353
677015561 421018259 998244353
50368590 623572337 998244353
203940996 103057027 998244353
239198736 508049638 998244353
104342504 310853922 998244353
113252986 944635098 998244353
135164745 513269418 998244353
918552949 410981779 998244353
385895600 722031859 998244353
583110434 543667217 998244353
841421379 238361441 998244353
223700714 890286355 998244353
401834255 692531391 998244353
67493542 11842635 998244353
713645329 581971736 998244353
976546504 95049090 998244353
980640035 743284383 998244353
207837745 993167071 998244353
209005718 857385467 998244353
194979602 573390965 998244353
595010493 74073361 998244353
295475938 418002823 998244353
506585160 332911131 998244353
972518853 866206243 998244353
167976044 303138913 998244353
884720018 721224867 998244353
591394765 553671443 998244353
218631293 370788288 998244353
990547098 228560740 998244353
58650734 118176142 998244353
47201281 146594371 998244353
70553137 439715589 998244353
718726700 414262154 998244353
592933913 739758408 998244353
619795593 435019886 998244353
512935103 898747808 998244353
728501408 299352457 998244353
630371684 290141714 998244353
421869537 920169714 998244353
437738227 162405767 998244353
77599928 646451262 998244353
88752540 395793380 998244353
492544839 214849554 998244353
228943378 343654680 998244353
827983491 275912146 998244353
957359627 309540280 998244353
593371425 294340139 998244353
294402597 968501955 998244353
521608226 760744527 998244353
797074140 915885648 998244353
977601398 409242716 998244353
538733907 297066999 998244353
487859750 683929095 998244353
636425184 194012695 998244353
667620248 845663344 998244353
116804548 53190451 998244353
159241784 117849961 998244353
314481379 299687377 998244353
243293724 388065037 998244353
260221331 464442668 998244353
502695401 784194755 998244353
638463959 960584700 998244353
430109397 29960196 998244353
847099296 466371140 998244353
7255278 83629503 998244353
397721664 500988902 998244353
255576463 979826457 998244353
93001057 704852403 998244353
242382124 936827179 998244353
514670152 830716438 998244353
834970520 163631244 998244353
950668349 842668116 998244353
657897256 16452949 998244353
46520422 819290383 998244353
998602071 198926195 998244353
311209297 355659362 998244353
12032775 17912802 998244353
803747911 473675354 998244353
760840502 338698318 998244353
569342678 58754979 998244353
22308373 846921918 998244353
872013297 366373593 998244353
613003307 952388420 998244353
848991234 156105967 998244353
366478531 493100254 998244353
346496303 114555289 998244353
639691010 74625394 998244353
754440001 263711709 998244353
248991088 288370038 998244353
151566900 973978218 998244353
696903946 433095979 998244353
386213578 131623773 998244353
592869589 423122791 998244353
159898471 64813047 998244353
113659185 163792827 998244353
25015857 336523722 998244353
984007222 823671606 998244353
679280113 129669266 998244353
136987917 675164475 998244353
754349826 733537686 998244353
372704445 224587173 998244353
756698955 892509733 998244353
865133509 722047263 998244353
994685969 678352533 998244353
392290290 157403067 998244353
278667563 233824669 998244353
857313198 506983764 998244353
610609597 245978547 998244353
57378030 196697484 998244353
684451868 730717647 998244353
568390239 579476017 998244353
938494856 366104980 998244353
868518932 954445889 998244353
895316965 728405043 998244353
818475984 281173735 998244353
843816722 722031907 998244353
269305089 76671054 998244353
424233075 631414868 998244353
627537733 977021059 998244353
730527662 910873619 998244353
174722858 816879693 998244353
194854216 25537708 998244353
17415336 710804834 998244353
442014601 16897257 998244353
701100030 188960038 998244353
842611355 702451878 998244353
593791949 668586235 998244353
212367895 727056237 998244353
183343740 295644895 998244353
269894353 451181442 998244353
845929042 514900193 998244353
836900558 165956398 998244353
617892719 966563741 998244353
842580909 649917178 998244353
769501529 186631874 998244353
730129551 175579231 998244353
838585159 166154425 998244353
753938858 216703115 998244353
660986677 502741377 998244353
958132876 885747761 998244353
820781494 619530247 998244353
843712361 615782715 998244353
617326581 535578088 998244353
945424168 676515154 998244353
339805571 771136768 998244353
413371084 135180953 998244353
868153135 281168886 998244353
661733162 475686484 998244353
629145088 553638543 998244353
777928744 51226323 998244353
436078198 725741166 998244353
298959993 797289399 998244353
379600 93521364 998244353
292971908 450876698 998244353
481186980 422615121 998244353
62877798 307389038 998244353
678564186 179123682 998244353
615825315 214089691 998244353
115353634 632101163 998244353
755114848 803748059 998244353
987107433 264039153 998244353
596583530 448368492 998244353
271047782 124994222 998244353
46952281 882846376 998244353
268697650 334155404 998244353
839782562 119002173 998244353
438604084 797723824 998244353
848980692 140611927 998244353
211696929 206301252 998244353
669747987 61880418 998244353
112886438 557525751 998244353
798913344 938780069 998244353
887021661 759217003 998244353
346471545 223351514 998244353
745734154 404493577 998244353
79125178 196132276 998244353
998498175 423235045 998244353
296208283 171047238 998244353
289357191 378877135 998244353
692524873 777984013 998244353
882580394 38750166 998244353
812091265 845955343 998244353
246240803 774063449 998244353
520714355 282137368 998244353
659726788 922719144 998244353
151340284 525536600 998244353
847909050 327142707 998244353
681682131 584498240 998244353
720198896 723137805 998244353
808787321 473408786 998244353
935413898 580170546 998244353
410670778 716252067 998244353
206153711 868306792 998244353
394463539 542409636 998244353
845005514 757429698 998244353
346524800 664699983 998244353
324983323 860373216 998244353
892505337 757306633 998244353
289593879 147609453 998244353
624614534 227052668 998244353
297901387 617351809 998244353
542344995 214856123 998244353
343448931 569056562 998244353
161627713 692806751 998244353
497984913 605711720 998244353
98512744 914446915 998244353
769716981 355980693 998244353
651910262 492354658 998244353
342672554 487623275 998244353
413475644 293931297 998244353
211486158 940458705 998244353
206114387 628302653 998244353
782869044 938442083 998244353
174872769 60933775 998244353
615517880 624975271 998244353
720386982 933975310 998244353
825396219 335893376 998244353
261831920 525998013 998244353
701297184 275516956 998244353
419304196 616733872 998244353
52170814 627859163 998244353
848987243 685740522 998244353
990894775 747941135 998244353
389090035 133160456 998244353
351368484 185684018 998244353
412853328 879330265 998244353
48309296 980772433 998244353
810043261 686513512 998244353
847132257 820611463 998244353
721538709 934885802 998244353
987531325 261931833 998244353
389991369 635753907 998244353
436433939 325399853 998244353
280466471 773462767 998244353
804168103 382123957 998244353
792345868 146951961 998244353
705986348 724247821 998244353
612159517 369568749 998244353
248223203 14521718 998244353
894164465 458411097 998244353
358568646 807295782 998244353
911630786 537119632 998244353
137333637 126433355 998244353
752464428 992465133 998244353
838638087 865014306 998244353
802873804 371967167 998244353
611177238 147186191 998244353
107509812 143795143 998244353
368551537 912629603 998244353
952814339 174286295 998244353
790084208 213921269 998244353
951406765 20167108 998244353
172864266 758435080 998244353
540343901 880689082 998244353
424421644 775485426 998244353
623928127 215979634 998244353
624251249 884890810 998244353
354677746 59996599 998244353
83781220 698181412 998244353
910628517 321330857 998244353
958206756 423814263 998244353
180067042 967626138 998244353
955700463 8697445 998244353
988264498 73029146 998244353
453400682 895551935 998244353
634815714 800168514 998244353
241283440 583577526 998244353
381307481 987505463 998244353
221545347 65065115 998244353
701315856 792266878 998244353
526723412 158344372 998244353
116458906 70636283 998244353
41493372 655601891 998244353
433121420 575476650 998244353
864225355 369696082 998244353
873016060 139749234 998244353
216039507 650970632 998244353
328733331 206806193 998244353
577201641 172161618 998244353
12966834 12972153 998244353
82717522 947965863 998244353
926185494 139459877 998244353
590614410 983188553 998244353
47876368 86281228 998244353
494645627 806805168 998244353
971430607 644568767 998244353
982284936 495312827 998244353
515528177 284738276 998244353
675841424 109722287 998244353
764375987 897614143 998244353
496190978 16773534 998244353
279060940 825538559 998244353
900505544 635161098 998244353
863658280 827630001 998244353
590101169 278267073 998244353
310407379 12504622 998244353
973607832 347441887 998244353
890431002 447895843 998244353
715913106 564359281 998244353
849478393 9734490 998244353
22232683 128356032 998244353
326611991 418782708 998244353
302494873 614711112 998244353
9190167 213464123 998244353
311752217 206716259 998244353
682724777 490757921 998244353
966380011 294934454 998244353
893575380 76400961 998244353
478739726 291742984 998244353
343946942 198189793 998244353
904267069 476578409 998244353
360703165 969432512 998244353
834623710 708024940 998244353
340393867 48835147 998244353
40741114 958965085 998244353
915226783 238176982 998244353
562569207 606472616 998244353
613591992 676833983 998244353
650387526 921745731 998244353
533471613 362176920 998244353
813538812 641763178 998244353
548596896 437633171 998244353
561454977 457897063 998244353
275003453 401703828 998244353
856109035 736974357 998244353
173308920 88561269 998244353
640065035 755828912 998244353
979655180 286634328 998244353
579989015 133855449 998244353
178630833 602713305 998244353
310103602 515722731 998244353
213564592 49451500 998244353
807549652 554891236 998244353
602449451 383781161 998244353
743228844 733609649 998244353
609481339 52745782 998244353
635197739 395675398 998244353
236261432 437687400 998244353
400245116 550011573 998244353
339365524 624686376 998244353
778047029 264308827 998244353
546209414 22006893 998244353
946807349 332436642 998244353
332323826 446948495 998244353
963700320 760921403 998244353
63247979 27936023 998244353
428594393 32337899 998244353
849269316 701462380 998244353
194996279 958232179 998244353
857032393 637512136 998244353
858113877 660991114 998244353
109427013 42846403 998244353
88447237 415667957 998244353
118896138 568944327 998244353
386185815 739913589 998244353
109856310 42891462 998244353
895664984 380499820 998244353
195271693 624672390 998244353
218836065 93200008 998244353
766861752 754858785 998244353
401163348 258927082 998244353
43474109 406474909 998244353
596987305 597224177 998244353
125955446 75010496 998244353
185750524 960073156 998244353
771301759 328026492 998244353
313499366 820239687 998244353
336612840 647543363 998244353
266373729 182219185 998244353
805203221 79422217 998244353
986984582 234122404 998244353
609219617 720235532 998244353
229654215 234740949 998244353
100265362 611299396 998244353
962993122 605810359 998244353
857180456 679584947 998244353
588036195 270366677 998244353
638815740 481242804 998244353
11425095 346037575 998244353
910075946 531409925 998244353
33601594 236900824 998244353
439853040 519917056 998244353
414261109 673692988 998244353
646660653 212403589 998244353
382947467 143402417 998244353
60075011 183558668 998244353
971285502 400633676 998244353
651059786 541241760 998244353
960775328 680392360 998244353
814544865 797841398 998244353
832725788 698118699 998244353
140916152 976213973 998244353
427009612 415813750 998244353
38258004 38666095 998244353
936939322 275005613 998244353
652485179 804139024 998244353
429334207 744161872 998244353
254885339 372312931 998244353
504612776 158226292 998244353
143354292 656687483 998244353
465093473 339661812 998244353
48484981 801994915 998244353
185682475 21912377 998244353
108904306 77678615 998244353
995907892 357712170 998244353
860828216 327792961 998244353
191946834 712444495 998244353
34266354 118660875 998244353
368195809 351234597 998244353
446600784 894873789 998244353
433077910 600343934 998244353
844668197 844649080 998244353
272416531 824833060 998244353
777976253 218211790 998244353
401705326 985430749 998244353
319682048 489365747 998244353
853987246 625807734 998244353
222663097 344295376 998244353
226053942 635214986 998244353
331850016 761629800 998244353
607110828 99128190 998244353
823734783 662470657 998244353
521226208 777503450 998244353
611316960 313931437 998244353
180399077 439663555 998244353
794060124 781767899 998244353
33244118 167650408 998244353
766771992 874470317 998244353
388793988 622328764 998244353
375059426 161474666 998244353
7614490 578654926 998244353
479181691 707076025 998244353
845961551 250234865 998244353
380076552 995253532 998244353
612437394 692623546 998244353
847063689 908199966 998244353
415271389 741117138 998244353
601380123 798922392 998244353
19140028 1869279 998244353
410488553 622117271 998244353
186777511 334517816 998244353
327411919 271891120 998244353
241493339 638835967 998244353
828852272 826438188 998244353
308576532 321730512 998244353
558283668 95334675 998244353
648031044 981758535 998244353
269917683 31761010 998244353
821052914 978662587 998244353
307083739 233414231 998244353
846606304 355347740 998244353
85756438 137214568 998244353
110454403 847686446 998244353
410209229 101281484 998244353
695672755 704062872 998244353
198410001 673430734 998244353
859682892 754137461 998244353
93725081 105560102 998244353
166898435 737927447 998244353
994493182 651768624 998244353
561762117 190344760 998244353
345231088 831057368 998244353
812264343 494220169 998244353
937974245 995450648 998244353
710525545 555083006 998244353
193455280 205915644 998244353
70387972 732085354 998244353
9463002 616501479 998244353
710765806 704316133 998244353
842011624 218307924 998244353
54475697 619027603 998244353
942774446 228967030 998244353
210107271 93957337 998244353
853836180 50815249 998244353
243046009 531785124 998244353
611189756 84670722 998244353
779340056 132902880 998244353
40143865 565598975 998244353
949969114 768636921 998244353
56117027 426857489 998244353
435054496 983193390 998244353
280122816 891226688 998244353
958529371 314823253 998244353
152464544 827768594 998244353
11735852 75875806 998244353
595195418 359053834 998244353
641211078 678914603 998244353
986129225 56961015 998244353
716883594 265356613 998244353
477145715 768453397 998244353
997496381 958534418 998244353
870823184 231095802 998244353
194475700 16696012 998244353
686703230 222123222 998244353
152050572 652697321 998244353
963776350 400353968 998244353
710412443 872946713 998244353
391131971 48485842 998244353
948556484 741174092 998244353
360582588 544455133 998244353
315064541 626036890 998244353
424455068 69648874 998244353
100155046 447922488 998244353
107474494 416917576 998244353
364737758 875201343 998244353
177259386 471749791 998244353
670078009 719691499 998244353
681627806 982182998 998244353
496184545 655296288 998244353
707867104 855784246 998244353
540694565 264205521 998244353
177562124 825851455 998244353
764776232 499582749 998244353
976573944 600299891 998244353
426283881 634913343 998244353
759168821 499436518 998244353
895503738 394337771 998244353
213882878 67663339 998244353
564588950 285233912 998244353
644053803 366007475 998244353
733342521 63434043 998244353
537302960 217056407 998244353
622851483 850318426 998244353
575299121 75500991 998244353
971700904 650776893 998244353