1000 999
294793187 756195953 359186269 754852119 54323064 922265669 693022072 589064507 348418791 900435761 220778869 682809595 311568598 83153957 517004695 744623709 137718939 342511069 533034806 981942091 456521948 39031157 877349620 694557424 80184991 269636215 362932912 6686820 928253755 299488844 963421967 582900223 963554695 425573163 949325222 964954345 969528333 687954320 686868586 181620345 221728235 113832561 589253498 625950719 583310392 70937955 187522317 981035820 700453922 62671699 526950498 777897240 669172345 441961014 190378667 607640800 51454982 777649409 561171112 381068411 666729740 72526430 944555217 246167653 278632970 815562181 475169178 797679653 472713557 80618528 892999191 542721157 401659506 676534499 188044109 264958792 921350533 612382402 32197079 458636707 609158222 432527676 674132625 759149291 25490915 495194379 13243142 965886090 986143222 304034087 752504996 802336181 901948687 607126000 685475965 209246107 476680518 20412716 653997077 189356658 334379279 542775907 544813018 109629411 835883669 334494861 223883084 603995225 695271765 691604449 766142408 448146413 758145497 887010405 611075085 414999753 904312763 874990799 501129475 114311689 195489562 214163009 310576613 125546575 491865484 523294660 536228071 459545144 739944619 172845026 965953566 627652375 710221778 739023748 254154839 922993371 459149958 648665228 801989977 70677412 269097134 484545986 734904789 183361895 948285337 172272441 239448676 180140510 816620995 72529577 731292661 732140456 234572460 238960061 301158883 217222503 326098158 368089076 168844986 677782478 891752057 881365495 452102295 286422737 311046782 329848380 313011649 835489318 330327714 206308611 102606898 937924296 853823079 131961200 201245239 982638843 821275703 154501605 319807708 302088671 336593370 293844209 83776893 701704334 911797938 699400773 536363725 896145482 2770002 108583708 781678163 347851404 348925181 648323963 991352174 267978048 824820233 299392058 487509512 207731658 20225066 742794210 46419052 794365763 242386572 18034673 302163053 670742831 168201797 631791995 175841944 825396206 436688166 256453241 34392714 998662327 557900520 594750620 726332199 115898319 59780204 85876769 756838906 9951609 221128271 215330074 370264888 169022779 162388831 226467638 720534392 485539610 30083652 102657776 276424519 797087404 523209461 884364134 54879511 321999068 545086911 617237322 800004780 491370219 956725390 805536349 534625547 85203056 957013481 9165219 43360267 653305398 727930524 618659830 403791253 859153120 296019591 814179364 709489711 856913114 683243373 530979747 835692284 785570752 124765504 206697144 466905726 800412295 124225652 414503746 635589811 748917096 847069986 925797486 809898077 20402233 827485740 243518265 624016674 430948984 944344080 445714387 264881758 532553202 415793044 964305363 475008369 425298313 441292320 619450550 987069236 488931107 131321738 635163347 953746485 997279341 360978024 429438981 686891893 438688310 920645120 979520626 439423912 692893119 318192785 17453383 88027164 331508880 596575655 634396989 233731313 902969338 612994823 797919078 902147130 838548659 245190642 950982652 90115320 51687252 237755378 247299087 640888434 387059239 757054597 661371078 450687757 137613541 98478094 925755770 937662637 734709889 836996619 952115632 988559285 642182979 751154810 78835421 478451384 752982438 226081216 240731279 736732130 69925283 493311189 455122625 108236473 195078054 242105206 597427395 928953496 873169603 390140039 103875030 880996644 819657894 579507695 659191755 954147916 428033615 77611182 855246858 621017361 934554822 74482704 890310140 606643900 553678273 288350678 109525645 315597670 395660640 13683684 243360210 843064280 497982960 575682627 508939928 272073725 3844363 108815912 719090065 230001394 105349379 22723895 73494244 804415728 789567863 961421917 878861744 387221419 522403756 301793992 453808421 949530473 552038830 513126086 128299119 672293328 613402452 83560891 772858951 670406874 586687138 254279924 944645202 542136507 130893407 299593070 178010212 301970857 685591154 539994375 280993577 869935644 617642635 126132074 409217112 49128740 575903969 368995573 307126096 107644030 812217932 273963764 399365751 422699224 637614239 503992816 375836385 173404980 733048401 676715765 998045451 250942151 890788746 53300268 35877418 703611398 960762917 953695322 811439364 336764898 207444607 918812157 444348170 740207181 307035130 903243718 886552423 152329933 697848851 516503656 888183860 554178394 412033425 185074192 951230481 806285992 358225824 165548772 640298636 836706207 132050947 926352866 130301071 133389839 307038724 272622272 245425253 815963965 714763865 669951087 358687802 764649211 513077513 760728543 632203845 17059976 436890929 366707351 652234122 479648246 91931003 895835516 201834571 343880815 408279718 865190651 465522416 72766118 970836360 226630974 730793606 801756638 883499798 830074453 240478622 518989110 895291892 670119678 202618881 497114198 227821279 539179245 482457350 174876141 802184604 274491073 753316009 389010448 330906737 535317659 848388798 405646011 87470883 721982038 564014983 693119484 434501794 359547842 735153909 414876440 750659377 122927756 877086458 724613388 234929255 908195412 81828243 789877373 200987529 966530113 465429871 720792843 402158367 117128643 576325250 651909210 61702659 256369476 654944737 479610283 399290084 811344009 725841513 68954332 674648800 719481654 524491205 254494410 885889873 627667049 179564532 419086661 457688417 131356360 480550309 443919647 738271045 938814517 426218348 112477157 16147642 577015023 365279305 827750463 669406297 238002300 707038648 882499317 47203204 115722979 680635509 553672133 204200612 541045743 47864902 27417732 173939210 956979587 20130528 916865661 5632665 115741524 468913349 247476246 470492609 863990180 261844265 641187016 428502316 803528073 362423529 777395867 912351286 445913407 636562850 910435203 873928666 54294434 351903757 628629016 851166436 419743896 942983456 588343215 665242945 137965838 887764263 737765959 15695715 384717491 749061343 382499072 624699825 224765862 690214015 352779081 368595390 637567600 484822138 91838084 631072891 490057114 362512161 392559429 140324866 94963486 622812927 690144305 108233196 918778387 473114351 928715631 369975371 73217722 816532920 629137436 294838979 712841007 391501136 917862321 838475884 280600788 889050988 51125354 293322415 158495262 914729823 375218352 60036276 858737421 744048439 441419471 483400227 996388918 377320793 786210315 623556139 283755657 8204512 716623938 112883569 521049192 656209757 423644611 212818619 653108105 990095 296728851 654431321 444382517 395833766 47575846 412501199 672992635 669262046 299899289 460024367 777976081 673187784 755981600 555216004 682764599 846162616 905321054 325517117 247497635 947549177 460852022 569531388 426429722 909499876 161094303 895167485 751073693 302546208 879619497 397652133 471466807 881141546 154389586 249666151 81621133 830203635 912989145 412380271 497210386 489230624 317067567 899286550 647213985 939984483 971174221 978210450 956999032 783393826 616132278 554253414 963970456 295386320 88950827 30871619 737826479 444708823 166093638 985979661 745749250 467800428 653037414 604638976 842635263 877630883 288840201 869443629 845355203 611617897 854360549 882141169 166399315 589150904 21029030 343991724 486349941 557720882 807497522 319360635 599905505 620356517 859345588 152665608 714293136 643266535 72169961 416182281 582501127 297846383 536963574 462801895 295470580 517961928 605453876 634873112 268923122 233152629 617128080 410861825 970967650 232993401 207865066 203601997 758492633 868597681 143226222 95503331 575234105 403209473 460614621 580563833 958598513 503627253 920230335 538776346 864057990 439108399 999249451 769645201 461277041 505048772 569876026 423927069 851338226 695284566 419668749 356475312 402530562 271126019 840518627 633840884 792747939 354537752 338492104 928110165 402580303 802064573 99451101 592886763 835995203 418426158 146039208 588235974 689585362 135527083 656567176 943006892 288428091 796093461 386815589 665744253 563255431 222055 236831182 741246400 31805699 658937173 448381804 537730000 950752183 771231356 432974742 950472847 549199285 248269231 805543747 311562319 975108659 571097259 449558523 662972127 746165625 18937747 848786473 890298411 805126843 656147548 471696959 726806914 902747591 864830563 827539773 933792566 919485607 258544154 145064500 462177540 154544420 180743518 473646736 763999313 797003938 484604949 352106624 104122428 529558856 143892239 235040722 195942609 18270899 545167707 444315170 95231286 506160454 351102654 531475158 735413836 870615486 16838911 4350955 271754485 955134193 401990128 903225833 765750154 93758013 293831283 243015875 306399063 421956291 312453267 572389909 663096407 328667973 776331031 539176959 867947663 486319605 469180683 889583780 937951682 504922363 369343205 857736655 551652921 378242307 577570684 579232933 333440026 638546387 551500511 543913826 307884516 722801581 76040635 766060465 156076471 590481617 725631957 941775356 707230438 358013059 221926267 795190373 754624355 420357352 201972172 969133921 8282824 573484501 238136032 657576593 572034758 889582836 550319954 450866461 73584357 416758075 953957664 575113362 513956622 229692374 584305956 742452821 548975292 555508463 603522960 432863359 172991036 758120548 175941720 205122072 465150328 417530313 26277412 701908522 545710259 489264536 722414915 280843690 833591471 912927673 250948967 682649808 330191304 381524028 671171591 692959264 473385556 29759474 573692924 509645612 934670100 9084949 108445655 277169543 931323564 795731026 672035592 97630503 155995802 497236726 641485085 619724319 997899239 600438139 918259387 993456826 438684024 320806087 445200368 132871905 4344609 458254495 897758405 786792878 353195185 370481832 231693297 822478150 876816895