5 100 6 628639239 562113500 959540940 533034917 815136346 122510228 407738198 376150090 95078313 638585319 881688196 948429743 213541028 674591721 720696534 431786506 800006845 349801235 942070227 430154806 993482925 305784255 846313602 70569010 271940845 73031599 652838385 861447582 748281918 853689479 992022962 680238657 566792738 982528590 743208025 797500037 551919456 537108465 421936639 303441401 864987267 156684224 452645570 928319438 294092892 304903151 13783363 660052315 269457532 858118423 411482918 691120282 612891579 298492082 332434837 80477352 197394612 756087202 866425278 858325064 358060614 394830506 27679056 996894305 604630548 817454835 982274818 453302396 725337350 703334025 44563213 996739399 262571462 307514076 470867372 225198356 328957764 724511552 269845411 651503194 434746163 2318701 247180470 591166515 82570377 994327039 537931309 558152925 573295619 83938551 756837718 56194105 504230047 397511224 632236035 965294159 487022623 687127563 236550920 111333320 100 4 183201373 959293013 339454833 111875512 980262517 946340266 587950883 505028321 991835654 926392419 982470736 951363968 402563818 17342722 966889677 607092642 134819984 62100412 522209089 209604166 710497399 274736382 565995943 983366626 661244598 110838757 763522512 749591263 76762743 115956420 625100766 880518680 35854967 444820898 281950922 157401951 558018952 732312249 706206432 287738873 3275536 856262393 131363390 767819036 577175944 564540546 446354776 833552504 685703421 553502510 23197559 367172267 383369105 365879044 414430005 788924875 825300987 435558086 455932674 42366945 954144771 605653604 194476963 464738152 100509447 863348615 577973933 958465490 814577274 271464455 846199054 393530883 541372511 867433589 302016389 693461716 733501394 200710802 147246373 853828497 413902719 364214230 143767510 873449084 489551401 36578282 459702484 951605064 999607077 565699886 492890926 175239582 309845724 571339572 187314248 490604955 381388621 870368067 400692313 820110416 100 12 241967544 226873926 466753978 586579126 612185118 790525329 410533152 782367411 889664956 803917347 76378005 183468184 229962519 142998078 503115743 173097913 513076057 744770922 647167402 482475760 966615761 461269232 802784264 750444313 885324656 742051426 831443948 147017622 486843212 845894673 570522286 930535627 290455840 123682197 816025738 671516323 248403146 960728138 673363232 970702601 997149132 834125773 670280182 408975472 892385229 489858178 976191729 769230412 567666965 193778705 802792672 201806743 593533716 855107045 901929969 440457549 447908571 439052716 343489594 841784560 40797601 31056346 324501553 978327300 266012991 171927589 47164212 247240596 906570933 989940234 992640515 680617643 869290659 204755271 221582145 919897820 100884432 195505759 280161782 251953595 341032871 579019033 842567695 551999586 456891061 69551873 41657565 959228909 961588525 626160102 636139410 354552318 421417316 870715994 794364359 160075066 768954453 995287094 935144953 290999241 100 2 155673326 354058860 293400378 216490237 803338746 629083585 975990551 574410394 259893475 117459524 559956811 101827242 986406984 226361974 427484059 924751334 355947961 543626470 957538819 9443930 928461881 729601722 73205552 538843620 713521347 421412396 981604615 66406072 619267266 360459531 779429660 101663198 650688151 343146806 53124924 39137202 376079894 535043365 506905572 284614756 460989193 153587296 877946055 32815222 784667052 567152133 17970507 134212929 596823855 267257670 96574220 434700144 101543992 721735145 874608216 75270018 804426078 841470150 905540274 943533132 467889583 992586317 293379408 223514997 592298282 295702781 533699485 446074873 600416070 361157614 799190455 625128103 290036586 345117512 212449010 396946595 604886898 521797834 6986835 528800228 616635441 745429060 52012821 570140087 428434409 765261853 409185576 837752122 828959956 330875341 399780269 804334050 74220447 894598244 165576571 96213493 870268394 157773058 618011549 735674641 100 40 836268537 662705641 699945990 374225825 850096553 610608754 988467505 806149721 697265218 253328318 58271376 987862998 412032745 742183752 139456121 953662739 920728137 833322414 487046920 401225328 419483918 753799474 15340189 643239474 818706025 317149753 700800602 409957120 261619343 238320591 574205606 684114535 368926522 113513506 361654188 824261463 148241958 134034691 263115741 768393893 960077717 402267752 315742826 97609607 697936588 799350508 830207946 869347355 92467348 837162574 248410682 96841184 64022969 356185582 19957304 388418106 729633166 274071891 215827208 752919282 342924392 595776679 61359919 236832436 985046559 84919097 804129530 444226448 729225360 538100218 75076856 904250746 199840285 400525313 732854908 243036362 430770219 452636423 903125532 628659389 459959714 707915244 382902325 472738802 755974513 233719600 973778276 966978285 113630984 63965050 750350606 640443543 523774685 718556181 132776921 291268284 229710568 99642734 603733041 976520332