1000
915052081 460464330 444179400 994755420 749788028 955156981 225201960 601393600 779761232 664169136 228456081 483320434 751502074 283769355 948463435 772894082 327334716 100310765 726860138 232239172 327934234 592122889 823981045 863051554 124690436 926810904 632804390 580932973 783277214 694595995 383085958 790278023 643359530 236931692 812702983 570208471 600928703 65269718 585908990 509048137 652158307 222419095 555233682 237554263 856520518 75893488 882561693 827724442 534857411 834835972 725412333 849087439 533756855 665283541 175120954 24492963 60228240 32251562 11702357 532624280 112455862 360542358 851539393 890255072 726745108 444009172 153184816 565909936 842991239 690628432 793577614 29672046 954409265 539611382 769331801 109344750 659117106 597223982 97426877 600160390 961445311 717777855 504557743 348499833 215891550 418828930 521648784 564291929 208135279 31658863 792536563 397244762 203346688 640565041 563943369 661220438 130594141 177814045 209388548 779504329 703738339 797161327 387230753 401739843 711119152 246588606 544492394 38572714 59187637 364381185 446788342 692865627 584158933 287815946 126871716 974694982 57173666 824512444 821997693 217278592 328681370 507438043 521418580 672675154 296384921 803550095 379503650 62805166 526389664 638822346 27453700 673598422 833518571 399780838 862265774 524844608 517103615 429972533 311031403 568553788 762984433 680477141 732201860 760254922 350647607 2171056 561131365 651513640 61374714 94614390 77265967 305850554 209458973 338138406 368070511 341796967 952617031 675651550 209022221 150678939 270913776 631211149 663041127 545709925 4183689 640247915 690442398 23127390 501371498 548562740 326733815 278727375 695542119 333983529 914333221 19126423 261464549 631155796 916528099 639309636 523614273 767506270 880082565 936952600 462927161 520121206 857538517 112430330 13417362 652743107 826056722 897653261 422797323 679695936 609264667 59114511 203414925 566496058 317211036 690140974 584598543 66695883 807940266 859141359 39227969 123890481 700672526 175023742 788536514 302352783 536743183 889399246 375148256 532198811 643314029 954226656 513329640 157959393 171869160 261749365 415828748 977751938 189529999 169084511 929804985 849392664 370225232 377822628 610729956 278024090 486524405 982240159 978197588 871998556 457287899 621694712 654783697 233890829 428978287 805350073 709575343 804251478 101597164 838528067 18347399 630342805 835557924 114379937 147894193 20541226 783221825 144623387 672453771 416413943 392245444 410979383 563168078 554309351 188628996 805086631 112518776 132976784 528396655 191225137 472840582 547926703 661246863 894933564 672337643 1330658 3903432 334912377 280707826 384625269 808531699 155827987 578603224 632163533 634496131 484824863 176285003 197145325 696448808 360176495 152155781 683399982 823967759 738528343 695178798 411480523 419350753 525200438 845760180 860456035 667416372 846834316 85870383 94448808 124602355 466174293 490260864 118154678 552275565 814229187 498034478 953667912 836795148 582100772 235798796 560201049 144596692 289535771 972327978 408488687 836136748 706265528 212677685 803432045 467859571 159562126 638508047 476505110 366901072 198634737 915171302 232669898 441558604 661786083 714572042 957526178 461830390 625596993 675104477 133117914 708294303 616148241 743833695 704019766 323284143 640981396 470951239 864816540 825508239 506246227 430531545 962098362 825291470 629313632 452385588 842575155 449362171 830684751 319383819 699625281 90403526 259400851 339238715 38817627 300255080 431441619 224468751 839258814 220296674 645616018 816769156 475788590 504341506 529564017 456699433 984801372 599453033 855587132 519561822 922495587 202067116 839461291 972307611 294923051 503064517 580609992 380508053 946281923 121277703 503700897 255678721 633986669 305814018 538056649 61025138 950990098 419101774 454526859 254659510 760452149 847879980 693600983 283138263 157865658 142810530 9817761 468209950 487631463 863409090 956821942 265537701 120524508 978057172 372612589 803853772 716134172 278886736 665290548 341251502 385485103 497742975 478831268 529086439 935734404 906488375 320297447 211656641 699886590 304061384 908232665 723553839 365509073 369757087 960439048 483795175 545175245 307690748 692011096 738575280 194716326 623762661 413683027 654315224 631571062 488279502 468377108 995579238 285328886 395656725 897574947 260811737 616350622 974903437 443168543 460478142 947914146 986570285 814623445 350307815 244344142 568010107 71589629 980560416 657242478 542854564 481553425 62890937 496500878 255783 292586663 227203432 475118657 96358770 532237881 139273661 429609525 61685623 613115696 605468569 809009124 138955124 176996670 443664683 978956269 781661162 867098566 245163186 356325533 375850279 934263163 84634046 208420414 830842697 876753339 506476738 860880938 211382886 463909515 982478412 334686403 648331117 414918864 537613834 733890698 389500387 213259104 700480500 310031814 251866221 515725248 336445182 970313084 168367132 315631126 523427793 373916156 441888255 126556233 491451290 361989737 328970541 432941541 692982564 793428679 886083080 22068667 344040601 962173426 854372642 944397045 916169426 794041947 736290226 777132640 799507751 840730253 51857767 220049428 21033118 784247438 563657248 201630515 680270421 662472829 924319645 931120810 518191910 116165327 543857238 535142493 580160697 589970784 177477297 248653630 139440921 510376273 908857720 785104988 723345882 638278570 199417249 443945810 160756173 563065658 873508839 986388460 69000135 186432139 797808150 480124346 22456606 947490202 962529984 734119857 745049550 375898320 273151620 82125874 206858450 143483177 226695274 686122011 992934036 375811690 245079702 713603983 940635988 238784307 403300391 164128500 522162325 759300835 823255382 106559726 869994272 135582652 767305367 141407106 523849421 261492943 499250871 692641480 655227002 530110058 197681634 249110181 306135130 131422800 225584831 824072972 588610323 88423902 78981387 27911368 132902224 537302640 751221098 221996093 726660216 724864633 166193042 509732911 224699691 870159775 697161512 854349917 36583551 751185764 173912745 622829550 931002631 787662078 442525135 271108459 815751939 861607472 566562005 384013074 395163113 321565868 479543429 123461865 677280029 98525521 149783566 308959800 828179577 837833928 15095657 842636572 953110525 430422814 831373774 235300140 666809599 470460095 315828672 788529466 724817644 781740550 554578034 421216287 213404498 285802169 13421038 565638926 965046194 859832044 436459884 691218479 144630565 297959452 912433852 421332369 860586295 19046019 11025203 796747286 733130072 25318065 807972805 814743534 271427524 939462046 167658166 212821273 186819079 547324698 369043216 746717162 528145786 673943273 621888002 449533509 403777781 793224708 949348178 150377492 626201819 419625109 728555612 700835732 508426933 832567950 261520117 379638044 53605739 477289579 252114722 470999767 228096119 137146545 560143715 689412710 925439174 841440369 93114414 476393951 695506899 121428683 131235596 941957445 534723065 507593432 743203835 863333673 584035352 353431866 176287272 167610604 226541762 21958068 256535491 577554918 515005582 94765916 613013083 764059927 908038757 562841091 22990470 800475594 941074292 606388549 193710287 642929680 299969144 87901789 489521257 189473293 463731593 901442537 583856079 936313712 131425594 171805826 439422875 977152508 509567126 642857116 134807405 513908532 777408860 574661386 583297110 677055518 478261989 541727297 89700758 17650566 212593865 72107410 110181628 847045947 82768767 911982531 87738231 89797337 560599267 840286325 158807495 141570273 992350925 952694907 179431313 343941792 514440841 772813399 451322802 84300273 295663577 803228739 932564673 259392886 127584762 625587548 679803711 968318730 183618401 890571085 153956279 200877415 473473136 949919762 133328953 146338822 430811429 226939104 814051815 779667253 245305524 508918891 547322120 378872068 940116110 942310675 668042353 505385945 659591488 21448691 121575486 968955179 137310768 899205286 254491349 812367659 43339172 957887381 635908328 788527878 183502655 974890097 533398032 628686342 391115934 462457134 152928771 256187530 760751068 698677479 731025206 569295881 19031090 303947690 957023625 255601402 874192698 50275122 311639841 350594036 984039292 468228327 966174694 78002885 852218752 408678279 165959736 966859655 546430086 57725533 86657028 964401191 812281815 103713874 119130666 262195725 786019196 23175337 812982516 559766711 665919681 561414251 226729708 560605869 450955421 281976933 992372988 329970131 658868476 99272499 710971625 275785328 785492321 586229860 19622520 432255328 385594835 353595245 752313015 711575230 573800297 619668106 212354281 2865072 199082572 794168052 1236934 745957318 159121025 856547139 961084756 670398346 54454957 913498695 346054905 512624195 319045385 609283400 632756701 22103333 129079341 257745230 721828691 650448528 504306061 616459709 551309660 556463711 834120974 431095414 31766135 763079092 217937664 464467314 640616990 301471630 383097607 963766381 925184673 369331304 100362877 674673920 860410034 345510462 142398278 839794192 813209310 107031942 434957395 399285459 181493476 463184869 214514300 331622512 608789180 387116523 979190720 545979322 54864821 486488673 349404928 462591929 785720392 359983384 450711253 553484988 504414275 36250136 791414122 159043348 494307169 88035947 678157742 629611775 37864534 679523004 159613694 789693192 364131901 639032288 968548203 385309903 623784850 625443413 470657739 393633390 584475572 809370315 41824466 557888023 759628600 716512684 106378568 592896546 279260111 934645261 174163254 339420741 221653609 61227023 138844825 572985036 469336543 938298817 84435517 283472175 244635318 805945013 319653833 406010181 471825115 513340256 95587538 436743241 11285723 347894330