6
1 1000 10 30
801493065 750226211 254903062 253929230 939651848 298908925 846623735 291073217 175188246 788267246 198077559 423132913 812203956 977804868 574062316 675038092 348368680 626530449 904855899 693770948 690931960 20938427 876131999 702759244 592232919 215240460 73761609 436430026 792665734 277838936 39795286 271823647 338047704 129470791 813337802 514394785 416212668 178925424 383403703 553749699 123722012 457004089 285645921 538959652 769188710 478028769 103095274 102520406 848542848 337948464 629805431 869421523 475933505 618381073 942584543 746648527 545081771 377458341 957188664 50300986 162312200 295311061 491700545 626160721 910083236 606665750 522973528 807885228 111618743 449261439 972737003 258791948 581642981 249480139 754794990 834430123 940562046 290261400 710280474 481729964 447850362 605718176 607982350 231070160 773326116 149018681 791253726 89879925 706060803 733959841 542969247 106603951 527111215 167229288 374656408 210064359 409909788 616086275 470465401 890220596 947248519 574479824 620053210 347870075 862198173 679669302 864138655 717675023 338196023 518053245 146970081 267242017 525949235 315075392 838691531 845130336 63470267 65858344 961919124 720321989 171144314 858731919 945471827 832442358 510362955 799413009 821643449 902343927 833859068 964850813 489684494 731253074 69003872 746700700 226509425 362082568 754635392 871923730 834901793 532861380 424570103 917227965 38965191 541075092 141867646 509993406 909161956 837824968 435482371 716137312 53956532 943245472 138996084 698998247 545324757 496963493 728819350 90406564 443803220 848752453 759349417 106654752 532059013 136644843 232458675 451610926 734816400 408886112 838674112 564092100 247137488 455624034 5500680 604111579 84569504 547216784 489129564 693023260 934920433 841351390 678677903 786645686 334427291 62622725 416115728 41764377 449777201 395553756 85267881 441832208 708636297 182514078 172423185 363495861 50759904 655293434 344384172 903652788 663459444 676447583 547282610 23439497 799576967 432376998 158193361 31360719 122371501 675752965 89940809 198436718 77740648 822835175 466518471 655994886 250906921 919390129 105363300 656625697 648175045 282321621 898426993 999588871 635593980 921314493 664062184 341180498 976775406 96994458 931072918 844496711 846756526 635382857 902488214 155163247 279307640 318064758 827746537 37114906 252164380 935678518 81014690 206554484 579836727 358139421 433665877 244523195 895436401 619020268 90840183 882538568 31586400 833354630 637792940 210944786 173541034 119209876 55136701 300381973 426484687 645601117 889305624 101404682 257951262 729070632 38433063 139045888 248344145 454821296 924932052 173268 348243616 645984780 222139787 955847764 133274343 358423161 558592643 778236839 853769591 241343000 845857090 966219663 469435018 266827231 291162034 562131655 636749762 520710379 287104743 958863445 30624262 995705827 939173408 486575420 941048106 749402469 307899624 534093836 406111099 168992997 354641849 167690601 778227683 844740859 877284517 66610270 3823699 995080332 591770495 546157335 104714140 865662306 661893522 60704702 412077601 228954460 939967561 335605289 979441793 431164439 333620764 847774459 908847627 951744388 149252088 835218028 408146837 458360888 611648926 611477713 742291552 417882538 158066330 318983123 953352534 731812824 423594229 859603089 480798345 227070347 79994048 984307654 309492586 96494219 54808184 54043226 29489464 224515148 226315343 235584970 800613013 962113820 242169652 644107998 846133426 501664957 850799409 837618478 954463582 312021111 260857080 418299296 477001661 709798749 287804011 885062736 805137943 730602086 339538111 876035422 190115042 357592848 422573900 594811158 135456610 941120314 5334577 397869990 287118176 779963922 199080169 75701136 642915641 987283123 291191815 365245121 730143556 527075003 480155339 695834022 585187627 774671456 856979042 139161108 481873126 976780987 199234653 317534050 515951324 292861911 666154077 762117606 595657027 216605468 859187275 305589740 92126889 689364549 804494421 404744947 229416284 202226999 319631589 896007903 798436481 244490086 647972474 469668777 607336676 540524346 196500288 483636789 602885600 601707774 680267668 578047732 200143123 420808261 164546034 301933774 213837819 883085699 803784256 291447658 154291908 568974748 225911060 968235156 272949132 83089992 105505955 569177102 434448785 613045468 944898525 534614442 604134814 104421049 338054035 645537741 141496319 375282419 275829484 453768329 768818372 782702561 666048658 483495195 903840400 595973846 203694313 33103103 15513571 651129623 114159592 330663243 45801316 347359846 471354066 428465359 713071892 759563881 422336144 343756856 512723464 713329858 404377710 177946881 193385297 871792373 93573108 913826994 883544407 878910783 711308759 281735455 116363941 610785267 124156648 689746334 443128003 906024319 905193603 585082493 963142463 417375764 732680695 143738181 150627054 52044840 949237179 736698396 259297210 32654986 676520025 902761930 585506909 599636203 445052370 647134693 682608795 1484706 238104823 24602490 75819398 3718013 266771353 75842884 13040055 506327119 437822460 312744481 708765159 764658846 642329899 308996411 538002097 116618908 485719134 490198057 427910976 53462924 412249108 462108701 448439135 209048975 257792780 21829200 154880581 574006196 645733521 911995493 359986584 434775921 191830623 991279130 455166107 534498773 813142983 515955555 865223095 528379165 842175955 314646317 202300014 421836618 618251786 884055545 451839361 974739037 814454836 54731901 814999939 77027735 129055955 254332288 960873134 411626737 719251274 645093743 356453493 498005289 925675097 663872397 665005228 810931798 417864826 724732016 468233985 176104248 676521364 948935009 928112312 665757534 743962095 682522279 687361239 825941414 585469352 261523503 975307604 871090547 431554261 89902122 959563574 295781074 858607158 597940019 476388025 64699646 144105234 29081635 943862051 338989184 636193345 982027281 296464039 564866376 627299759 964240714 969509771 805650889 49711507 913984352 535234154 884103624 631492986 990548003 445993534 685131230 329577499 499528952 948283968 28007703 317516353 318909667 362829524 27675813 524918850 563316087 807650721 450499792 387788592 618560161 819058018 223621432 248272737 881453394 360989328 5664844 415851963 453506176 886020360 625409800 31793401 508883894 794772217 759452294 417616212 442840610 799544069 257373127 949382926 395578863 804868198 269839151 673193439 617136423 499327019 575578576 440357915 469315319 508180480 858015489 4727015 90479258 40805929 374196033 745011786 538747981 768131710 139792251 817162705 917261254 903425982 798094818 474705063 630299953 275099549 862135014 796823324 515549534 946694290 527325139 343945200 259576126 906226845 579365495 157668469 292755942 412942957 463281838 579912010 282582407 849956631 68188336 178488648 761558510 894230177 97546065 791723802 708168170 70489113 710488872 246337795 45829397 988571967 768409031 321825943 953572282 868371590 987181702 367700232 312964571 831440259 184649188 950421221 693102694 605541483 120868289 366253063 112290882 174249709 754767959 470566558 80842269 371210406 389841891 306651536 364812670 248544642 467485703 210887014 68247613 183942144 889495367 673904743 161733699 658247136 944457097 803807324 758583416 642994728 396064836 954233539 361441771 166227089 15120569 724202776 739009600 415234429 95227078 203523752 802180309 489547723 425779762 504590361 527396817 469323475 3577283 444918379 749777559 907316143 834877867 339108008 335071516 212907672 31851519 214177173 629845630 829685214 796854486 950019558 995045163 71514440 469807835 499663207 441833558 577815824 770912326 435412908 246672671 93890181 50075032 817695012 356075701 477532490 982169507 551161944 213829162 307166122 446721105 642553958 243144213 113337583 585526778 368793398 551318365 228193818 93655969 439359998 362854859 471813287 231808731 981060877 24577634 504738751 427355140 379226275 971006177 233081636 876509781 607765018 87385782 586910667 240636732 528443784 393412024 364037149 366077754 620741680 67705849 386276614 82998178 17204463 337283314 809427482 743591892 99060507 494042353 189834135 581294319 845777136 156506993 81864715 773628790 675144616 380074339 960620484 870597644 68166670 993120889 418032820 882087516 696793132 622576884 794346587 30902465 560348755 389287473 430984131 582297859 68279292 917214288 827199675 655434302 265204881 344380766 510121160 487759077 242690217 821011066 551282151 334674813 562272544 811708836 83241889 547659545 913873271 13737980 976448872 404288350 988850513 497828712 157489647 923277109 851973554 62510214 118745811 358779999 487850220 170196365 679481029 671366830 968882864 165293285 539050084 49520008 768341831 29658899 537308063 224290200 850138818 756701663 235111979 809116949 138710952 766109043 164587566 70001525 295514758 769201011 442962237 10736754 52715461 565007742 504459126 430989709 987947578 598315563 254241828 696895223 124902446 824769662 623119016 509749635 795124738 591070387 738192330 767122831 482282431 147075814 351898169 523678007 159600797 502800643 39622597 532912982 390269249 121241352 786006670 287548451 497965731 629145170 697846858 586236595 866569493 423498893 832993202 850326537 854415831 688499023 981303842 617655340 680200730 626665731 885877436 387543833 661472470 190104276 510191717 950970229 227606968 97026433 826465797 388823655 158811463 365978888 632355230 973549703 75281550 122086858 430102983 201934171 705669909 884340789 30755538 682395835 211450730 699163802 508882392 799153557 182811351 683695719 866993532 390639959 63511760 832971597 618281606 528961364 409688178 575271567 210408640 669316446 990940272 77694950 278222986 236379790 352128381 275423298 555994523 790161927 242243679 730406638 498986068 945524091 751256485 849677424 109657386 402712411
176999631783