1000 669
788598407 301176921 969578669 714010553 266079275 143052443 765202070 224854630 243118128 59268572 285315598 588934860 427682600 76132152 442160045 809036952 700800130 475193466 104740229 831518461 841625539 804730364 136127302 360550340 25576560 739858396 403195723 9101015 775060265 492595953 348423670 118886700 850288132 167954130 663370032 889975912 708899208 896908030 516918439 731105466 589390580 526297772 163795598 561523151 887498896 183777349 425759391 305227340 438894247 67306139 678472190 331390569 888393859 795212806 744044805 543998105 441347779 952098497 462377613 586569662 278355641 974103380 58391982 266747950 939684612 276563587 99622780 299728339 270525840 423863195 947448488 491384999 577775003 192077897 853069807 211701972 695124854 116884191 46403493 2630668 149820854 18210698 117537962 283181246 481283436 758248664 816409629 119891322 718184368 552141988 207139156 98858816 416806381 62313347 698298590 231676515 894386708 221809260 916124223 600923091 504633163 580318731 416201287 17555396 651726395 14741022 662552418 650957010 973282014 776858731 498054766 665095082 537614300 407431606 459180875 525545935 717069953 639917693 335236425 58189693 35662259 638392024 556155833 942699112 281288180 792317309 748003620 468417485 171764273 908880593 845104863 402140613 760909725 952315767 376594751 185959970 172249297 347326165 855179719 357174908 341696279 412018530 104150780 314524031 508106958 548614270 40319714 249240491 160796822 105897713 132406343 984727867 498959902 708645948 328236408 601705227 724675804 497881311 108177252 365576018 305661942 378623173 298697850 139056228 747289351 579623531 879774571 219529918 492714754 811464513 561677157 307439294 796897570 197399374 871209548 219922764 763730004 674910927 258996649 573403737 72968412 501987981 210919350 474126751 619566365 485501447 548886968 549446008 507824749 831454402 73181794 356645437 410869514 938554464 26189235 66436505 653390196 930289352 245870315 432712443 707049708 691716939 532247797 839422710 54173999 6916480 139213780 508249400 911777509 191156955 875784894 67807096 815754140 794421529 571152708 4590773 360189293 582180620 958763947 474557885 909440798 973626779 17027318 938082506 121066121 240255188 543049246 366129582 690525285 382183473 464838561 786702330 182066802 312028313 420280555 443128564 205361756 634116790 804200814 608174382 542222834 971372662 408852535 830307312 141666147 412052125 514438111 973420516 566390345 128470055 653104741 383370522 705555020 738788600 41827761 511023524 377797187 123182814 372037677 136924550 170491669 163539385 322217921 697170623 44137810 334133387 462143237 183968761 513819170 919221198 489202963 668264493 141984090 60741837 105865011 877272806 759164370 967608501 748875541 450780154 296964365 985883798 680027952 978685695 941514991 324610946 839023897 922847146 295418562 976240444 133230427 711121409 51227862 635680446 503728337 357843085 457536310 746974621 751138348 906325313 768353936 562005737 69978750 976734821 971431655 192986624 257914153 698480749 374102332 91682535 576287036 51479704 38282621 208373457 712884198 155919788 192199849 277249872 916999065 504659283 246738388 781543443 413307671 752021004 224325128 405782735 646099073 362076675 377302707 708821496 239175142 625649867 843921344 355041331 702945112 999970950 471648672 599166419 285935397 58613745 872293102 270140671 419383812 832608127 465396733 52686361 191993017 611542630 833920430 253573707 549905076 565293121 656897743 943763158 418817234 30457262 19377382 371510184 300511821 379654711 20672161 719596182 29928541 351804589 985128434 37420672 94746708 894142454 450996884 729272170 838719492 520228745 421550391 284475644 248752303 566573527 414001580 531908057 823888868 835788461 44891420 830930881 488777831 448591612 193505972 627363353 60269330 464255544 785554481 197593850 14482514 483598670 414957948 810724451 545502776 411133496 172883731 814688844 899456657 582028690 408680579 579425627 182103794 954238963 611179572 877481567 639448695 549151455 388671427 790195851 31468364 218265294 661645971 796942823 237766629 976181768 149925594 220733163 820937136 803977396 504241410 249508170 447929759 195020589 754842240 119005002 470689212 436271454 611839852 549270156 406240597 291504617 887522277 321332627 565565640 128775231 902511046 973019559 898829567 690966678 758570737 81176692 548051288 682808186 654219597 645866513 222084851 863223644 919127354 706494122 859735929 23906625 787143283 597349666 25481026 3412751 194527153 319580844 916697419 293035300 809053930 90188389 846159625 45229206 404569504 179802608 256374731 828918531 890697815 248498480 372955327 199704347 298870572 959825526 300862320 115167433 882432392 296604898 176930055 813723385 832957336 633275164 477567738 69635881 261143737 931004264 584231241 278124676 278991488 389921202 514888679 575834026 613675822 580009748 583023830 264134912 816237268 771531663 618766804 337615655 220639499 748499287 294893137 148610265 402177730 418784749 769487343 25262873 904182446 370100299 24532363 17596414 993418148 793558163 491462029 269005210 131744014 781207833 565441687 796571845 458533349 81543574 49321545 517576188 577624292 113716034 931571160 977629632 472630616 736093659 229202677 120522291 670940467 508995891 267625484 991452261 915191046 814614958 477045608 728943927 784554486 877087407 49137553 960629861 732488863 645735351 147976119 496632981 217717874 292282375 861308392 222691327 123925143 221940128 294710725 448578513 369907237 432073166 910010563 899453782 142889639 645014044 616934977 53358786 202907764 55086860 288808949 632081282 445060041 47963060 547226573 915672425 175373638 85900793 595521958 56862737 607244387 728359704 408535278 471617405 200720144 187945729 333927276 350687391 98036594 593626580 744837759 57561587 14617296 796266712 331790836 16716827 924340512 440626936 187519312 647615596 523515540 879585217 149244994 422496813 949768405 421074250 820579470 415066811 312625475 950399365 751945860 592453832 567352245 291361098 221652280 378535460 134387150 352189663 249244753 188749771 628990596 512926390 954774956 533633821 776875299 120379636 903460870 378535674 194078459 596206457 914589378 427403008 84681978 825597635 944186875 983333765 141215659 245723166 361529895 220573125 345555430 290865120 329857016 864580568 736615462 938931902 839471987 434878417 570473373 843733077 546075052 336500178 261307947 886971255 903325080 301722375 564777344 342327066 411312251 856762842 559499273 409699867 104466697 783375348 111434294 955199636 927285298 47943417 218555738 680877622 270281147 228320775 557242241 105752839 486861974 341703814 555732836 424073224 365429139 250069784 405215268 330822439 168798873 287726386 497017119 374499408 422956120 237027356 940083744 509653286 129787235 268505360 615740429 610420823 966526048 260573753 97961776 740520366 721118526 570351293 865516032 867610454 332232975 956792871 569363424 679132559 89630141 16526148 337056649 560546643 248831450 674029066 685368025 546873510 55687771 920813941 483228997 63508185 553845839 405642546 931254633 582663125 921122189 538586695 6593071 513913133 581031038 408803451 399788210 430201799 536256127 588581318 649600064 494885986 274376733 781732556 761150755 281968217 920519515 30951873 888786072 874267381 755342835 863549904 524456588 157602100 485192533 39841590 744998638 402202388 772730114 526047018 12119404 196941365 37827845 441170967 477560100 178891676 866356401 575745804 215006356 459884687 143576771 90247440 933162257 255743671 891112336 732591370 268674272 822336532 840284989 278246715 757010136 487163134 995391048 127671763 163374370 802307157 897393629 147030071 56980352 640413419 673064644 647970823 669157809 245707223 915693949 437017184 227875526 80238086 171632405 411939048 513511399 188631122 952571742 979543272 278866021 552213579 796664960 194544358 319942153 789986336 255121833 574891654 684105708 677518955 771405989 891594444 13063350 693522637 583600862 199664454 530903219 954426203 389007297 858356386 785317733 501700117 355920727 640374794 544028091 733756745 427858221 825341078 448051700 199612988 485617551 493902366 156181039 656499841 803458884 988259720 290592407 184508573 516295801 134368969 273068287 63214716 859283358 94163062 831687030 853629502 950619791 31612242 364264116 805408758 886953640 114579872 858857453 238501401 573804311 592312220 147574444 814231038 704148538 893456418 944787857 881411437 819305092 70312105 76531063 79106015 22523467 457923026 460635915 658518386 913008723 900690689 722362800 57686268 999385585 360399501 627298597 905638488 882229981 774755945 812025037 820487911 538608913 235546954 90450542 683277719 130833043 591033183 815481912 647880108 369373890 359929061 602640972 430566186 291711622 882931724 891529234 332101500 915996372 691223574 955705344 463092180 928636757 391329218 564017022 534728264 601879900 457075806 962247700 54890116 372634593 112624776 630836982 686056148 439718278 774048241 344721769 615462964 929442259 426304166 569644167 715601989 465106113 752321481 54128848 877256595 155488734 388818048 540743456 197733813 994618327 220186842 459436461 654416753 625191604 530730794 851692428 748672433 918397109 71887704 366130076 385476427 163593785 684824898 971302972 741106996 527489692 375820993 885779265 29640525 298506183 142067175 88663407 3324679 878402153 57742770 416563382 703552033 440577570 407350483 983538539 621680119 408842688 376897471 573679602 658416398 737291136 918101082 225198440 500032577 269697927 179701777 738825387 821451331 807144790 224867233 200596461 14394837 308739113 335752511 8721298 723793054 384832711 325423758 901114921 990040178 401340469 505567918 759014923 72529609 57387050 307693759 587894750 307849067 954043910 548318557 984384042 82506156 578403881 949837465 14318950 414875902 839895643 957163003 734715180 940001860 24681186 271549315