1000 856
318613852 763475708 732905283 667734932 404757704 942370332 747628841 996127313 900338340 789234965 596143340 228765447 163928064 684963709 951069427 400383663 532485587 122353305 239427391 848785007 408427306 334736334 721092546 964451976 935300404 811116436 906586319 800053160 140289299 826919575 871789589 408130469 590167184 82208556 409679462 995048799 464367024 964150658 794611718 467701030 844775080 828488354 657896897 477361988 58461289 926146066 808463674 400060362 25744211 878653851 387768145 12948207 444167437 341302047 506106693 616464990 255953388 854845115 419066194 88684710 787298434 74669613 271266408 787872602 813250765 566110781 12575857 131923967 142798867 477380995 925300680 204633218 470399925 751391768 50797641 815607003 610443257 440623793 456007040 967855339 88587665 635394349 347962492 259655974 614426089 65930097 627708547 697314279 886903028 590001646 492506088 343163245 104737789 738503974 113553108 38735583 416803306 852284848 185321142 190657270 920953840 33126142 212078238 891921047 376369758 617928432 512381885 124429610 330402239 627594115 664596267 889033981 605255556 585054128 939367691 751053994 831959056 895650425 602961686 916109101 446711716 142501147 614774689 754700795 623065996 858226466 269577597 983104075 178017581 863978651 519007555 682916607 307263134 274610863 385230447 311449887 1663621 790175335 681677978 414369225 58015454 849801193 735471472 470889162 207959860 665714735 164764900 955604754 600556225 212286864 983472941 288494625 422069590 449908863 869319098 786066313 61840871 820068161 508668253 818598756 681765866 327811290 375389222 88563455 129469524 148724637 15406447 155442398 386742335 671089683 742738470 558293637 990551739 181016577 463072623 450819904 294917175 508424425 346666839 777944996 91931076 582568882 450113231 377177222 627128623 949399597 623577416 502580375 12769024 861552057 633731962 441671882 665686435 14962426 502024527 602133036 944879298 802425833 258044743 283847838 851915905 706345060 174221567 463461209 261955178 354031529 204898779 60123781 885319495 355663542 793525675 808767279 450483776 795784747 378023072 842298537 12901287 798904592 701939584 766704938 964938123 833589605 778519319 819631352 233076628 220982765 264502032 707257554 422802861 996449536 407731683 145105800 232337677 735433088 791617784 922171213 786085699 651742131 706470836 342007617 4960603 672115221 917378298 927772384 337558105 935338638 28818754 866284371 637419033 556517212 737599292 571833797 670961011 959476849 390916244 662334606 861166008 20223858 356508513 277021884 538258248 390506997 921756543 486793378 727895320 303667767 94668325 214425382 777138638 710589738 901690986 169169740 825388289 91092441 476765289 410045165 825147792 810525533 75629091 760271515 254226617 236392635 866866901 266895546 41387809 987147596 398054020 74294983 860469886 78648040 445854771 90658930 84620767 323775598 459112520 763836982 732215934 890691798 316391968 932414757 906530924 252406928 940796399 460179746 167765583 93507960 93386438 556233428 299356811 6540074 469042645 459633623 157014072 980410381 241568313 140424462 933298756 210756341 714880026 277644570 597945990 866788684 707955714 889993127 2725868 945280477 145521367 248406641 691750227 453493653 714968496 382006847 852972920 595857791 585550230 295957960 557250044 829015816 397637736 906139537 816556079 899969776 852023055 263182770 451592960 484489156 375592859 537850957 50405087 969925935 792076580 437920128 673057050 69825341 439201968 643399367 504685378 174464310 896052251 365191976 877674078 518075421 179083514 962775590 849009497 159657195 509738939 851872173 106117954 18783433 311483724 47905838 686945740 479463867 893433909 572368034 108349734 189008275 609653203 185041733 678128924 719720195 276177008 308429351 756640592 710255998 103328313 517495147 239676892 366938330 490967 45772091 502737913 972501867 263435960 380012029 78067470 789635504 880881455 336692416 198664981 897785007 567319795 72126857 271465434 281381061 597499573 526203675 654296632 612978889 725591288 643454305 295726077 391899601 47255118 627677574 857271647 866223928 969293784 838074616 886224721 252290166 82610055 41597010 785136195 239646759 486003464 819505410 632121336 658916842 611715256 124500230 535031294 164276056 675077942 265148084 616321429 854289159 576840786 397965356 142824532 339653988 864937452 225653187 753495422 673921930 964369199 968038892 791743010 79349742 582521274 502726518 917167551 902545195 654262709 267578597 310129691 339036417 175503417 493457838 604307783 140123926 736174131 803784664 824162139 251810908 285287941 58820855 902000141 664750248 577971273 545297956 723093049 929638105 808132832 782640962 931281985 36019606 289990347 529798884 392466614 867829916 899967312 18335642 834476141 373464770 399136241 833091754 467338266 249335615 717147628 12181874 61249651 340572363 367318618 34589540 206230198 915690297 518795179 852778835 772102430 421921513 129924870 407818738 986734455 979425937 467111708 489261199 773016690 436689356 352416351 400469586 488136778 317697496 964864241 343231279 690262161 444383774 25653217 923523390 231982130 877848074 259260753 762768902 958906921 783784330 769568675 423922032 678630617 582821484 69650740 896920798 803814528 330877656 181673259 397417937 148780475 265082263 868849904 44938782 5037148 16233656 63279883 272437794 919405988 941173532 251555432 324238009 774338273 888572195 657173193 118122631 112232358 674669452 794928909 328577109 207390981 892484740 695426583 697735277 380853346 342129441 544759858 487533663 946206460 234641184 259179895 30110435 301099463 64733124 292525415 811774098 370022729 739568838 576623435 665956122 800251191 913136344 893113517 252395141 61188887 18058765 650096532 914691002 592404596 986571058 600939062 167144537 793333310 661861197 937856271 101253488 748256168 55297266 171624700 362656428 954651170 100596285 865206028 111185974 299655426 493973509 122252337 529876634 805990606 393718992 976351821 665051451 127487106 986685976 651359347 841847081 9836884 764165812 35492908 416305755 785182208 329849374 815583586 571302440 349346167 308242192 447960370 169936902 779477197 868230680 857704657 120705337 276100729 984343195 784287875 259395800 200878053 737253230 447342250 61106023 718897248 803137939 685798425 515767527 502289056 967523502 669873407 492336459 50532887 777664753 288267260 232501360 216272968 348221573 81793076 788647210 207689131 872769245 860030143 106404580 896279405 691209843 533106242 980432846 484395138 946865666 463167705 364331734 959044990 298815871 940818676 134516415 216487920 987444137 94991750 768845630 54383170 625805974 357663352 520991592 417542852 806392459 247675744 651658554 920225070 487622219 837154002 441653716 744463076 378582944 483896390 969860591 886495763 914802177 945187355 333868340 887672003 64880773 261361230 155534321 864227371 596189391 350367108 724139584 123268219 863172341 743622396 909716536 808884558 934819754 986780762 977741174 480957483 778974638 251022535 733211103 65391524 340417501 413183563 928899737 577428625 137422720 496498081 544855191 162787647 452060887 371545471 890277468 917906447 642424603 459293859 385106020 512223451 93844707 471911620 288684668 384715265 508067306 60627093 395205620 229184509 949050820 499997833 597313009 584432829 706996250 478137960 595638386 363892778 405109286 803497474 61338003 694765613 30986170 945420148 653743420 27735562 694843642 744079452 179904013 61375867 633568460 290979442 10807354 917101969 444573201 775355300 279106574 662019160 882840829 399696477 308126964 49827547 390791202 260252807 159997539 480868821 130663671 422778398 341768769 458132511 749757699 30310936 67980937 633074111 59507567 450965578 811072538 16788716 524194342 939213339 859774186 197700420 613480256 169589601 78442220 755094049 173849358 348663158 442079347 611548382 188461573 5966136 865650359 431433893 980714927 24834008 618942755 209561850 648814906 194717414 889148046 970926756 677848493 302413090 385472174 839251388 239836458 420756582 409340858 862129324 966806156 662787232 80268231 7092428 102939173 111600223 662429211 31345006 604011307 90445053 737297573 220314065 900911057 785582688 514551828 733680635 350306633 244713556 520356148 390422946 174370302 859487930 900351556 72321159 682308868 564815759 870671032 115028065 302412695 994054722 893759308 441646156 151916287 915271289 370205234 152982717 71562528 990306177 611100998 59303938 242378278 58922322 234262571 823237134 993508251 776592247 239970095 247936789 512485510 246845923 616543320 472655077 968768006 943602534 943797451 625886528 411243408 832529662 111859586 867103421 194052587 134449397 10226146 578808538 947310 986940778 777082223 95645269 356847562 443546443 648442066 764853317 563259620 989577059 879241939 119716104 575323561 404439303 110138368 752960561 879439882 594079939 722768170 878653070 307560424 102146688 755377722 542512561 393176775 609193913 861039177 814264539 495596526 845622558 605758662 474165062 73712805 604324907 833587111 7852733 491669097 689029026 138261764 15446080 49892464 647088365 361988824 505896047 966944562 954059714 838583090 163074015 612385758 383776729 482534732 857297541 961752174 514095373 956162726 814624337 512781878 507425451 153270195 682401994 533219330 881542596 377708285 54815825 732898473 880858018 414446220 178960656 21666834 755297074 814366285 565831113 790286043 332922402 638064077 958509716 819184592 841433308 41917597 285557215 756101637 202683158 454870787 358990534 135375982 332115819 94580057 159757188 689126513 937407575 648490483 887624975 97192053 874844997 543143867 455711314 929718160 789600139 795799751 360357665 962743302 860598795 800974525 906444960 655102156 538299919 911760661 476192228 672367402 532699076 500247925 238122224 92166022 91858682 415030259 386919996 187267399 784074626 872690277