1000 760159905
355720361 411926150 837671832 622577708 276875862 405634754 3429905 371142842 118487409 239324672 30863674 79876000 118987981 554834546 891686485 70324850 969375090 235259170 891125900 775502390 797835811 513183118 843797605 453664817 679909349 864683762 379393810 841254494 206190461 524806789 389245052 539862149 319084161 536517203 574236419 855339422 943179668 303852554 104683699 838436793 277100588 52175809 754817777 895898817 122034599 795341412 528541605 310548560 202373660 142644879 437737761 675305577 413670443 322668275 430850756 223656031 634925048 377200792 830533710 653512468 429770997 729937399 895655989 635044154 573127859 335751471 96148612 759109097 597676218 706445591 934904094 633430526 213129377 234100275 773038533 310819604 987158508 230405014 178490921 668078895 733397942 384102252 535795552 515544307 114314920 991027829 37418418 194985184 352939788 786503320 943824204 89931624 827430871 597465162 157048541 742670114 151446002 625485694 197475084 2769479 697619352 16223163 144907287 842581880 92850515 159517155 19799077 248324951 320294031 154552360 979386428 378180670 851212149 574229055 170215901 945635147 273767525 268238699 570463136 548646434 821034201 967383459 454709268 186874055 708339385 891779452 747645934 785838652 94032532 957459041 534438523 991044181 42733486 710344012 99218334 656669542 47045240 771039695 175115840 419299623 623921908 158662837 779798310 796872884 450955127 619807888 940454996 954064015 332096994 154460951 639796182 420778489 573789777 44268777 80265178 334850306 136054782 213520791 221056326 701497598 809294645 428171942 642453240 176820669 112111257 469083974 708272914 90019804 660899916 571124578 260279352 524344757 165826885 847528017 106384197 244695346 198275338 441717393 389005121 377978998 60483947 758960295 445749984 424219812 269638610 644697576 682496964 373729999 302824295 699045035 987758607 350284242 500805644 769232516 104183502 337593145 53579630 28538238 965361237 925739785 407205162 903532481 202059661 582200987 220180535 216635784 670096034 904834515 876073968 974893436 69733963 491219067 180234628 623599432 206977316 639582184 130627330 235492527 299205275 792466477 273735486 905700462 867752718 95343923 831280039 266603482 700205802 793789073 22050383 639135604 491168611 84856665 234487364 718876595 610022879 91598295 777373421 250028039 954057104 141714558 514193483 130622182 478584450 196797216 363158666 160696492 468883146 68865795 201457965 778594080 182013968 728388687 314148419 852603392 728408294 556500496 762090770 792295119 197393305 147852879 652862166 207426816 393929849 229781532 165809843 797506257 604832728 717183058 447232453 73666615 96339396 938889042 739463069 861171277 191759325 382051397 410233551 257908643 34968554 431103493 808583273 738768547 303490696 57148238 869895366 492850360 936494999 721570211 76094661 943775161 728113101 30754212 448806319 859554350 958183203 278047550 279214258 737882194 991470470 86791107 556225875 643782612 668458722 92171326 588661297 675423516 80105438 454968931 234109892 289189146 726350071 277759026 867938638 99345832 785424060 209194465 256197175 476326535 730473934 5140799 708286485 826078868 759114551 792489871 786452438 636620180 802981027 502357175 465994152 519136326 22156565 587616020 679146878 168835692 375598221 635025665 834744783 662999975 318848132 947920847 404598934 943809929 326539447 694637067 70039407 864276419 951735772 206407401 744396115 798670971 59094813 196598922 346898140 872551236 26811811 498544756 294434873 643003139 154452047 946662081 654427277 389467325 493619164 347333239 113586709 6151323 838757580 712858973 404073724 380570492 335056996 771939721 649393421 463946529 531435002 967795221 271210444 426801150 533969603 885743574 666980322 564109647 526524216 837732043 833124576 166918665 992664962 614446648 902868377 731431954 968143662 903328828 554949847 804143833 521383650 458614681 354286149 714765560 165921637 274126183 457484928 671616732 60503237 650191627 241297199 142544855 551075410 384236347 347249499 888017799 170901469 739658642 37879718 74283076 591184007 713562756 120076030 683097326 18933526 157219432 318453268 445875840 173633844 250519975 200369497 427932880 550920083 715380606 420061928 413096579 412968715 939939406 788222034 72636701 684401744 286339222 846063299 996609217 830813521 742160157 189093009 611253725 505050220 101594884 448181101 389833052 413927736 16677165 262875450 920399439 724098210 720899457 257817406 239963181 108889582 753825174 153858723 786581127 463572098 240079048 795603608 390394685 325930924 636826636 888065365 178763339 57190337 243760753 910777040 64715277 741218178 935183516 668533019 534274353 872935726 240438391 768417148 206630828 181210775 420576087 984814492 850516918 141791400 402051287 60853853 281749836 542948260 795041765 72008326 112050040 700453671 312528274 292417243 379838188 938050407 316814596 598681402 585767949 139980452 112632588 495500075 801482930 173200726 86792132 39134799 124470878 560558947 369808484 879594803 379862922 606592662 47494687 136881057 15759892 80994280 384090668 888478862 961151968 858224946 306304005 192100049 299734059 285887516 702423859 432642328 56133362 737247079 566350176 772448960 452959684 265510692 588001324 78393679 51381586 826942768 683533141 713088806 256093629 599817496 917651344 226125026 33530100 726921831 881556010 84766930 544951677 310335865 338323821 714204177 107796677 153274414 363983530 794029306 285992857 804026478 722974131 274933859 87317748 408961106 140690253 28138432 560073462 982927556 167318585 14530161 445567666 8828083 16103001 120393127 785838052 798836100 151148415 856205296 748772998 815304154 902856371 413587507 443765470 149414073 489689365 440024514 473208886 405926181 819960866 799776424 515838380 990552176 255611438 574418195 34911303 440000865 787733715 977623963 158194156 704937853 674382882 613061209 143411798 858160606 403229288 222792961 41304810 777452631 999505168 231858083 21626526 559100810 180409803 115705155 659021803 346908434 28014020 350520601 558879528 370974339 89274843 422680110 731067876 401748621 920324951 830745194 198556151 807743497 584602835 91162722 762060183 286519725 853337887 101151199 621070420 820201079 85570612 748580721 572682793 308020330 66244988 513360346 172401455 186889504 877509479 145013184 887697645 939023758 638960316 538979081 453523065 266699279 128199306 29853033 563082074 20889656 172427030 815076671 270098369 526476180 657079017 438635653 84402163 480158841 26131673 343252856 659440803 811476565 300926273 179970002 115749603 298367794 47230881 286577480 816190353 176519317 126171217 13708479 722189438 46386265 30443564 841097990 431971168 732491722 602127827 917727732 565850762 820120570 775700979 692363661 935736858 805288546 272069028 821168271 786264724 135812908 271859680 517282734 811415657 269551616 550907726 140560319 74779882 188423191 224954436 404800877 227090984 928573658 396146041 394854801 161387365 182172514 25214796 635990114 247841802 264189759 287759515 112126789 66948502 852798576 74628221 164980421 957407822 32384489 561837111 489755133 382451859 842288426 61576168 260914583 881195355 593942063 47170883 681132113 757785970 865511745 139453604 68526045 293587278 969089211 295842157 45851556 862530858 676144922 141803606 597299905 896791682 689299634 709681859 942309459 147508591 714479706 364389811 43215061 496772634 114964723 153900299 133580122 184488212 119877517 655632579 367540455 625661539 110427647 154414539 338554958 381650378 103897666 814222495 623625789 435085971 451295440 556005676 182736996 416612950 370150052 679337960 83055616 889292660 649250887 723691663 831905220 891396773 182676081 460715848 594154499 227064462 617357505 282560673 168233981 864858727 896982790 852243801 693994657 174781473 866885696 25684729 240547273 266285639 565921900 781716386 715554150 158361914 226154992 92630572 56759822 971992713 866576494 448388861 977975972 660840151 171695521 570342091 596259096 341434106 62902907 32272218 648103988 22694828 836289569 745940252 288654109 365522930 994053138 750501023 148883851 732616234 317494448 666602333 454187720 432582203 917901775 457077108 391468748 368267814 560672161 650834450 711059119 232551750 807299199 213510822 694708986 27966577 610158982 569449342 494687078 823729643 929575249 949378604 564004282 40117094 758031079 501841329 619870302 99526266 379762796 589278262 257311188 334543364 333927832 178655337 444942172 974779687 197545961 720390215 417527379 232381184 521471098 682642792 646317591 820577228 147160163 550175156 482766426 27359168 280110890 817869526 852843531 230849124 20237827 634232760 232064112 702634079 610308421 76897727 900139936 769670262 466440773 759343896 168161013 372225627 741113221 701589940 482357554 236826664 495445505 824363681 556383295 986081063 184510877 297782688 68248317 27903001 514867194 529283966 909921396 610537979 427059449 734749667 46396254 79800138 291284518 132938994 833238565 255471552 208290829 539367538 962337576 643253609 530299810 570187718 913449696 275729620 963221616 277540756 724855409 283236251 888790603 278879987 269691195 634303036 454214921 515583364 233250988 349653197 94059211 48766431 820147110 320789242 367976833 171913127 429190714 284705619 949908913 47647436 347213545 297468519 488815569 141096108 549896402 232694480 626387603 542195151 611326638 236423281 924935151 45140421 370455716 803855925 71978345 765474677 119914904 655495016 486264929 848970081 220207937 412031954 324843330 30334251 239360908 15087031 541466672 200315110 460364533 209366900 395871068 611759063 59670465 875516544 160449645 658089314 393555166 606931066 555690685 716712589 458498409 550101032 463969213 759551885 841608185 281420339 66147360 695052097 568337378 85667570 399578834 526799728 319402894 365271653 782645892 556146690 399945810 340720461 866372470 162331677