1000
767559674 917209377 213852097 148393121 89562963 144243927 285302081 15983751 238659401 703779049 382207251 598149553 759845621 893373921 325535617 643346776 236750001 611506055 126713458 350606501 261567809 183185851 550342801 889580801 307914873 561916151 390089033 707880241 432125001 512059261 863362409 438850809 74350781 187227088 13529057 495849438 159512201 190139415 430014191 430125893 931255988 281254047 128044941 51500479 370439041 712284795 675168937 876848041 218080689 729009517 172189121 310110481 855108701 694832917 770248801 426240473 546398601 816181913 703686681 153088856 714379121 330518705 490158335 89805426 78839391 842406511 509334241 172282361 123279185 699207873 80784829 302165973 263420286 850264815 163288209 287557461 378921241 814487761 708865121 567880321 310285096 798947317 751078507 397807681 612480649 22995273 81721601 973121042 915522955 548783433 925935301 639724291 826765369 147702676 651094865 473786701 883699121 104763331 658585077 441711383 168798565 963725593 911060926 259854801 195761931 870861089 288786501 491502877 175772212 508601001 217537226 690677993 591095767 866444681 254496379 974351331 905996073 663823793 363332351 743928631 925644425 874503761 336581587 263359831 505703681 597996801 733263679 425135509 75702191 471365279 634489534 378031851 923281751 866232821 499411201 638393175 316320481 9507841 330892112 734875321 860691246 375828001 895686525 176377249 126426945 393592085 404639413 549445113 676616345 111073203 156796801 5737897 547524545 459744945 989369088 610137589 901038349 187924598 545774913 232507905 191113931 319561005 218248643 667032426 717155851 210967395 813067001 114238910 362473296 248538597 893571385 802680931 939662963 48828609 715451521 961912841 31336560 891388417 904256857 654707066 374238813 910820387 57957313 514029633 779194081 200991701 901727825 748329729 196771481 340804251 130959558 192986979 967849893 486604055 870550913 438469201 541643812 872191489 792836673 126920001 801518405 522601771 556360356 957070951 430322045 929770616 296006645 177670049 25076161 639914049 675937697 234395246 673282872 725487749 838509711 495188257 533231011 214494391 339336721 522584238 928262151 468462401 417158785 752324011 387618577 851360001 778004551 474465237 5629441 140637339 484547169 784641601 585538481 71625875 288949211 79630881 563794505 452469249 965340241 14032933 235634201 485204666 861727827 15492401 493415182 97824641 769250225 272771524 856395269 318351013 840292041 289900235 941272961 844376001 737787801 817566767 900671279 340498641 25366313 496583985 242412601 874410659 962677310 218111121 607358001 45427961 841747621 976627941 339834123 401557793 104837577 6282621 370788289 220790801 432788433 449589543 376736597 411585008 11879849 41643769 300800545 656355061 957588793 54845521 426577209 969738217 724089857 590543801 200073265 272284001 999428951 600184345 783509423 176778301 641926801 830198561 914281121 274930041 180483369 753637626 424145393 452424321 857254401 527279329 519156591 335364621 293534851 929042521 239473025 131480369 145783239 474705921 648198897 779032177 320262733 494369977 20798081 165733761 100145521 264936137 699147633 984984354 139993303 988782031 454002863 564012101 912279891 795630401 823529495 923839603 402846732 103190913 583581729 156285001 437033416 375744057 172414545 831888566 538835353 225239041 378853825 722916223 743098721 307743329 399618087 128318801 137160001 678425473 633411233 843596801 97213937 12758093 681098861 187307857 373476637 179036113 586744931 884400471 397310906 278172657 830995717 121755931 688751132 795153921 482080723 894836577 31163751 550409992 900569661 164769201 567989147 204963586 903388225 308541246 435987105 18887167 203097981 416162560 178464697 547105375 489579809 317584514 758106961 672549461 868882945 128351393 659012024 576275097 617106049 299945985 780420691 281879185 269931080 316188741 865644656 79039601 130404961 826356596 430567877 77152231 705752001 221290633 723825665 7888089 732122669 643001921 206986801 415596871 348598481 98345921 655957576 996816661 807636001 355315473 398436069 259571741 637592501 868198529 485552361 463598961 346960629 143281737 428693891 326074667 748067111 320278849 644645749 166702137 800223441 79441841 485588047 203674083 351852377 661041253 93832781 486331698 614397523 518044789 563135885 936783536 215790451 593915691 255994206 803735911 454836401 646982001 868650609 458475981 860282401 534689802 980963857 693767553 669554733 760292355 537441337 282217961 971095359 931126707 909386241 11831795 454286849 129635651 42847969 627519665 735327281 497983905 500623750 653869401 695527259 75510215 621995073 464272501 393151241 785579821 953619289 375236617 906707721 545913537 42800993 646369421 798020857 12023051 241234550 576944303 956019897 671010221 775862081 635454673 416417391 884899481 434781743 982852293 596930881 282409441 211819129 329061737 392871905 983249473 707456726 118879071 419718177 541013476 166632769 489425486 124042293 950589336 508863501 573362915 383810161 325333751 37430151 308748024 645746201 507315601 944149676 568348706 487806101 957854721 328873673 499452683 917965601 514441653 881478331 116418991 848852737 90149073 334798161 625801601 355745875 865994833 80805645 367561397 872433681 235098889 95072639 405920545 25577801 897966649 818742406 412234505 680718571 995436091 990475076 683505733 461524672 237056501 66256641 217679076 406174913 387179276 182470641 110158013 314787345 261221865 667113529 854900877 263842936 454656001 971024254 786778927 714777853 224887473 941642639 114630047 416523851 26398625 74587569 961948321 922593281 452315787 334131601 280771001 672649311 946345335 396608953 544798881 308734631 905930555 13464821 174432782 997882501 399368835 104640929 462614655 69791876 804007089 945519041 888549249 396920937 935255457 699430529 685787293 922187681 653626873 616723039 288856826 338021441 375104513 609495601 930952649 744004251 988548521 239436041 664595116 559754657 226944243 505824321 642675779 115270941 854785633 288143561 524500351 888665939 958922183 201047681 386913307 985611977 970541364 989992981 342731039 253010102 394281700 556228897 217116497 997904798 422211841 424525296 622151233 575776841 72263201 287788921 826073825 70030901 151037857 744417651 913646545 15576261 283129591 58558001 869420537 114358661 200187501 476043265 136944553 636028465 473958001 992830581 515202103 63110019 454891866 796224316 887512401 501689421 220867411 106533269 412504321 804128689 652696761 389363713 118101286 928767397 576503301 219948601 529937031 139832399 819118657 766367901 743213857 938360565 305382113 73319741 539033281 302891532 50741233 346657781 705295121 419833941 83459729 192066743 657406887 332573569 866945425 639927953 350848501 358541031 689176859 657977665 322986655 320087733 969473977 375594010 633970807 14966641 902818827 27613341 951091431 529337601 974333320 482084101 407549601 7463641 449832193 197071601 538102633 774683421 535250021 211645626 790484449 133532801 221750801 849958161 462851803 234359441 881034241 215964738 897759066 818735691 275180473 103038249 127874912 314780301 806166629 146206483 597243451 918122571 968489601 748292641 454905231 18601233 797410221 496983921 515187022 26611071 521341551 368105441 641751506 66489561 809849451 254967351 164445671 721567239 565813078 786474753 875911626 195005306 937139521 482690425 455249017 481779745 536705000 111701153 681456201 43810441 973180001 56561433 18312571 146735421 309026729 907514881 940821001 575524145 918026257 426705841 517712401 586770641 900159341 842957547 595039777 985720171 91174623 580372881 350137561 258985569 55117201 248374209 732550165 564452593 590046321 934169381 279761460 754967809 803903173 990113831 301262401 284297825 680047801 527397586 699823366 908315137 274300557 556994241 411030501 847224079 793267401 536220805 726598161 723063003 306348755 988451877 901718621 983438929 276536001 497440953 460334465 107415901 845937729 774717149 852868039 471577233 31319276 999971136 870272781 110824005 197759041 492396261 246442903 767911107 482913409 435025801 124891861 193278251 273338901 910491589 579316705 285852849 979918111 331636831 959930065 335641030 451053645 837829085 986072646 185480031 454634861 986325641 984841121 176928535 627230386 170935801 435195265 408179201 419411351 261615510 790627971 159878593 694830385 972183521 354078497 544253451 598989897 262991665 564207995 524377115 860922081 61848791 6693985 528716467 620168729 796897089 825547877 818379323 969626881 25533901 153489393 909819111 151638088 126420801 721798913 79215809 362056301 840259831 127200833 426150719 661965097 193039041 713979551 465260965 639537057 113224125 336668817 556380341 290083201 650594446 986421885 857878401 821501636 943142701 375646401 833269393 9433441 905943837 13213281 669609841 813670721 38016741 20836873 944774120 212134655 163053951 285310721 985524703 765257301 542602065 154700161 421152449 267491801 336386031 80080641 371687209 442046437 55497141 592064513 964476801 678984575 494412541 315089501 292513433 562410431 737730856 476644661 875665437 299862041 239269875 725218181 434194249 839064057 479540619 480771489 946891361 299506041 72436383 196814841 849341375 372913665 380559501 836923103 683455101 183149569 585597367 273189273 457234881 902067585 732809461 54437861 296024481 37944553 307883011 798544125 138368097 120229701 298976331 619420261 478210495 48810931 141334471 375038241 693715961 742170785 643690501 906286505 806542641 740150403 827747926 514714869 540213121 220461225 178833841 649607529 970672817 849431909 334092801 244968961 278422850 98514761 622218371 905054393 132885625 666461935 461442676 605489510 999102401 603094845 700219921 118388589 214236365 759887889 395648385 128528385 631780049 662687567 993125389 134289147 377374977 304691841 411336641 646628771 98616437 719801391 146395741 448133953