1000 50 100 73470 887764504 67073 412853011 5118 695224523 99936 382792210 25574 185130725 18962 527586091 82504 849185420 5813 469640205 35737 275019646 35494 836793013 81003 415889040 33932 80701814 74840 944964209 89207 512745421 29298 682156014 98388 203425937 13484 128724 41015 787623903 50965 397111117 66630 80857887 10663 620393074 46888 572550483 97029 823376135 3931 98842786 69363 523333371 14083 87295231 64748 618883683 48409 988418103 69234 503217362 10746 915646913 39000 750295108 37142 320873030 69207 387968370 67200 992409926 14846 641886130 58898 193191572 45095 850729993 39299 813272001 23102 782751290 1252 901025197 2924 656925694 26725 605368843 24966 672840283 1078 419223403 43465 62466287 81288 96323075 44374 460173468 53195 173713527 45639 85113990 10680 793670261 73080 636022053 75409 260565257 43959 136780984 50825 633787917 75832 56060248 65299 881688628 14503 912953601 6728 545395745 93546 176690444 54725 678438465 13898 479741263 29238 761363033 96232 136784044 81640 200638167 14660 830458294 56567 754152592 67045 834334387 78419 370006492 24359 152904754 83461 595227717 11663 26792309 69539 643352193 43746 7333823 1815 507919904 7120 345525962 56838 614839788 50542 578513031 49036 435813178 29726 79410174 91228 680143991 97201 229163229 64152 237955139 18999 931513607 15562 419326296 54853 203023276 34903 890495415 61193 589051857 90640 813607966 88966 371416522 54837 418985906 15379 341724498 31627 983759000 86419 570671562 15798 831182485 76343 470870311 17419 374967821 99920 492177636 51704 457480685 7892 653811043 29508 803147452 34144 517267348 44820 812975050 50457 561949851 26425 467598108 71487 875435353 96268 338324593 49202 667169858 73691 156468069 32177 33890051 2519 987330486 94301 75997780 99726 565250513 71490 962819315 4766 782595000 44276 861876526 9064 929544633 81780 82784877 83132 876439472 97532 565510332 3410 839312963 72504 591860546 14148 645014742 83794 350974811 12469 393990888 85110 883156433 64921 285268436 40257 784658750 39081 282277119 5149 213779257 32257 565024631 13232 411238627 67354 971461596 3172 897276213 24589 884054538 99040 940225321 59723 483527338 99082 77558306 80231 256618887 58000 763878885 17491 157776106 33637 834580486 62566 481500775 81515 878299635 71587 548411574 85250 772096939 8827 795771558 14544 163930084 80500 549270130 94599 403359821 74297 929795705 94535 495625541 12967 767298434 89706 934984008 21720 698081540 75087 695346858 79767 821407394 45343 782286397 6781 670323246 66223 376954930 45144 887583239 63976 964105286 23249 980114671 74586 910401931 23551 73518346 44478 143715387 54356 179137648 70381 819121602 52195 82352005 12021 842556794 91417 296211243 21943 15717837 67128 343025504 49392 17627514 4074 219225058 99111 953987261 2493 766373274 83444 370723594 66464 543595406 7587 47843078 25095 415480828 64743 577192402 1781 297060122 54005 760976715 29059 68456118 40068 528325008 24705 618229292 91570 374451722 56819 124891821 38091 222589317 18717 31155132 85982 827421133 57103 523344092 32733 682013346 33203 6889383 99649 524715606 24311 399538077 91397 853074685 62899 636708808 8977 511185981 62143 468114410 91618 807802075 65951 844984494 49032 215912309 12567 406625108 43768 679093648 7219 309117012 26171 591619666 74177 202285366 5935 917584177 38444 625527993 33749 73851011 9592 346908325 22914 501052938 38495 6430487 52261 482534149 82804 77998106 19102 908080359 44239 900110637 54630 270519821 64916 395864268 99841 229850641 70934 807368295 57297 486875058 1345 991566561 71102 98223018 63611 730923381 27638 725289507 50696 200186026 26290 461615214 82934 842944447 75198 798357630 78387 516970050 33580 71572534 67052 114696007 49632 848730157 59850 769843629 8777 206070584 80064 672567539 58145 758424715 51074 226000011 50324 362678130 81934 151596117 71692 801677449 89190 535409770 27126 168110958 12991 959428959 79007 372357846 23295 678502094 86908 325090315 15296 977228137 29362 90486431 33971 135595346 57279 298920 19415 590431837 44983 698477549 10501 734951747 89494 163561867 98244 342815504 56508 379860410 24432 467681180 72327 920246315 10541 912277302 30418 616864504 43524 291438483 60358 287063021 43691 404404607 71831 268354138 25691 139698310 51771 762662944 7661 623274784 69354 263101699 48964 756041552 20749 374915267 21679 33581787 19294 537831755 25998 723843718 48619 645895186 14749 241544683 85157 644611075 65750 514300778 19254 395738354 80153 432903788 92456 54402269 11528 830638246 88932 5644130 10229 867924006 27483 926113247 95628 225577832 86126 16222571 54692 345914362 80627 606357148 72683 45373940 88566 718925386 55610 931200851 55389 851448401 71651 132231204 29089 389049172 29246 48090593 97102 555458794 36236 746524415 75774 17515555 26762 711988314 20268 943021189 42664 68687831 68877 980904412 49778 290307365 84668 645656542 94989 505938412 60938 238381764 93416 20509174 31575 480496502 18020 863322465 60107 773500771 78100 86533993 65092 709321599 37219 755006892 75090 474395869 12746 696555057 27408 165066960 82052 146341957 42157 202362298 15342 674598870 98513 220262534 53573 292028790 2339 882948384 3958 8906238 90843 420539195 50958 429574661 48403 767282206 76917 192785258 69332 339800945 66736 844163774 66951 685853734 59936 600953651 16350 515995914 43247 449492418 12914 121400799 17456 149665105 39375 54180939 61522 481503245 58923 333404181 89625 883721925 88091 909244750 18980 414469721 93429 742194719 23258 826015447 12592 273989992 24150 160099989 94831 624538196 80783 183950379 94731 622167259 54467 637945901 84065 294905059 37924 514918762 20438 965038120 4187 329585092 92334 627610029 43551 575028646 47069 46019421 29410 466722807 11604 60745343 81132 341019707 7030 902502189 47103 973934560 71795 727690724 33926 220579088 94247 253209492 4025 167935748 71265 492939787 93595 738235711 61553 125465726 75178 184366520 30735 855547331 20933 5932186 70622 906417181 53232 64594519 32849 126677178 14015 252708677 82632 301248210 64895 267674699 50185 24878133 53826 976350086 37615 486594712 27084 14780054 59110 779421914 57654 947212439 12690 25302776 16093 459853818 18047 525590905 87691 272025287 27283 143899463 42288 275253364 32730 731865857 39103 114904028 6010 404061108 89717 356861185 35496 468046265 35308 73264456 12969 54093131 82676 998148481 1321 130097706 17725 130008986 37440 710810882 52276 72601381 37754 758376180 52318 725098229 8784 958140520 38507 512453822 44363 548837454 81824 4301706 98547 944170114 82149 535818346 50857 364569875 99815 148321334 31188 392081397 99518 82252754 46195 373333739 83148 258606065 2154 684927153 75143 108706265 82189 848729070 33009 185131441 43900 459287643 32199 585212492 1569 72155342 99876 488313549 76254 160919522 56048 104715027 72335 395495596 64069 477812388 48560 842562281 32152 871791749 16042 582154438 25956 521705027 31690 678567244 73237 138977494 79598 914584277 87957 24394781 46742 220007853 46530 373533331 96876 192824 91239 147486619 64332 488424197 61969 297484028 57417 437544774 18907 423137388 83103 615587491 64268 849078041 8079 477531153 17031 152112643 81299 884525752 54897 828218697 25969 77675091 97103 819826403 85397 467543659 50695 89045150 18531 356149997 77491 145233077 5275 381429684 36313 86977208 25575 654685762 71253 74269206 8141 647361023 24914 864660455 27000 759180477 17193 528769552 65239 223202951 9771 947276579 54698 625420410 32504 374257431 47045 1049792 13628 35039220 4400 617340185 99011 499914081 20443 931628398 27263 883227211 23379 914811439 59276 549467125 68067 980537109 58774 143126144 44004 478849818 14085 914672828 4058 309404607 59855 61795866 34095 951684618 83341 824605485 14346 463251549 25723 965756949 46953 152923266 91570 671632153 72330 277729209 45536 180510943 85756 163899049 27358 408394615 64843 712199870 68157 146512555 33099 127348693 26664 384603328 26849 177434633 73595 500713397 76250 159963090 98964 942348230 87723 970305833 26752 444337660 87839 964400482 20036 717903575 59755 220215325 61252 171095707 62151 766963288 11179 849480391 97933 621373472 21448 178397991 4343 142078087 73219 397759054 43456 293768537 15467 378466625 54302 218245762 88505 787071565 19532 592781361 46557 236337321 24413 357062939 60418 905129638 3545 397543759 49932 671097831 27666 572043415 9594 381014485 86808 784689834 94762 611131387 66078 89053144 7022 390369722 93327 37079483 63528 427953615 16618 554984701 49179 217907596 74538 864106524 55628 412970128 31865 723849176 34034 315236393 48174 890739280 82456 620094335 97549 963124358 49569 264286734 9856 558476707 58789 529758444 86678 88206361 73642 270925367 24121 238224571 64029 917823948 74513 70483858 36703 54952225 56757 172871881 30570 270718522 39403 405615888 1833 864223741 24974 251261386 50287 403154056 56834 718709938 56165 823968766 58765 161206539 92566 670692629 19317 730144607 3780 749632853 90544 532802118 43178 777287563 85599 867084954 39744 705075289 33901 109104133 41720 343687891 99581 599465378 95377 476633798 93714 537615789 54408 635600010 4135 844314915 37248 178427790 32134 470858903 27600 385590029 52792 814999465 49952 684670137 27637 75002603 16781 806384989 56114 413481022 77683 926871673 84247 16399394 16318 427728174 41064 228786103 41786 732590367 83586 345440383 93979 202494216 78907 176058728 60538 503070740 84366 597017929 42098 341871585 76350 342881628 37351 765030622 82560 784519558 42316 936565064 92952 429820699 37624 665727097 66704 293583327 58507 482921724 28200 174636453 76110 93254925 27774 226946874 32931 767040648 41853 147719384 75787 522411104 42337 849381325 10492 235885341 12743 707717593 33886 760727580 98550 794124635 8530 726993382 80231 970109967 30274 657945094 70704 194645945 95628 335399264 99968 721860231 17019 453471513 12358 117320278 65078 750435184 70342 375709528 56163 925542334 83105 690117409 82366 21832063 87782 469925806 49902 958050895 81390 93456309 69492 4582245 5306 966761997 83823 376145840 65199 501515501 6703 501241318 21381 598323122 27919 379695338 22225 103234188 88318 567382403 16276 457718121 14799 650055134 11755 113757475 47414 928273320 70258 54838922 13878 83777339 93826 132149069 23183 340677161 27280 462348679 87818 817926910 22537 675678406 70327 386803475 6963 903049778 84050 728828005 19251 133698937 44394 632913129 5253 56829998 45539 452723209 42629 897025836 35026 868422300 10748 662121717 97039 775286320 97858 305582203 93881 910024063 77582 178379636 53660 270691580 57788 810497556 60933 912182295 88172 841186161 29258 207786564 87900 378814794 22878 92210019 79229 147270037 83226 493322724 5608 908170941 74593 674425486 52090 958450414 87562 994906940 94942 734128799 94411 716308171 3991 811534186 56069 656762152 72614 148625674 7162 957283852 68935 877658809 51840 364476461 7499 284873267 35710 590206591 17286 660851160 62914 491174600 31533 287724817 2627 12270138 96952 998897290 25948 223372745 12271 927836794 28811 407221580 14691 907268803 7594 951444521 95567 191478783 14337 409060803 25717 710243608 58834 421338362 19659 431636495 71045 417490244 68792 19823678 64295 214037110 22466 106560846 54629 646420958 23990 759057221 96313 787196234 79286 468161738 66569 485312421 40336 349597452 64529 86974982 4530 853467336 84718 63162866 43568 260616733 57871 392704911 91636 248814412 61528 538113092 19068 409014890 74299 95692609 57297 186817669 21784 263890002 67388 857164686 86003 405704093 63787 76359861 52941 654346118 92643 18034714 45816 489842879 93240 725893688 11790 45529290 45309 188655082 55811 168080881 19815 665552227 25523 550085327 70231 972356087 23342 668040364 47689 139216831 71930 924830744 27969 813969951 82951 473691680 57424 634777223 40128 22286075 87600 538130994 62611 861685811 57656 271249253 86374 301643537 13495 507627349 32004 416583390 74066 704657755 95972 962789149 60129 18320738 62664 936761302 77120 57493085 33661 311634835 88268 466857669 61010 419896528 64036 629772041 61459 998203955 81211 681381278 26331 224358457 29730 671043448 89001 882069184 58837 824132972 38351 834263424 51600 528908342 57320 364872913 99436 918994343 80798 631251162 61021 538445737 58782 676693912 50388 925936437 49077 685514606 88551 96444067 46248 852674501 69703 903587098 78649 910361566 89692 720298398 17234 970571115 7353 617562004 20165 30220166 54171 563175463 23475 546207610 63338 425809145 99732 105595089 62971 331943724 30870 908491167 66568 112046535 89457 303054459 61116 206311429 12829 355586072 44840 983785231 49161 87335008 59952 736403397 2151 383053463 95169 780195251 71906 697365406 21137 193320535 52940 621025760 40034 829769907 18700 165876054 58998 408413434 96185 656199032 2274 597797909 27947 455411488 17183 404064626 59869 366138382 19212 727994498 84769 42104428 2460 675499875 9026 920698935 27702 329876937 90791 974692653 4042 646956535 33537 579194330 50418 726381376 14277 131743541 73530 494084597 91750 216111085 46072 97458546 75830 558487566 76516 831696065 44113 635625695 74042 664136895 97792 261195777 85780 893764656 62289 145758427 31242 905420520 1827 392950063 60631 216320463 14206 317757323 16585 136199843 7805 490462861 38256 211283832 79808 717656037 92131 709424390 73161 951165397 9072 770062248 11002 822393953 44085 51751278 17896 909597281 29251 641847578 67496 884787000 1570 3426545 87474 687876886 60827 66403107 35331 448139947 89004 75698079 10069 468595524 26453 556063979 62006 388266595 74881 760001238 27356 760746672 59136 42610877 75049 998180232 45763 517699981 27189 487157507 79892 286129444 16992 629217115 40012 428823627 61932 547596613 15231 791509118 40089 547747140 90098 138697120 16437 575733853 34898 500638167 15778 68227883 25563 60745804 58049 524823422 22171 535858150 63593 318164265 68818 793849734 1366 884086708 12878 546052266 55485 400226070 96521 5851033 13477 301975778 35419 637439075 48772 567957544 43567 485419458 28525 238865179 28252 859895061 94688 791327602 55411 581356014 97425 966142555 95675 722742364 87595 506689949 56761 98115478 45057 533980736 34211 850567406 56044 572662736 69252 535914356 68746 438740252 96884 661762541 61665 93344724 74274 626302391 22531 77122757 12120 110639108 7211 236025436 60317 751568279 91865 834134209 51932 594912361 6793 902884502 90622 660003880 83309 680918600 5800 793790080 35365 74499797 25889 574466503 51246 732741 49530 264926586 19359 940137895 96461 326558924 52549 310672487 16135 464281022 26162 351289699 8212 623412795 53363 243871123 88831 142794192 53554 657578879 51442 146794464 2130 715964417 12882 194359145 97383 734896990 57880 481007463 57536 223600952 66159 73185261 75430 983590328 93750 863223449 4435 608246667 7264 39972115 48515 436088653 50798 24647451 97047 8494356 96494 331554364 12298 126816033 48560 183877254 99714 216922338 90289 288697386 73226 551354159 26398 792838133 42098 887982479 71934 964895242 43016 512710595 48813 431831800 96119 618867669 93495 981036567 23080 745441975 85808 699572648 96614 887546473 41157 145453885 77177 632661339 18916 687909021 83226 77293549 95626 213295125 56068 293943854 70475 177850430 61687 98365799 60079 788379572 71130 361543274 61174 883912870 46049 971829616 79324 332369522 85683 259664119 85505 73667421 57539 270321958 99338 39474439 39998 758382513 27426 301150335 7990 221623127 85937 489402224 12068 651287748 79352 707661521 79000 13588467 87469 558307564 44468 909404603 71640 833254300 59206 548423649 19289 635123330 49350 812655910 41663 754565749 86911 714285304 46898 216753921 85020 858343765 19560 258270601 76415 61282779 80321 976110406 75859 289903392 10835 789208073 95243 921875879 51387 895401567 16801 190102301 95505 735542224 77489 446677990 43521 504548324 7124 225385455 7643 514945556 42645 479635019 27977 648130140 99228 702304353 30570 61131646 98662 251841840 26487 354048921 74911 351495285