1000
118243920 952734485 860927978 769156184 639318486 33403273 592951956 56438628 453059484 360768334 306005814 530063511 39601904 15588671 63717943 513918706 624668333 891111447 312281836 602889286 394371438 517549360 395093758 399528414 184007755 502349960 244681691 525425753 653475055 610224983 419618552 343997956 982019288 163033787 8980335 122102023 927547493 358914373 969104405 155068365 877713453 184536811 580284347 3025783 852394866 900341232 673583197 58586705 570497508 288247167 464166768 883684150 501316457 806810604 414263436 727003172 833571215 613370311 594841646 770023398 598851843 649514771 866242814 611954964 308393191 670010087 908239666 862225710 764885037 351854773 712778282 324560814 135762298 3953814 554963120 394819785 757721239 78064958 876989200 776607759 103984820 854487176 541075583 419085037 682004945 36446287 991748781 8789508 311443843 566320241 747304193 835006098 838798832 472010400 356498687 756521839 198249047 532527751 757957859 281136903 585551688 479598284 166982886 424064402 557196894 747008295 717866616 761372076 673284198 69131828 754517199 876266221 484657744 211384161 772812188 395667575 381206858 123261508 131130627 896007688 362770611 891355261 115627036 210334426 959582109 635307038 487902094 780532391 730353104 188039005 52967798 259651033 681654464 772251543 97985539 44077842 911862734 513033902 850974111 45682586 442327084 997257346 878735514 913806826 554779044 597282369 596613006 934103826 602924510 492564405 120543553 842270107 511465224 756306530 923611045 919681423 627340826 319234734 890180863 703953333 132213570 248990773 272555565 454881599 333551787 973574087 877787030 939394338 129643340 23430764 15878670 342265402 33788575 591665332 855734446 316674683 222289215 668216430 523968287 940679762 90918534 545227219 846611231 898164528 659160798 39715000 650638978 605287537 2781151 303350117 823678213 603850379 244865553 488321186 554802074 34092215 330283102 796759731 969079188 243642379 464662648 663003943 37427908 137460091 1622121 832655025 362111463 506228126 719178604 974793000 406408653 431604701 260674496 454373864 420857470 647689821 495211940 530450397 777917012 572177644 632557558 346804466 113326233 816459082 313302851 758221515 455825681 865611839 720047648 384355158 336703334 799717512 954636272 750645520 106630835 961820885 146934364 168815409 644714645 396251504 816005278 568066814 645270377 363567298 412826709 298597433 235395536 50769612 568794870 831465057 750440840 725011013 390793886 895504502 438336687 298098580 459083347 952866035 31929105 508001871 979094849 636609917 433051556 202484592 336455922 562971981 396741111 972026113 849050662 514748106 686113745 339412543 98933089 423814222 867808578 276566998 989754507 506981261 597114754 91592049 800242628 721380388 847775755 929337813 421786386 985241147 513923958 559748583 969122614 254350837 303014287 878692680 714452105 874715401 734723582 376291403 33975944 272028686 200213462 948866233 402986308 442397317 507468194 886193591 429115782 237909851 820865906 49035420 210043448 34358189 764783788 938594335 963598987 571603819 956495318 702697723 408234516 720414932 697460889 673325631 344829405 110954488 379259194 989263623 711066023 940913217 935948472 754209256 911396859 168503268 833054044 134582287 924287585 311520638 587801699 435140061 365647424 82333207 861067421 667230523 164280144 921042153 657990862 493183186 774600902 839217650 739327665 483629855 385750672 100878644 455403873 990191692 84525901 738132889 77855207 933212475 130684585 643778725 714978543 336320456 787269638 226753821 346444581 193538753 154071400 181729951 542811901 479992338 512133284 915193933 985171770 179852098 602182965 676856583 551787833 961013606 203747235 678984902 812020741 201904895 957158425 494849011 42453016 9625760 750706111 665958310 619035328 799748666 797896344 910199089 961442219 26213723 30770308 781043337 493740186 349856391 506313172 579050705 651356739 432660118 413715099 885714078 801009835 378852714 12821692 916958418 521399151 308383392 343835375 817113905 555989250 215905875 120309671 808763560 29329614 879639211 992154154 215024709 756076075 577812445 247311363 846372090 615545832 781112638 714065827 803808124 483393850 309626259 87912396 722030838 423079634 204923415 840525031 422626235 654423769 851430307 539983588 8988920 64894421 575363217 709960435 987892188 878895742 688123874 102792791 577754667 226098590 718515038 637180354 270633777 176038562 36492036 427950720 643023227 164968650 644545440 223291652 860636320 119704184 462956743 738187120 69547995 394208113 395943067 117357797 944096034 202139875 82644856 238747623 550999181 239257640 182108001 510475011 741261067 378702894 183010559 247733190 673506678 350369483 482550964 744646163 93873706 954277517 961177957 234844789 913318584 58775660 613030942 936767058 70522896 36045127 192404937 339152033 742547487 432107581 231791415 708664144 933228702 979257383 912517882 598004486 818603794 516372340 676491085 759894191 5132384 624068666 513913748 315729755 776361607 893278869 453375835 991119957 38707216 379714341 811665567 591093528 445342614 744304492 790721942 212439047 394392113 764048624 946346190 339632985 529340367 585150577 987211152 717261761 504365780 470862083 934505403 66610156 990145632 735234886 820377083 308394503 673702664 273258181 530667043 999086296 751263704 560032584 58877792 22656305 459684628 288127949 884805849 675203074 208554274 457740010 31783242 994194151 541374814 777097424 160182597 25879989 79323191 523598279 701531203 201487808 651003721 875365517 22159820 795371318 669070986 504924922 389114600 928020671 307739485 917318113 829009178 696128114 65099313 783973786 763334471 620345939 973984461 401478953 770230957 412441565 867707512 526183454 536049023 696931674 482730815 533213338 322201819 768663813 535641542 383694936 216376286 40418589 371073809 838433340 475432463 434354717 39277779 298407435 891958890 841537271 117974453 59469318 562631024 493330142 508088063 174879527 965690614 281183713 754762283 459454497 93289294 653471188 272020419 5245921 80473191 443042934 673352075 558357182 313082070 448756832 303255816 251090409 368603248 969058922 776048816 356383464 678901175 908756139 499264701 154979694 729615110 802104451 383757305 45852470 999423324 258076939 797087284 979511220 478302721 840086481 545245341 424625941 989437461 881314021 593910406 304616596 530137055 405212850 576173369 902828438 328038943 42574552 6201147 705899549 196370897 829141750 114601937 109181898 647286352 821356626 247726485 666287408 527539890 744483567 824593502 79391610 539316635 674477679 357722015 194833660 277787147 128171125 315432470 891727064 808403847 584720366 954887340 628586124 7904734 555481350 575716373 60804131 516014078 842483803 346954076 295819090 426415082 696332089 130994750 2334931 478925043 41409174 929267949 600704530 17395901 34300514 150218646 813180799 181384384 105264731 96673674 538260218 76386271 481845753 957875192 393505098 212510113 372409328 441390437 155277338 15926923 750473685 226929860 240239790 139169725 111687085 10292197 742395173 865669509 58141817 680224141 300762823 656310915 924940931 74867276 23479861 763652311 441736633 397112507 473889425 589692905 59695216 315901686 503816682 970713561 384520452 256132847 908051757 62661573 44176991 283126334 271650375 108971186 397266996 562561662 572680078 353747144 653228664 810274536 23851302 149407549 677729287 616068591 678599195 42569492 9281229 694344256 266110951 724805046 5370956 865515583 889612065 551620423 883073209 957220193 642403470 191537044 710997047 269262218 157884987 994920636 931040021 701467951 515556748 112248762 373751889 325533814 520600193 175418223 270528878 581029648 63952829 128484993 19631507 680591936 380345707 227125045 226769951 295011917 574590938 730078975 730602407 717449270 38740346 796173679 172585613 192312069 533471200 471265426 433738514 981104905 756544108 554097555 605816215 23391969 15029520 521025892 490166773 465121637 501356744 744814525 32097162 65313651 736034156 760163346 956634200 911400773 815861830 770764109 794385717 712516297 391433986 516259234 294131288 274328748 417188264 971335678 194430864 95344554 670104289 61288450 803447091 378513065 589317535 495399893 720578825 308900537 193910655 249768921 910359536 788445845 80585293 826826304 682309434 790296028 844435110 119121967 950059703 709983042 100341876 378331346 580809725 713451843 862721693 937208458 594241474 347713712 707734907 901747138 932306452 854167907 228564639 605087841 930042946 975023476 302944823 104746650 376025981 320459679 726364821 650436191 199934584 543579533 387783581 405484486 359902030 579226377 895505210 888036255 992675963 323049875 889270464 505268710 614295864 998278078 91078520 518226124 294760362 361682783 367763597 318901499 338645408 964611335 60878342 221181215 888285082 97733240 356238193 110308341 11184218 209466050 272674919 768220020 137416262 673567098 888206775 393590748 911077356 595545188 545402122 182485650 860405070 46784366 488672181 304467851 520232459 821184704 631481461 401299344 696785683 14001338 101412935 150082433 400752775 913297038 578457950 415358828 794190276 110080216 193282053 203130514 979810594 915765734 396562119 36577888 103350455 825778509 61249576 728539788 318520160 961901025 598839010 930285771 406749320 337575593 662533482 594952002 890998280 220648050 398111109 464260040 291073141 994615358 206043477 990454591 472667863 793129158 651759215 893242840 439529766 993398130 394403533 95946602 14287026 629538259 705232926 748754454 958467565 456465024 696779235 698901537 24365586 425603250 145294048 640026092 704005134 934803202 877257435 226370290 598623857 331073697 306332671 503973876 501202031 885082574 43989526 890847188 500485488 126109827 227302019 172697368 816262653 292698420 523455582 499321747 88262312 206677764 652226391 526025123