1000 111 744098828 406171561 343811321 352659393 774457338 978064132 56635816 33921706 541380876 787645529 45290558 205144981 742752022 722561292 556232143 924303606 927199707 121608683 936266344 805783733 379516423 640013487 954700733 830686351 235339906 931546545 35025602 99824477 247948515 173486037 946625717 116846427 321055421 891545484 478753353 540176187 430096775 930721508 30451908 189761882 217961723 26201289 267953105 274620352 730010053 345896005 143102803 70145400 446572202 790565202 939723594 520154258 118059207 602824685 817209145 88879406 904607969 431104320 925372492 131036182 382355092 101679459 448159442 46900588 657935435 249191888 92136964 311129918 129829085 861802148 171042135 771744724 886642284 382372991 21598654 482545488 387078142 785523801 329383111 542608663 506636841 594680378 437934488 667275600 666916786 920611288 699802309 950320318 853074250 539061523 99222353 493943597 801998859 268764203 845843462 882813991 348470544 736201528 761267402 558981457 441434903 98607886 430832849 914939366 979742771 172558992 13938810 530970277 692277857 138690816 553108850 412836689 163364972 396955256 417667537 600925684 666708183 699364104 647669210 310052361 175989300 40473579 596331512 499762958 846296593 128302223 173255476 973930451 745039103 276334083 156058451 567006075 364895298 952406949 837105276 642563331 397969085 962757759 404139050 749822026 672902618 141294253 573439657 606135824 141107129 10405314 848978057 116905711 52029433 554982275 560770033 131935619 468095267 607796074 182344898 337895492 160089884 919545227 145312115 118631091 475790384 176450107 548766124 870748048 553749230 503141124 670298029 518273037 461408206 849604981 355776844 674326373 570958429 971024345 502935240 759123774 720268299 148293783 126068535 775831793 29460735 919970971 702922043 230686563 831551686 885989521 280185441 987310947 140027851 995948618 710566917 471998242 956559378 284717854 119201104 205369541 383108304 306290826 121157900 543331925 283360598 277490683 624584849 857937407 84209266 222477823 314339357 74994729 702439552 471888750 872462646 171058926 268391145 974599138 893145340 510422084 172254853 195837314 885492311 467411951 702746703 494901242 491953839 192963479 55485311 376891818 929381765 94965765 679756508 832646665 776911154 682838889 223478644 281528853 948150613 165571693 427603017 741321869 120496337 782909647 656133774 358032172 622916043 338645265 655597178 282136544 72370071 186755828 464105356 998381790 77196496 635051276 874599241 457388560 834771797 27649870 80551717 220116087 251590496 663175381 282231577 627587002 303389693 669247958 723580434 101926006 372455264 773794692 937577742 43351877 846656243 921481395 971917479 317586400 377099021 850170291 350553786 822247917 597031895 632913540 755870788 720448617 147274927 509242446 474218625 161113103 951027377 808455636 456612880 179937986 2026089 458518135 553587015 10949171 557358871 859994855 647440272 753406205 84406768 843524837 45199136 38848150 178647717 7473159 264201352 634019442 597726083 417455805 624921235 611020436 678813552 731526192 898922246 952280187 994093163 587797767 544819735 202629173 697189183 181546390 173008298 291566008 139411562 808459739 510669790 478089229 942181986 53379458 66409992 380420691 114851845 282601423 126459827 661848331 535119679 835223690 13299089 386052661 838809705 118680901 848022679 58260805 450438499 589396425 314962460 702371448 734904360 169889354 992256885 8200502 275762722 332948783 154797419 571351720 187969793 338740361 277202215 316544091 213062570 301285809 921204977 67035521 409100613 177625511 771424336 366474139 836139471 472756039 879558882 559337408 531173193 654981758 864573844 886072924 914855189 804543002 957348612 378965291 810831359 728923051 180698847 58589676 412927824 895220512 270490155 630249053 248435901 945537646 326054012 429712299 528414068 745987910 787920182 491792767 800782189 15583844 482661266 54944342 422214076 183679922 911102503 976872872 579588218 245061610 726357158 168397843 423495367 793306463 868882104 75834017 827826489 322623591 921562316 785552280 74610685 427854531 426953793 642395709 400747431 345199212 737560440 671978037 898372756 261445600 992314505 829865095 509819018 592367116 644359606 790431883 70342590 430297038 927409091 438159356 187449067 154683393 5013661 924652050 183193920 954359834 258888477 381831062 978934780 623618766 875453968 352247443 295976252 243575566 596653237 830231273 605389264 54972507 949321107 537047928 63348545 513546675 616856044 267123978 981420346 703914932 218057288 517648852 807893401 385761111 287660004 388525641 523622335 570719537 855218282 599919207 190287577 977204387 287368527 94966114 341382251 839678793 486969806 476473510 771876413 755564415 965407938 961231169 462547065 288116741 887113992 148064621 671048069 53829568 939231063 63956336 628981819 171028643 454875472 836164621 418319741 317627285 63099840 452931109 80334862 762257075 986206552 365880917 582389583 852448390 777273171 933968729 203552119 143338924 650309567 369329691 29831273 24152958 224143914 334959582 132181615 245910160 835571639 158706484 14951745 379848499 895859160 719655415 284181840 120506188 261101776 175287020 244327671 689956202 674793353 376254147 847033832 875824846 426120795 950997354 622069153 770483599 3923681 807251573 720724463 316330997 543108606 393648376 857624079 227128279 471025289 291759837 213844537 847401390 789599346 276546634 947641276 254252546 88586838 424669418 746280015 216913142 127481210 313088136 698766377 916624727 805682997 217143079 568491294 405340924 119835866 994920645 626567695 555836753 346180891 95015034 708947553 205543018 188564486 741429216 773532011 798983321 7491835 831683312 870000145 759692468 240880002 899175691 276522569 773187714 848138944 77946957 386519892 500815593 63109797 50630654 825369942 218286446 443568308 171162191 148091975 300372115 20787056 80604360 756669124 432167019 518080810 263673676 207470688 811084904 863516512 595179417 752921142 503876346 791201865 187366789 163754825 498195956 583505033 701872783 967381168 219449306 762217793 462522919 718269596 83667766 524968440 683083879 904914186 793817336 897400341 449815760 273227823 508509450 191698716 630197180 688701417 176244535 972941874 254798147 128376762 452862115 375441724 286866017 7452514 263847373 179450339 178149971 401817131 158038958 988177824 849003243 763400153 517036628 924128583 472178950 984820388 568544630 358227537 865358354 290478488 79896045 170990583 358017418 330426373 986305256 656947180 895148798 344532274 732080790 692976810 384585790 412344877 841646179 44174260 228642510 406442620 170254951 343791048 412504756 378658916 965370315 860640942 151439804 173194886 181228734 931325685 850844881 313611480 728334361 645162658 939434006 737909546 264805139 564429315 10974209 484270570 312622215 496730776 691346247 512633002 808955093 650184986 867852927 396140343 537790422 200678318 147080764 577558950 889076549 475045984 681571121 643052944 205540654 56950661 406916279 247940927 649202838 542965353 265545892 628142260 579549506 411668557 95563118 710009288 277308648 172427520 320972616 107060159 682210186 60224176 116195761 366854134 689888940 239643080 437195006 106321161 902962451 616368262 678244175 754514584 363060655 171806670 452095163 735673495 495932014 538451552 39968200 266828419 619203844 454444237 116373367 911951216 606093271 692857440 818550554 650791141 936978388 313514582 954276422 246579153 612082867 834680596 327342304 317542853 88151814 704694582 621121312 158192505 853733987 721541845 180399013 535672487 54499947 413487950 283814345 729192335 994449652 10002631 807785365 400135945 130101102 710491243 717918914 624249983 228528604 352744439 533056840 903008838 738860482 116888227 347935128 99339837 169181397 938872457 97330530 882426327 526512721 713869850 706259304 745543531 150434099 375750866 113805976 546447116 695089322 239250656 196259457 998188611 85987246 818305917 223233339 477997080 306353544 296682279 628029300 276234506 865934111 397004566 502565766 832231260 955438542 710518646 627648437 966590682 817818301 991461185 391694302 892543676 982059146 280785141 629717141 229713488 246066960 411774751 314417145 349309007 736609172 732144129 84361880 970049124 972766330 854026382 703783805 643313288 669669034 230996567 497188638 472622578 431301311 863936001 190835807 913116364 56083592 275167198 92245925 481400400 145180381 107801518 267463593 503280961 987581275 312747088 124069012 965805667 973212477 821961272 506650114 740586426 666371379 723955042 276571750 815017567 73667860 626676442 194153398 329516983 218685088 693640968 696472134 487133823 192011907 750612056 466315834 287919949 249950452 615498681 174267509 494998406 555225351 394572035 531766137 389420403 626518525 40380548 651470138 781211527 674017012 159411403 618366982 487250150 804448812 891421981 71333487 546662650 502326669 865031329 675090168 715251835 649621951 749030384 348302918 810669543 758835087 790185801 597333861 837409410 825638833 755926792 350733444 391912138 93081769 791900298 316572371 412520616 82077274 717537886 971359630 883867939 886522214 684783831 714727504 573671101 516573720 362015044 8609368 936027561 998894602 764660086 434075388 336571694 194202063 291455338 130842785 16947371 458140716 513902119 486979989 164845253 514220622 454717488 269956533 709468988 241827374 91785483 490695042 266000903 638511642 589793815 948680313 961325771 804350376 509773509 715569980 884296631 580389637 306440003 886338038 433932421 724967484 459267750 172471597 620928220 653056519 36680282 6240701 155952265 12822912 46035466 742983493 1766586 238216908 5010922 608239640 976847733 154949794 213590115 218052160 809030713 685260331 137789239 97772476 936489835 946426799 127775611 157025138 69352786 502733223 306749159 679750942 221745625 686783244 377482711 566618819 166404932 594875839