7
2 1000 20 30
381795011 697888205 432902592 886780652 62496617 545580139 646470861 860938978 374810496 728773678 670122625 728124606 173987984 692464723 259406048 872734921 592196228 558518585 843349354 512266194 947997109 807129263 531649165 67642623 782358694 122998128 264886387 906368266 518126703 769901490 444803955 58765119 878807469 262589035 336034950 448758937 321554378 438323914 775493723 199680248 249582142 28918654 637261094 415213020 766809675 567969427 990834229 457698838 492009925 574990200 309447479 586285449 123597095 447672505 736115066 746768733 593341416 257229182 254696261 367635143 207110851 157390703 609750205 424308723 771219728 199566955 915016662 879057436 636319531 652808429 39442224 829792413 109645873 831231629 375269721 308739251 214158992 141481373 964765455 436114246 772465664 352221285 660136423 567098922 762533376 554818119 609678195 117713236 21261381 855546384 898806733 439342162 302020372 610775928 205269368 211695 478763207 991007756 902771429 221045810 434347708 166066166 484831718 407888097 536415470 272234765 206076733 218771270 270335484 774099268 428058036 147809781 849007964 203695351 52961170 970196671 808967220 635108114 861372087 777844662 438586283 260770011 574216584 428562278 573789847 107045095 630399108 507260595 360923386 546085257 643356520 496676535 127917965 681232319 222263057 99995244 396796004 921394826 600700511 864457331 493540856 639974146 470637781 913996842 807316730 198687125 575871683 17342097 816104590 471622202 600412728 974531582 607422055 481483457 125848926 693618463 559559522 200269121 256131247 720074439 704244128 500284883 962100147 293127846 927826278 905293276 346979439 564041880 654816643 846475527 591345474 527842567 21647230 711268468 429853143 87278697 143617898 156989870 585160235 671918920 316423758 279555999 766941512 181397283 351164388 232397629 562110445 477959457 607890769 711448562 523784810 35676187 888048356 871792833 17469498 637787268 468678960 245929343 608726939 726694303 746768036 169668954 469660063 121872644 896737778 899472055 899703757 405975226 156394422 387981345 498587642 629834345 886469046 935570722 430683616 28717905 479307667 940978873 265168739 404134776 196577531 174206051 595183512 781100507 144205034 704130081 252545719 20142208 851933286 922120243 30435701 115854136 536641689 292476901 195763843 362690567 218485213 165313787 184678935 629400751 72837643 499850008 762519186 462537957 235749579 265085455 120011432 841240730 229071061 989852144 352769994 608307559 468611720 626095810 739063643 371244782 757999893 581511224 422911667 141630339 562279524 957481950 394944834 879255995 776584493 182456523 32407574 351949532 1358457 20388421 536433770 279135912 34028459 938091591 895423598 691027650 691553546 229691717 4938173 221601078 787058720 762909898 889135757 191579125 411328999 85326031 130321273 74855887 490720563 320660270 27777416 821184615 349831391 285671838 297112169 188431230 204535796 669494138 101515420 804350714 531793438 210319120 536489452 847540365 429639557 314789943 832680999 495761922 191747526 735405286 251820423 341179810 720253484 274144409 843341395 485498553 973016757 409456327 779536442 749226349 871982882 583700780 556634599 421210161 68010855 72094742 486213845 355923441 677854640 994488491 274444037 52347469 373994102 750007788 312825609 813168484 65647065 708762215 271389015 643922643 916962706 949658723 179196420 101110722 631220700 150181983 846728561 468341437 468510742 608324262 984094081 548853226 2652234 323546414 739693866 713348720 465658375 820318299 486687090 8238821 360195104 902294849 76646992 826712505 250125487 781758614 571916895 735678680 818863163 845467273 119062319 748777464 619368828 889241283 589994526 116841401 598827353 985712890 203011641 953649794 405413401 912188240 541893682 916263096 981599566 88287833 398407753 558362209 725266928 234572701 870171945 137164060 890972524 326054947 925058326 620540141 102282201 729607597 557738241 573307830 561326022 785626683 5909625 668310089 247848516 897730654 307063621 804601875 651199023 468851633 981796902 743817670 579601458 674944874 998323976 63623063 760334059 945396629 9881385 564645701 365243132 183585319 475777939 97115508 286304141 847104669 111298136 34866106 188711894 256800586 437524141 745801334 235903011 570286899 516960577 579930002 115414925 46078496 608025802 717363345 545385976 996686867 752825298 228544811 269413477 249326894 984465013 773444531 598049178 316635804 68392482 567095524 977288563 755516764 110964210 497269485 559784662 994966287 815355692 223447458 184823037 706098322 12827708 454918645 696151720 270730699 135119542 199353252 184405108 736863408 622360859 880463393 358639989 638745381 379223435 503253293 278927562 982027502 407969088 844706021 326878889 861126036 472567844 429048323 860146632 457670492 75979075 781745606 888110617 804878852 90944172 471261323 467347180 946429423 219282367 218152387 76336751 976595420 894718678 618541230 737600602 836024821 218628222 546853743 73966657 559259056 404698801 745371185 173133032 336766474 699668593 627725099 694741748 108738119 472532108 59926663 52527201 104522123 585581697 571403324 168550788 815666957 827279525 132991471 573366018 369475066 183665786 617057429 716842640 238529541 309223032 578243345 291190135 707931597 242337479 964941869 329164216 724503732 927979746 633600220 605578528 859979512 163894984 248279428 101810701 218063883 799352117 910893824 359316871 381438982 683421545 955416304 272456462 304736 393934015 840710088 946041692 235373867 104015528 100167937 257564874 824243817 430576603 713342461 327599022 572658918 995552044 774304508 105553463 195351904 408329765 836085678 276847238 459151496 331769445 261829072 820227167 691089202 576245424 79973757 708645648 725306012 692969222 515165220 624760544 649311202 814846067 846155736 916054198 307835127 280508193 998559221 747044922 553970177 399888980 854686058 496078025 402948760 689716400 262821382 842644150 749673150 600826606 32076136 78539209 882771487 313070018 886568588 415654426 197871304 951200199 350716920 42816880 325511091 628834768 343447139 300129702 323122460 707702302 845945823 48050780 155530975 642265981 445706974 640183871 278244303 557752929 75142336 402451316 271660022 364742452 754379739 454204881 929010221 255252082 554163772 300562018 628264034 466397838 627329347 174959813 404167299 192712524 696262187 866103102 995537378 351902817 578519217 841976212 618816135 355585670 616728107 970651023 892995257 685741298 858845885 179069285 33214117 816959387 857958216 572466424 657165951 845681808 685244845 222819697 383149372 39782211 206783926 407151303 528585346 531691647 925482738 510925950 617888477 569338364 867529 852331057 18705099 902279648 860564529 653006822 731783695 942187990 902502918 387123774 974562486 535558897 388167506 903905404 524457904 347436452 247720724 376882720 883906266 608591050 785067932 355916444 632177769 988107224 896747534 998286553 933295554 572191737 754614244 413547697 18882396 733791742 714464887 593759077 709747383 173917025 965077086 54932758 574676594 313460639 319582864 638566318 99861611 406099939 373805801 876993652 175487421 246460439 437124291 514296983 3696467 678217490 334841297 856043551 110272348 19509623 137492325 147748508 379549701 731251009 851031298 297396064 281731179 303404548 765767885 390644924 461003089 14963338 475030189 740768062 928798896 380748161 795287588 158056532 937414424 225083297 509842516 566405830 109519426 362490299 230786654 415550535 768841829 845997611 71313043 334185080 215893132 219402277 247921018 774396873 1216636 472922878 651810889 748092850 326935287 749998075 134478644 565791407 373640140 570639133 314680620 253254782 168134901 406723298 205575253 627403436 127454607 437222026 255697879 399167036 817393401 348461540 255958902 444995486 842889595 17996028 553883199 217397568 979817295 776159339 216705226 55356661 771783499 852824061 238954370 589674313 632819231 653313736 979975536 496854928 605918202 346274642 803271601 147397077 963610932 552878219 295884636 599753286 628039488 97543802 495044265 331831052 200988795 280912819 728147149 627170485 787214451 720868078 893378606 82178738 638375430 763578241 960513547 574760715 123006987 903836762 556269642 771419362 995277316 684616192 648805696 95317278 906131596 311715044 394798155 304396337 848050492 149911306 245357278 233496969 205072181 842067740 855924205 103565089 185733456 992714506 870710378 20661016 117168651 345572232 139188390 433126078 403984879 828734349 576152413 930226704 191980244 982841209 34763940 828340450 44921127 405879149 689785014 580971129 298071126 55614423 503465197 341024267 376705776 551372653 457210502 467080287 585221141 704786136 898480955 646942814 428289160 203581338 877780389 299120682 884467052 837919666 173391734 409306093 528910896 491136442 182841155 374396936 737991781 805409811 681997155 252500036 929105683 80235188 366557226 256513730 758631748 712423324 83708094 538837602 766362574 237552252 197605092 377513329 374764165 208237969 209427906 981398867 12868197 533232435 827470398 786657572 291928600 15692325 656694919 203314623 165005814 64772212 69081884 551379451 157001999 666315000 407764331 242306165 457249175 166164104 659548666 638991491 389449129 572278324 208786807 658938087 791686290 95998157 502056275 716604514 672616358 600075431 501780048 339603724 536680538 503168970 702272952 777832597 218582976 758895995 686840739 600061116 969169312 666548568 168348498 529703482 200801034 16191613 65469138 208591329 725330473 172420792 843463822 663891732 848416499 112476331 277716187 365914029 749983065 656831682 788026414 204074870 774800916 484552609 619306572 329054895 964032108 215882017 59931347 98524314 707583427 194532878 311243392 194872477 289753457 268165614 584927625 665642488 199205104 944126760 145321158 369463507 631035152 369095574 87918036 850928044 599685643 971247551 612514877
528953970 529222569 6122206 501872973 50233339 111945618 792979589 822562496 652151017 859804657 880202138 371979735 975603728 868428549 324364150 8948640 890020397 273354818 996678706 150607947 957897541 526673738 523093247 528795673 503782776 262926926 343589380 38129087 858859193 867568575 594188721 254358541 802728665 868772652 219380884 370371652 274442096 641129643 226228309 717319873 93337919 422581512 799167128 672739903 989923807 10892469 665282189 301186007 726691020 661179485 805092793 640589094 688438918 864192563 164898218 996695978 874345762 329027532 541461595 831810256 861559612 60909203 128593313 730932727 831582833 60322018 932914873 813166521 705595321 87082151 556901692 281523324 422411533 721601331 785084265 277474016 598681953 834882993 900922259 232942557 384934224 344140862 457408178 425426615 348044116 203829080 721025054 865237322 598608078 299173377 635134356 549430419 879194511 557416994 471263257 543990546 120972522 429568544 752555111 80543465 189376745 924085233 478738846 101945172 346304957 11329877 830454 625758946 123015501 238076898 540568443 329926000 573863544 913782848 443781966 61642163 661038428 993677689 735730556 817311904 435051575 694109514 743262888 349765082 352736595 724207676 37686810 520611121 413236044 280623980 919576428 853947263 528871647 291217785 360848824 310196298 130593350 942002875 177015848 936519024 203371586 876154749 102855511 177418830 101564330 991490260 934369038 137342659 891007338 781435226 710366315 988654781 736553098 763926571 939032827 333391471 309026332 703683641 907801326 193455179 384024307 772541834 205905587 795179237 160717897 861127315 534057913 964508287 61137877 154937324 611235870 734577356 674307092 761794097 23002616 330908981 544805934 752045471 872343814 3600417 842402386 685909953 631202506 206006857 494971922 545141980 672507512 489054614 966315967 404728468 326323739 820688034 103816769 677413135 576877527 931967559 992303741 687046172 805858532 611177170 559517929 295751538 183737606 968950273 887716341 324817804 575552811 171810958 240352152 275756156 19877007 539147808 224721774 561725837 521793034 119727726 76742174 811756271 571384473 828506265 408397991 46041215 576817660 151564080 286467146 153714925 288551772 722487076 989075441 366297453 193134950 647892736 993991340 883322404 22675447 898894322 174408165 240167477 577204826 407507604 429121568 990203644 506935793 802981970 435947810 761562836 594440671 903472450 582059748 245704331 450177312 691361086 814167645 833313650 13420441 601795949 9283858 135362033 565730847 773944042 770094880 558638622 547756431 380866089 912597606 45676368 564499607 687345334 553259538 756697574 554780752 77734194 906941793 470199125 777618224 864299979 337779474 39496051 518699668 904164922 584926114 820362445 497794353 417298693 703777180 253925099 406254292 522898260 67127286 2997979 462059715 551389571 541966420 683592748 152875787 257739880 675113826 488202395 975336493 228076372 642545010 756666927 842305815 497143678 456011282 691716137 420017550 859517988 862595126 189349627 297187627 659242771 81872804 628001398 28607085 501227697 693984482 789812742 607870860 141987683 538889091 426766974 277072067 503739196 404443407 124417741 802048483 403256966 814573915 902462054 312176736 255834056 193988489 236323742 326898552 431161627 406970813 560974308 146342631 215451643 209030495 246257822 149555001 435023475 65315657 698374162 485231200 802398718 256398269 791315466 743429799 737008204 691216765 450549240 213854004 202327005 874344994 557978019 806898954 15251397 981825661 795147675 32787466 779844466 813880731 784653656 616315932 19913325 689128185 377572482 183569807 512905854 847330754 662471902 717095758 699651131 345990722 397885935 240349580 932919278 947098573 862779184 104394772 202698092 292563192 181670793 918335707 948747881 76149373 303263242 636100241 38513895 466211206 409581923 817694306 139917793 143830505 761859832 156758113 225446323 722364286 217755786 654410156 196095956 231099455 94640804 8363931 533715650 557987965 819266323 763190430 448842764 384780349 452981579 899184969 920399910 917770070 880332587 536016197 24984334 991818885 687283866 72308442 920411709 970254853 670157266 827548316 598232308 553945211 408668016 507471277 670042974 749331863 947444071 645300427 659424741 587674513 47723352 362536200 13380165 203438665 313441371 790706690 781129273 600918267 149436033 938215881 205655896 325793053 388606504 488835258 55516107 870275258 622663832 393091572 462380369 845881813 659942864 815866024 833981996 459876623 22984335 961411117 539469511 574157330 285622556 669502486 5131896 22826763 749844793 68519418 837381955 623356959 788152965 114611223 113036480 785571365 23118077 516455337 725310829 785764312 914364110 199314020 822689032 779373009 619134578 859673489 726250402 566923866 860960660 729009576 4313304 894747801 102781674 321962761 645186804 719226920 19233026 874361381 703099379 598213158 152883257 97065585 227340881 914022460 328400469 898767110 387054576 883518976 253501050 306974145 564957919 162060035 517539006 768996423 609126031 287229898 622161291 695068238 646985966 353917088 569396902 632691880 307256052 220142138 159522177 885494330 793540809 402000731 741265037 398321098 981021893 416520698 197565331 516950583 551011453 821697171 725881109 709128311 169044281 233327912 685355980 140078926 14466536 548458293 616155500 282309977 362921215 498969393 800310753 854589858 624052705 637757782 613100353 26202981 721951209 121229665 861768199 518605823 624546973 573975505 443854192 592256529 197723977 599557020 288403735 271882604 948545691 733302851 976817955 102079483 947777603 238887936 53836761 68901371 351370448 123018672 741031794 739895926 517756100 441924781 532641176 916558675 277742464 820438218 332340644 100244755 998078408 951778092 821808488 674598281 220325096 267506099 857634279 607497245 422863332 149383429 509421783 668917631 819892804 464116636 399462309 520606858 714506479 609891677 914674205 699549090 555317100 272473203 634575823 678530378 882505296 702880044 894497341 424022908 6863811 43061766 248454624 121246475 731945155 254613080 958184313 304517025 556984901 641161067 842792449 754290209 616474958 909102698 89336435 987055086 662911937 94368627 925995574 347782149 220092553 276833535 88330331 81142759 867284507 206132735 645606717 428287399 684108188 527900469 885391882 842134863 692757872 470993464 595230932 183830555 991258543 331464599 842895183 828743493 701967784 619142552 890466620 222231793 580882982 433347777 578718769 384530589 660599461 169055320 27026683 506658556 176439656 772546212 298932962 960876052 606147229 232592813 371457514 220331277 378432686 665937514 682865868 264484534 375131803 878862469 1494973 903203580 189403196 22671072 947906323 409790408 809567314 720049088 936464239 409788530 246552747 277944055 681197177 132962281 639330845 534066990 552675183 42406940 684048282 99005379 250647824 233355914 747153622 899660880 855184821 254255921 368854232 834478183 722536494 105514883 196515757 389562798 612489516 853140234 550264762 480392503 631363236 960795477 408196813 341441377 956480856 972977127 361058418 372407919 548953583 780960756 659910649 14450840 611620202 808468626 381673865 588368302 720022718 50451526 587538746 93974529 939685256 609091996 480978895 503288015 268489401 778088145 681127450 929945214 647544537 240123812 807651235 520513334 55292108 519852882 444626380 312037358 451051731 348297955 651514948 583629460 727501705 942110935 379278217 41201581 432387264 777655762 68569595 9261123 888016169 25161077 46390350 342578212 34246638 73465099 960890581 104883352 500734505 751543178 447541896 817778597 283310935 186623681 753751428 547894410 223161822 929191481 249185614 427896157 926293183 664992295 446806178 65491621 926630787 866351074 684509696 843737173 560155677 142239382 679813237 10802658 923733047 785650285 928681335 351834123 742934822 838550635 903677719 164910277 459593746 762961098 871209485 480290217 6841180 282529066 91062771 573847797 121799934 614821823 953180852 302484053 132996037 140388602 502549081 767238292 849988007 711908531 806354822 93465936 96808041 476779907 433291087 505305662 635578805 890793971 823099322 836140247 552515174 452658169 488244077 315125782 195005864 483021504 12428776 775293100 837493541 883889492 468736798 307059055 627749487 443232978 591430918 14856706 683597426 902723635 853157660 241898161 951977366 442976935 687912175 91165960 302154974 898483654 570646020 226055030 64290644 966525840 528442152 802647909 952626172 330267208 909404156 175634636 691508848 588649736 364109252 429284851 495099331 968503765 932691916 418585050 107117362 112304294 813318890 762611014 516992884 906362865 800208979 850931106 964509690 463931101 701898652 260382855 687380702 438476583 647814662 224897744 480206431 932339437 923665860 55598697 289817874 973403405 535641687 578491091 184941325 304194942 775838316 336152194 639235018 804397011 634127850 390980404 528842772 897478181 44664841 429976909 623870535 476432677 510255694 268265466 724530873 208233936 5153454 860991412 614794929 71791214 905933232 842727315 323782099 293129423 458664976 777309574 410871496 526412346 264722719 543717692 273274258 418688580 889731766 962305630 928665729 170797505 681962264 388937416 844712921 923366422 98123290 988641065 845770999 170666811 271553409 919371489 326732321 485317370 77922034 209737582 402162354 75273344 948615450 333641872 97779234 922155442 276259085 485263978 428405665 836387714 724951261 904168440 327219897 200893764 278337217 361852427 45200412 160350889 985865108 919543115 455100890 138344673 144790010 6627197 558698256 464216467 382117386 144997712 512457116 217553547 874920818 881282419 277640358 847597883 304102184 760291868 177854254 844526498 491908338 160642165 355934073 486173202 631935479 968734165 941972418 594467909 725997112
421755918179