1000 627
470703404 361690018 443201745 387749497 389769360 807446040 174581028 29226777 45399068 173143830 473329952 629537106 796456915 743421800 590597566 852355224 191375363 771011037 731257270 981483293 909955706 919856601 846794897 420941614 198128080 788508876 422205615 296019970 229966721 928742446 442375095 997163355 980513328 734578848 478664822 334547671 995122128 962995686 102474029 40949744 174052051 410001576 127664067 510034875 407975121 514626847 737749134 224875882 840324581 402237296 517244661 711147990 855963079 777582569 955757589 718320138 4507602 16754908 166062962 675549004 181020517 241177909 991504031 645712327 899093434 380079209 105132865 573500690 991501180 224738232 178668088 677382650 323520172 902626348 890599077 334590345 21868376 63661507 320899643 939413093 461481010 549045123 73080526 831778860 683912191 946201321 100654985 874870001 963735447 520377583 895813508 977310680 49965867 437749780 39376816 249728603 875305193 868228794 87388780 882021148 160090987 59383508 633300670 736783752 209545643 335132996 339008353 860097569 740629895 242931931 245500575 580302547 116524074 130247383 802061603 883330088 35283203 136012386 272783918 647913046 324509982 225573339 277349964 756639293 894278311 184194097 117660587 758285035 52764854 505990236 116049187 708686115 104411406 520607828 28052363 556542271 265470537 604432212 773699771 228343851 33238876 575748093 834028972 263839417 466091041 299459885 913955139 499023380 473073107 228255596 594997877 618980289 878071532 299567963 88089905 186041410 908691920 898719935 470275062 435822450 480905520 942927563 620224214 414720069 874738568 10588021 719215214 199217989 700559164 835350353 119962007 360186283 563244330 846376924 554399901 388208959 510819871 296723740 32646442 800726754 766897860 72288688 323702653 875951632 436722148 419866469 881373429 328710124 931304687 219920642 11517451 594407366 839345560 947945983 761147001 352418953 958282569 230668651 956643248 247651988 964134503 91031788 804423871 236714867 971175807 644199972 145915872 713449079 567301889 416603796 799258813 943643285 189375310 166963499 345025527 715709366 134262490 405145309 621350460 239376054 207525421 194648610 762535987 167613086 684172055 977855320 743385414 389424645 589702094 608138195 5992248 432369578 113654758 810963889 258441041 758586954 758612742 46738712 682153097 641370675 161993194 968821302 518125236 850424914 19310197 295674296 426062947 610935281 769371587 450364766 140066424 584575199 550046052 561768274 758696511 733228103 693744766 320819073 179679423 432321757 941639528 579102569 799071323 8088642 184187654 271660163 781702326 486147596 257744526 180507643 905145707 719072962 849578625 105224797 637230938 722851646 654012589 822215202 73210111 685592778 335799404 917263864 887854212 711677642 311880884 221188208 298890419 822009306 459865097 243280023 186833374 831538392 874992007 588852001 783685554 512653251 130479895 578983336 321539410 393595725 147942711 270470375 386780600 460393680 653374296 138056697 260534510 619638180 763857830 546859132 965198594 673078413 611198497 638266638 331985937 923960408 732896391 517146897 264014163 12476047 885369955 880331709 762420106 120975901 420119769 729194470 731852718 197424001 393061 123299685 782957434 954745662 740859719 35710742 378111434 30199496 68595887 448338378 430239736 585702621 1461062 176610081 134783217 724677931 256294693 939202162 37622660 498480396 607142989 121761716 898568814 843480955 407157155 942909282 698254242 832822421 118035902 564690397 935604576 839746045 863301657 376883654 867771415 499675993 954134816 81302407 969140661 324155204 910722548 915651301 958489902 853452373 276364264 594156501 689996350 905365549 834970627 426927712 955161209 937610723 211252485 945870796 850461726 569967835 372202335 50203186 606911392 884661938 347856331 911388327 798391494 943053611 27211186 472019675 405018054 291293181 361334999 87512971 643702531 879334823 188064063 723020274 661392739 801805619 304803709 769066340 11244626 817365455 988563835 110989665 784950024 338278082 985061883 814170447 948884647 734276113 478079917 766756362 298366837 759610713 894274560 66920039 19902061 826073574 207184804 85912647 548288347 822405346 195558844 317088288 378204025 212124112 594089764 195905925 887432616 77226354 831269702 498263007 788208611 784602431 608032370 650441177 775970257 992043480 163086187 771026751 835859165 728289349 307218187 411321182 167447325 120809154 390348774 379758309 94203903 859649959 869723025 335846704 340851171 122516404 157732695 531355003 913332868 607447558 100822044 118313548 801578225 766310585 793015680 507902900 870561903 587137671 260879260 38402722 977886783 215790149 446049033 440468850 538848605 104088634 239431868 729878677 870943185 216778086 373526929 361279777 942992446 33394412 89593841 253101529 619332244 849054159 317398665 533516842 652635492 732130071 976484036 207587658 223997928 196178014 966565231 583826689 67537064 192001786 952964787 197722978 691990829 99220836 10169246 759558892 740595651 88180678 219417100 888976875 737883593 870553543 340446267 161261863 958428657 967394139 599143519 340927769 727799602 888996869 196999382 72274532 665193284 143771072 638870188 441395865 914822810 47672027 106463405 269513654 454571115 598836516 562288745 131628917 576867027 124468042 856209489 401186585 259889230 103120341 400527757 652841132 172829328 790425610 596299092 473839176 871647777 65304332 477416087 612307194 89589187 239834475 185897662 380034786 241348888 192779596 359095997 640476867 893089641 818925965 345120092 858543056 43168550 771808673 319887662 546607486 750992250 555824844 188579063 203003231 504501471 15195028 597975614 559249919 851007180 697654311 879747795 396022519 296906045 642924340 912432568 324995211 764689322 352909685 339323995 379267978 872271338 846366474 32577 203551353 148820485 967873848 448483672 260275196 92767052 490675655 116150992 256698766 437903329 477431061 741460318 399266485 148946652 374779252 874335272 299513921 650511225 21972870 907145291 807578017 979063089 451000753 278844616 259760650 607269847 188234371 749568350 157908104 793771493 949027332 901926322 596694809 14272931 262422580 354202685 261249836 475469645 993474377 470731301 644683701 336103132 163249279 966244630 796834964 56485971 436910032 784290489 668905371 275376762 587779605 382978460 142655779 140663361 123248783 632259378 755309410 257637780 239655786 272278288 712799947 576954039 23055916 293320842 975881370 986785013 500490212 983518227 428711885 689881891 794981672 157151763 410156308 535488769 687159340 53656147 24047354 436395096 917658060 68776862 548156133 396224396 728629426 850236373 941747979 39185332 420310883 735341784 104312366 678643641 33740126 960648560 473213569 276925116 575300167 409798758 351869049 362316390 488006412 167641910 126759775 616798457 161891175 861777097 903527979 929669942 177033492 711288804 537273883 512124470 328174410 741046402 949128008 871044172 97553965 171892986 230217529 739730854 299227568 992137348 361241180 381593475 96454882 984226809 154672235 216429453 865584563 272720103 480789910 278433756 159937534 603672090 917178539 833240135 723587844 996026573 254010976 806046957 876532750 371450978 737951960 160373238 994686387 890219804 78839951 676597191 619490694 142374245 260299166 332418864 152571777 616961337 289963676 457142537 726811774 339508957 628716678 484899057 313716081 764271327 104641814 833731388 123817007 527737120 610208915 140137651 475081580 833607351 370879350 460478721 96748667 899097504 493352484 873011818 264710000 150382445 873605752 355210581 694001407 306770473 417432978 953440887 919513678 565812066 559049842 982292395 829144436 364719068 593374625 884796336 943249375 911489318 88826175 931278899 778001079 361660895 41450469 307713367 107285367 72727757 808128175 622346739 726153540 70932318 594787744 561632454 916436666 324069178 395403942 56153040 5456304 944537653 71654117 843580859 724018562 768533288 259370510 831620383 585158151 412771356 439621809 239901536 232137629 170840186 743469157 699209215 30454028 784607184 686603171 125582708 749166494 956945071 83514711 599673115 279503492 743322643 923959222 203655079 463503583 721808794 583256884 7272293 773834554 595517072 855311940 807981219 102996306 49496789 532711169 370190332 206437496 147367578 693770410 691990693 944241750 676692335 46843553 387826421 645687681 394224503 641712390 431930412 414708914 957372816 627144707 286540892 389872270 758820394 986997996 807230152 479871554 460236302 824899190 666400352 929706940 713618336 741205155 568598228 675077845 304590599 703872991 532894449 129275172 181445745 272187167 575387926 457455926 844278249 423898938 144159301 162751736 414152510 322823514 283968402 714891233 268094753 53999755 336533190 633006016 204082588 365539454 486862349 935449888 88583098 289798157 880154472 968943891 605459407 852729183 904273915 210806504 153684271 897072255 774365803 310675388 888672049 442311900 320461814 433864381 828394536 163215008 916399126 510880188 700825651 52085833 331232650 969200146 594651464 421654609 567206237 833787595 588034014 307546051 509698853 287126988 520425214 604002815 170587886 772090605 676374956 328423039 352815403 736388433 603199579 105783322 298653454 73536778 704807540 89722609 597336081 282358260 724478644 521486616 748713663 299887114 726466001 300529839 872479275 502849266 961982419 41772618 467932889 831788409 272002408 568750254 502350420 118051750 85126896 977575651 339771348 288092323 314373676 232549598 593822968 867468023 328129721 748730225 676621777 493294709 489665436 878079409 895769144 463289636 123260492 26441680 10171666 721822564 471981954 263670810 261244134 323303692 424212925 929784352 983350930 621911643 932106940 763810989 363663480 533580824 688187952 590484837 334108050 766725610 411690887 946285078 58350385 709877001