1000 106
51742758 721182979 711598058 581133136 398002158 41768968 924875547 953829800 952016915 771762166 896171865 974389788 98536999 642770196 527477019 942113724 111897437 803153923 33057370 308664415 422498256 754147895 7689544 121606517 413628175 506349360 181855476 908772114 797433501 524620382 854545822 946711928 234737853 381771022 266742934 524153578 14509918 569495468 366348913 960497681 834757334 707681514 823148957 594815121 361427005 65709085 28154118 223056838 347838410 123363884 862085141 511158338 136574767 990817478 738088959 837554408 225760354 488835109 883521101 514393381 319519701 41309013 885296864 835289162 549971916 381831012 721263024 27651709 849935747 924296109 948562543 439876768 251071692 674571613 40231461 540047332 331876135 789654080 902242412 962379241 958354633 620965577 857744279 116919126 31159917 588222038 797167878 31707744 634519480 344841152 670141935 73987992 489618928 285710406 128298407 898728841 242420698 211846970 788804185 782509996 636619672 396391424 568257203 369206646 966293340 844393908 329876205 412664564 18277094 982406921 592228262 198848911 467346594 879490151 173769967 271087152 841915926 555314709 439044030 119827490 228838621 46872820 299958422 372767366 846101319 179283522 963544649 488203258 93722242 242992036 875612361 38873713 355760038 718293278 367342952 333800293 600316025 172301991 717815524 947973526 777774541 488559165 201356497 562958499 313651195 962223551 479526002 118154401 180494266 182269353 215121929 710204787 357320207 560788234 299476949 415271865 642907417 112155032 733893027 583960085 788033119 441445380 416637448 671066234 118102532 300421702 937435820 402510060 343144747 308016420 35396497 200931995 407029421 508013929 915010460 829138761 243477931 34432296 948340971 485379054 633470630 752101438 926825611 634054306 744505236 993025619 557208013 57238765 113948858 161742250 265094292 319679754 597636577 6227205 306689768 519466207 953856456 640634683 382281646 418736390 490366156 417340288 438583174 877278813 173218328 611901911 831300342 263502312 876143642 319645912 267162129 200824631 800662044 264643000 846879623 670162211 320758223 637763925 892923502 261646676 898774775 539731866 708872555 860631519 750025377 268379428 455808537 24896198 539956129 276086277 200383039 940723051 906213990 20512451 524608706 121552659 645663651 173724245 992513873 706308584 976624349 978686487 897576028 588309140 246722821 88497946 672467198 457996656 553901237 783070470 275070959 179088765 417117373 295840361 805489820 667574499 730128429 317834686 85684788 728857906 136723235 795147426 99349 830781978 58322126 551267254 784255435 378794919 734704127 618463079 195016444 186270959 22158340 204565188 792479108 818704376 297751723 817277795 445429892 406862630 142855506 467406146 114692391 429753111 470214231 452383789 259835180 227791276 534732623 218288492 448193375 832779161 67885812 667082072 652141273 975778758 937934516 160224864 705619508 923445428 790886265 765577464 228815430 527574743 700963090 653251761 990790662 837626732 287937935 527627638 115231654 647382392 714576766 976770075 798070643 720296278 382984398 78474294 762075268 716804477 169749070 973875931 465610321 390729434 595420080 43428167 97254136 727325595 578956125 309146006 242481642 917925565 944008927 182538791 670226330 376668656 131787010 23677020 707936605 438702467 809733195 190003729 110664347 597092318 5960027 746186527 87401948 279839886 311000363 133731204 311099849 119743566 736661101 254736707 449864600 828421418 8683915 433069263 460887107 192964242 719363660 283637218 62612899 349924529 534738465 203956717 355745096 539528288 286390290 569476893 125319060 779580835 296488682 695514524 312939824 245804207 782247572 157506292 229954765 903879715 361737550 825634939 839561883 7439829 896838696 23427075 291253014 488827325 94814367 838339965 994262503 925339296 127921529 193960613 526371697 809346042 914866333 416007904 574975213 651971555 76383653 315542204 852599047 125971887 437435087 707545318 244565011 308069306 631961300 29723208 183378542 966793034 972235447 428795156 189413062 99307714 939557318 812426595 533841049 848604315 746209466 301350086 547236342 682764913 864676505 120236693 115484044 387080876 669241951 221516969 985904557 245583384 467865445 964785754 465223720 34675722 32072087 550732471 669902887 636403460 965988475 333848570 168820498 243013782 2947086 796396921 284651628 171014316 459564575 650539740 192559186 999794188 774122728 837801884 247689937 423717610 152924350 681701181 873154572 588469135 260637510 652109609 950838333 311435390 277632499 504986855 105826056 76448664 542694012 231986869 475919722 399739333 359677787 156725875 429217515 159487783 762552185 178274742 822417161 551519684 110540930 452419750 366268441 622061353 653919736 980987535 16279064 606980977 580608231 225265637 207998184 265407024 495616786 197432790 773770176 776831246 716528954 496799791 600838866 113597025 87505225 873717545 149796029 395697321 401345416 609610156 958446160 974617137 652074498 583601787 793583141 508080798 990861945 907833788 69872716 895472408 475017966 455837595 708624600 682564239 802018431 677807299 528682337 296454068 367990102 163285026 302970055 568793812 880486546 36075536 519459647 822894301 167736756 760626996 795979013 708832488 297245007 928154836 314878465 957990348 27001883 467216361 309431527 674817349 741899004 974575392 837170492 853452434 932564696 654137348 739687771 439491625 969331471 742546629 133610442 58488126 28043938 23181305 740140664 753617269 493460392 129523773 280093507 811885667 452773420 394466781 321634875 951519487 671059096 63984436 302806613 502886422 53809659 269806282 773774541 101086232 5700362 541142996 124089899 6285611 438843802 210220651 577210591 451804879 585861528 346168611 702988733 863170827 254337319 285900415 434603610 322133457 826151998 910745915 206812404 171465225 390987567 624579991 366084454 395874020 758933740 65139687 343865981 796914000 897553257 998108603 983576593 422456035 212206097 598299187 353996212 837106260 174759919 785738788 237746682 505052371 606775090 284189852 584576361 251858932 331690226 869254684 556265049 76750542 301025508 590324460 645012598 489132630 696747360 491716416 436870589 804880878 906387202 152042392 115174203 988522466 289554219 314581522 285127459 826019413 174535659 166676324 773570091 759400459 250168633 675648358 193690541 795070897 629969245 999142677 489454215 683374901 863038006 515775254 208413804 698665377 577662399 758433089 653015012 460423049 265989426 228869596 174869471 218081079 518135198 21875881 612670447 758495032 570903173 349556540 572675938 758591527 497356308 130229647 205774321 672216773 679407999 43026312 505971209 593757532 838811525 25780024 803322136 697364483 538981582 791972123 382103679 412393503 519619803 356112113 922477294 232115794 524940127 853880596 536445848 467444944 519362369 756193270 973009729 619855559 896730615 145787963 406608385 170142080 477472940 262238982 308844023 858168920 45066301 323940004 955000173 888940065 193325679 629769391 621937140 708312016 873698416 280480360 288664701 48192725 840260641 453891826 359611003 640611002 733764243 335229986 115240544 952724324 342120814 638796882 565388882 993663986 505289269 801291786 913739244 510280818 715635736 164324947 447805529 649933964 191160516 151225327 677295571 405704899 223976744 493584511 441898163 494674852 786580194 247823168 911227396 22997025 202930779 553285829 662084996 451748718 360080111 63815601 832232159 517603438 359888128 115000324 862046357 991824748 353244524 740059911 490964454 363835155 486300 839729802 970052019 102183434 890103343 877780751 190365263 658873534 577766844 81609354 918859225 437446137 998237776 596758803 368448100 623732882 741477047 737006655 333049818 659113629 836584521 643688499 615565053 820446102 665796569 20558980 613734292 959713173 565449544 430261273 705483549 284396537 87301107 489617511 151001427 940296713 614995326 918903987 259832369 817719090 504323055 223257975 684080049 285971670 391427670 829018415 864066426 652210486 144144272 245938995 971770227 869121428 837166923 904134429 953716780 634915187 10113373 984630690 197321776 551534502 864785149 858143784 866112402 303222165 790208435 952067494 532783079 362146434 784577478 99549600 516743298 155134178 610879385 633452012 822104128 757184721 741542432 54726027 380375164 469512579 167298110 784207062 88417626 526984189 115396071 418870494 333630512 176942747 842679774 113639430 95452278 333046476 325564889 284948901 874732037 367728009 564773856 76182776 54576422 226019205 626887039 515316683 396835581 991613086 689759956 415763008 839799402 413092048 719001841 284122080 290527173 557720972 176858884 859869887 718758663 669385688 861924743 998683685 161698449 945276417 939863049 843358687 625986710 41752506 203601278 754768630 191730815 615883582 622286482 745814648 164097968 977454205 799272624 220474747 686823062 361380930 335492258 552589228 433071957 336086727 234162220 864624720 14286904 542537461 804937176 5253244 397002687 911002633 643936648 522191753 276590356 686034720 746163482 508721274 60488881 614110620 707560792 980994911 803730478 441796342 3835504 697968386 199360404 859429237 922302905 104508274 4380874 581339975 102623898 458572414 36970636 992174712 934636091 936973498 297929068 186203796 183156766 97604923 533834395 453638339 844270455 19151719 958880652 496963365 168620042 738442581 68077627 883266733 741926931 963238160 142016009 916878013 251543417 913944834 485026453 334872978 251911723 386586584 571889984 814214084 369747168 467146281 769638876 150561398 147232139 454268628 41491051 369919704 638847709 85322266 493861535 350413048 518092486 959220618 317079437 926474122 800351532 969138023 240790125 571682768 862074302 105895061 203176439 226988349 698029941 186365367 713648581 188653588 540309598 888342884 931401500 204017703