1000 951802244 24103593 260135688 331254092 229551627 444742204 613682941 834023288 15959786 724810629 200094019 548443412 693093945 565119987 407430296 855308099 818836983 131154294 926098513 558255707 339543701 347283435 205334474 789933115 184779033 848785182 844646780 510881783 4612863 749929500 681053783 94232170 676175343 492942219 785550185 832082834 179690703 441750886 978935713 536506523 491651749 308833610 57076225 288619405 558981831 523596783 542455569 486816640 166874801 633947615 146419044 315782328 658456844 233185091 311126972 329440449 269812525 244805617 119137010 430489247 917332272 504372020 526839161 550578720 779340118 332998045 374041864 324673336 452554070 310737405 51682680 446698727 498849783 610731150 540483701 955398260 740395549 38158998 300404956 634021128 357614889 487636664 17904961 979655822 384835353 884567451 783635981 560465957 454838188 385768351 393042819 985316375 714759061 754856902 902257920 922558832 814044055 928565418 484508718 20978527 681393437 379629066 162722950 25028157 705922214 231421632 655055227 858125361 690800159 375363021 32151750 968365697 697172107 958584457 430948708 653846934 419927036 598265993 43446802 868525597 958683889 243252396 470058089 88197553 799500715 647418604 416047803 261080457 160370826 731038628 558051259 954924101 931970264 10913719 386536229 793638320 329019959 254814737 812503805 839986019 408052999 117946168 484472760 583523428 465268882 922707104 925858073 344903588 525163716 712819570 233405414 991313994 717577971 162036438 744221139 599915865 267612353 165643132 807450346 766025490 34882059 957174881 138017677 927756808 26472303 853181569 848675030 493957748 832867138 631012024 123564716 948183091 219034034 647625993 302666444 559879479 357915294 467285221 615912415 300086001 294737477 53718736 241257993 509205994 728128486 403597591 146022671 26089628 22431943 635984769 576335955 85179165 132455837 67372754 20023133 830361534 770759508 301690124 989150053 30260986 718042461 896249327 805396751 530843733 739965417 124351617 684513224 42065243 921671861 660458016 740804597 356305912 180204670 536345119 825641236 44871291 456431631 249800134 161527046 544023993 405802518 429771174 57577517 303331408 553052182 571118166 296758114 325644866 256750901 661389345 908688423 68205129 942850513 441392035 52627295 535794370 877048210 993364692 26520650 263724738 580904828 843398561 485926123 493406063 918418236 987645921 951804524 565061140 20040169 192589436 353784442 65463787 998394023 670045220 101192692 492021298 439195923 520570670 316691564 166787869 226333414 727632527 349888017 246058879 55791625 243117207 677261016 131051712 573394433 243118155 361953669 925820962 776344579 552550106 665241605 665384635 961144516 581929795 993585759 326521156 25198197 288127631 911640688 867456850 230107928 353047997 420655141 805328503 187289988 116914679 508259880 990058003 850313306 277315438 82321828 994658735 745488931 242935668 156516013 54560177 832451977 126647188 452350066 717573041 582758887 540185513 11992223 99255040 331618437 254292958 811603995 152317714 997177121 707324540 680218287 981356132 309047159 244037118 431758724 795717920 318281394 573924484 940191438 966755316 118761289 524156083 109577517 618358868 571471301 514446831 390946200 885379344 775702669 263346123 102758804 981947267 681835209 715923021 579556430 24948264 169910248 994234722 920063523 279461296 836497689 183510334 289442638 963027164 312620607 268046170 838770279 673582276 335713430 711131183 770624846 618845225 431783507 71159397 883193841 194330575 364401250 970754 83436104 23476765 919040534 623801011 830034502 571280521 524873252 475530212 455003996 368137787 988412185 543493894 486776478 810329846 875576233 372297018 880587236 239705243 311680000 648800769 50964636 812504847 95401381 79179347 274886244 718343654 458951961 612046222 885331620 938154772 421702055 802715544 435361916 90411646 101049661 38935244 375363204 526360827 838541015 306056757 950610381 438773860 655796847 723994167 722722149 359585395 997681576 840876678 236050370 429213081 885674578 272036779 468215771 568437651 154119750 768348216 782696277 462787609 830307175 921324431 384567952 332959547 641464226 11649602 1584056 344925303 33132547 572376100 253482185 260453448 560334373 343970136 374720131 945928683 190272779 688141842 774327607 640374992 799660666 403648928 729421276 137234904 94461428 145726080 735570190 55423415 736101767 19363947 121919117 947583288 28576326 998004812 130517286 384998399 632027169 163858393 39292801 947530817 666287108 147864009 393445882 246690567 435234167 151793374 188699450 265059 566297788 21307945 210679663 421559637 752014991 756559919 916555332 230749487 462854901 16321125 772707640 119752303 835864716 321445619 172083741 841693084 275877798 189028208 69728073 572408722 222381 40000709 76591693 290609862 43885045 240837727 991308490 965711441 739109342 310985028 818773528 902994396 855947555 909275059 590689713 445289239 453851436 112257456 6040781 543116457 681457896 831953670 802886552 33054607 411009827 933823261 248370090 45110985 63550940 64097565 370453408 107216519 143252773 737344188 89282348 195117668 273223983 603186644 922967989 444305752 419828702 416464577 370201014 933033248 769776221 18055929 840508094 342455427 963789478 351400534 852719639 856104054 84502298 278709643 164056536 172584092 975875207 698620296 868017450 445723477 344955890 792008503 749003033 679780573 593632533 94295954 435329733 160894 41361465 968575851 652055676 668875662 666253343 238181955 375057218 487502501 481130135 411070116 509138067 541021657 169499854 504243749 275440785 100653120 752185344 175961733 571455660 679841892 246342624 135123199 559636260 909872942 98613055 741579195 574944665 87133070 30629158 690458509 843131554 402739477 105016412 300883028 144410806 280003772 799950676 97803987 139063259 923152391 13892569 974757927 30758338 117855728 75715226 162534320 526250433 724894263 143913647 261905942 150106154 89926954 50564006 479941218 601888979 624403316 574293297 689983939 227644976 85799221 459017515 590491443 809093607 355545321 924798062 172229857 938609468 765489318 930697760 422771570 187480538 84113908 59620864 682448145 739260743 937763668 866044749 877269642 226065506 696685792 333816115 614926868 705529796 977063866 195475613 748627987 738495278 539361996 525303475 200083010 498005374 794675198 207070075 702023270 541459353 854571261 440481119 335575849 646354130 991065566 271007347 348436665 697501770 547689794 532835987 877320667 893224195 657523741 896648376 75353651 417907445 121449789 586331952 746849682 906593680 361427231 268721744 670540285 439627066 106007485 572528048 793674020 269486425 672397032 685156716 911257666 16924839 944430424 823912182 324826308 944179350 858169766 544835721 683886810 247212795 46264555 239704314 589543725 654807070 62803918 668457299 330314962 59168169 765753206 947725106 663943335 509307768 96749430 51445639 828005583 245081361 821282295 602768915 847146718 186608730 748377601 216148119 363507120 555745909 40503986 121843645 44525931 109542174 560643478 368094818 484814613 4446583 460961671 221036091 533730715 574617138 185626647 862683883 156809683 194229183 347533090 595730876 265161019 104010167 639464096 924455522 904818868 621308378 594853622 770601809 540810063 599951933 986919694 849602085 523415617 43251200 611942724 611215380 252169312 123529864 40152705 583014249 66765451 992806656 737020193 836815275 649317300 550523727 356681390 897781710 215976556 620909302 144680087 807152443 592601460 520388674 517636377 67525022 308042799 95513578 180883894 822730284 242063393 208129636 817311474 21219309 682520067 209979424 269003286 601422876 339783008 804395523 685537753 919885092 551894714 300838377 681596532 361897566 500130973 619777362 55167384 454487566 223234416 382217882 27977709 901044833 998450273 16169848 962812941 106183521 222103932 896949455 394558996 420909466 92361183 785523903 882185913 547463886 919336532 461271100 165208956 763742941 918746835 174834656 472971773 493634836 119763073 968541900 37743998 824672720 794000675 215643970 271530668 132312826 194295344 147646141 505653579 64686667 703788176 860657880 397936292 533638496 378999676 361004817 192942886 834105372 256188690 733235650 152469766 994983978 223715104 747606776 59429518 745086706 230705804 432337403 250583988 316216402 112000615 501749352 204490571 646814270 501172672 816388147 757219172 943189058 422541160 347467001 394128105 817109871 298317272 203439443 442214936 457985690 414111267 36980801 962892408 805551426 679776326 899179112 918142745 436697384 682967965 625927760 541095031 863533132 410491793 891428427 160602106 319321196 963507437 665138883 361828839 737200271 747850867 682331047 554088259 924384942 97422031 463963841 179639313 896331877 456404890 629014249 268581600 284628216 818891004 59891429 5609251 669094991 348899378 478757506 883922656 388519291 618241140 60347831 704762885 571285177 165934077 771971106 996540464 836160851 531787475 198543771 326891002 136729223 725307694 477106960 535888299 887179809 272703067 447348894 233946704 626389937 967384160 914073981 406665152 201721016 320079542 101433814 888147576 552336571 956639604 670064400 160137417 152027084 185683650 848689714 477463389 102769941 105636307 854202150 752662561 545766712 732579952 216084851 84189161 722042887 719287293 816293473 994575559 936221778 244951090 847230879 502284593 821225055 687719070 461571995 76798086 51724608 823702681 215531676 676483861 676906299 390028048 388789462 280179456 579611940 97895588 892320635 181359109 917116121 591620997 482577894 245970735 641891858 364066321 371327912 226078997 635829632 29465642 371135985 755642826 867723732 414707986 974904345 297581268 404062296 988769989 377847203 486869170 432403729 312738159 79743661 247980185 562986909 283779909 149963831 478294316