1000 646
610242489 784982664 782607440 906800829 422465797 63033439 915660848 770660955 125535647 762997217 487889297 582247877 642425811 234248743 569604113 686015936 889494315 372363562 684033455 297627534 825033130 366661291 662125913 387084032 344243469 712755828 272583797 853749403 349961343 333539102 408178148 135918519 826807472 587239808 710936049 487701804 826842365 569290807 925136396 177443008 814797162 434940058 962277569 798904402 949861443 331813847 320961787 457731645 392307061 175103155 575205792 861196215 690546195 547119340 464705674 323318593 787769033 197267233 632006815 501402229 595870282 26844664 145395119 533334058 171314426 666189010 313287231 96062534 962475007 301060451 76210344 759839173 960251240 435454708 477107234 613027930 435961249 899842852 846879866 222132925 831476145 472233346 133984009 253754625 811744401 70947673 510703357 996946197 323127097 524268921 108379227 899587216 592227737 513280014 780331507 794894128 885674522 235579293 971619106 460053545 123188519 419342770 396784006 35302061 48676458 823875231 635743987 40956738 887669612 221113776 687263070 643556952 388709140 84581060 759923854 403824292 996612943 934619363 1122040 575030522 828055813 519819460 326271621 127062610 747066473 322024808 237040861 699801686 201820411 177628216 809598136 500450818 767388172 489320490 811220495 191425514 757340136 460874202 95862048 622878 882878420 77112782 377617549 476231650 219664512 870245245 567566966 20011125 345864755 790449626 709869776 289984918 694618608 926318114 850107449 929034546 993558559 226671464 799563933 78362408 141548974 446384518 762642794 214684860 566899540 46414424 563181241 612898486 337245648 333661010 160732983 502178396 173051941 371225838 57599505 865884595 805349820 749884915 743948427 753225834 856728607 246111534 704143136 102004474 167786006 120736415 735959017 539091850 557851930 811187524 108672948 889061086 905122353 326047991 902317101 454716967 627864210 43024224 419641223 95909946 237924105 569414526 97600523 810793763 805999500 513775203 966753076 647067761 14040632 743262908 479361287 830288610 106035789 498102969 418539046 283162470 580612797 132813603 429100657 704192486 17223480 767131064 987844766 324963346 925804261 402500525 772373107 688763345 400680899 897430799 689490177 628897751 709768376 894614960 340254638 883010231 39686514 735849428 622314518 586044392 948083747 244511732 747787293 73019865 227987390 314613977 555810296 858462641 390214732 642942931 546500529 440102324 724059490 745588328 486717151 670319865 912316258 796507996 692114682 927011783 352318845 430355444 612333827 868273155 455376726 3591439 792030840 709151652 7449577 384078591 585565510 581875678 23491399 490989237 979334394 592402550 507532542 609221658 278799510 279621430 110699517 277665783 341695219 127533394 634079225 573150355 972888328 59269529 94400334 958964103 210237003 311604247 276943341 179524647 766004125 424433814 78973407 695815196 894397345 62830067 218987000 199630959 718027596 680164847 760551762 859820968 893083711 362159303 207538924 177507066 723267676 409935553 353075980 180206545 388287094 971431239 508312056 382312626 131173727 551123588 358724529 209603651 940489349 907990833 180628732 512644612 315163950 589297861 807278340 887693072 249978698 166302584 164790423 159282899 190514491 71884455 985676413 934357050 413307608 390590916 395967333 295835381 757018018 256534019 62739673 866511269 169537849 980583428 719880102 665637431 319651262 800835783 701678306 633215599 22860346 430292928 590359620 731755259 544245750 868626167 144856378 582942430 118735863 729490352 928154198 729975799 505016942 64052160 49900531 665337628 148557841 679841438 672552818 541389148 476764445 302334379 597662790 290392523 458275082 601703979 925514968 842305920 825248732 265549501 980144500 763834954 939232938 499549331 728697901 357625564 52530419 760373267 999101781 503662379 473318692 951228141 60997037 537857140 991423311 221903259 570376720 143247688 459004026 76227120 19789432 444826905 428401169 636995606 183270749 296451749 718948992 274809692 7866903 783111805 533035677 980531995 43716217 505715348 714829994 956252472 953019500 64581079 43320547 561540201 103084160 904599177 515592975 508620889 982462104 500167793 411456728 579733166 615572955 378520795 761653329 519188963 927920089 140186315 177016652 727779708 911426022 16413869 626424251 216466932 805606912 947723502 295555223 453910224 500100961 572070313 208959185 744532084 854604136 145401692 204579087 993005104 548326778 422209191 417913218 20030 49589508 795071103 412147652 79239597 784397421 471007038 528932521 234260320 304796890 165694102 445413319 218102084 774265597 670131453 668153762 592863999 110903248 64942872 531246577 733008651 198695240 542006085 978407312 87714520 738625371 410546907 81000793 666497378 248229262 191069402 78125672 679140666 370096360 266037213 822684556 764258547 66755553 30182316 165357202 610461833 267445240 971438242 624080303 175849997 974683445 890759812 822732066 607048631 200926517 594082133 710062804 649186662 556387751 992417398 491627871 88276903 908385813 163567710 588129752 612695309 137209676 810331166 164967797 41670397 921973412 888118567 80205201 156240269 137914111 559361834 653113680 766692244 224337407 663567672 826099098 762681026 416006482 293175721 482399808 860035888 128638163 257502444 28163608 713373736 759236234 106766327 73989701 933362977 640159021 281334897 537531458 127980531 518490547 125620384 299685021 790357489 756028631 782714302 400613553 672864660 151254570 977918254 56043139 971476228 342547995 725547131 608054974 840877936 220322092 776373141 742204797 77241776 108725810 631381636 471964755 413939802 536704255 489163885 821012096 221466017 117947684 29462384 1674992 899001728 533709706 922792616 150725072 741192000 571693367 743609858 32902803 833856070 490675018 311838600 390740006 820082874 156247382 676665016 467847237 787590853 477169406 853604268 67881430 890268566 676907794 21102025 913699977 461816606 613442728 948894735 627191298 576903658 748403054 715976166 936070610 334801049 982477015 92762993 492684876 576682470 945007837 427587475 359242646 25091725 727644807 95788277 936795684 462957575 16232777 499229035 920543246 496681275 885050116 295106911 205485801 564249802 409713603 488699238 122919646 248401894 747186807 630717552 777413556 763672572 880941925 60208089 441451963 182499151 630061491 710834486 843647524 402077267 93378317 585510988 119158170 526273347 817784653 169889109 441969472 607179810 802869390 114922662 150376 807006621 115028084 501153130 368343269 67551439 397657194 986791707 833757880 450454538 509782495 699885991 917964538 145088321 424697707 144787750 66963853 156287103 457962050 152615266 411008783 138252418 549457246 985476732 639829156 352126384 58904476 191804203 617529432 424546446 132273668 502684257 431813182 460617853 892330173 456179235 133836524 721030217 208759506 675451883 423018764 327372818 60393876 184210908 286276610 699391701 77469133 326928832 477043620 977415186 573378721 729926392 749282355 385992843 923239380 999838477 437620896 134114140 627809956 323152851 60068290 528319572 475313830 124093554 870007363 599722045 592278688 723044931 375101414 422212512 89246269 638424229 498585873 874136320 918703312 959081613 73894229 416744778 530871415 721629035 426323281 769788202 759463856 707359092 151150475 534609737 171195281 171801352 716004353 269101581 679957512 594801219 517682798 370446665 4558068 921975855 855664776 166395689 987397676 292802010 667444209 85888180 933227944 566494633 757814604 256354323 684161919 916563714 351263495 353827297 79659669 262946204 32170889 882434258 450561535 358950248 459535746 173774873 386185244 935020943 29923020 6247147 199345233 781917685 136514494 990013228 12738605 164593393 619133565 305162240 98945967 569841811 148389536 316061516 99113160 543177417 764665407 903701392 883378407 279783834 118794027 777220400 615664930 569164029 619688645 944001538 281326490 392423974 588513223 961653997 433281746 963097224 107645247 799493344 958247070 96881714 678635447 237209255 953959511 60284552 151023309 193298812 794153679 380543089 420625814 606431151 929686146 385500144 686990960 412410981 147165443 400023938 32474582 68018942 125622238 875143373 712689776 659458733 10541815 335893965 478264497 599906943 553053322 526474459 812267587 379387009 446594856 138471250 5486694 772709494 218782182 74837221 47554298 194193332 980952411 64678874 638422339 283625657 1920030 755941185 38529191 947636826 225522030 895104632 778855522 536122617 399019183 500799513 505362508 986956680 872508778 504349568 891242923 752376340 427838210 949392154 760159483 6447713 234175810 71802158 175186400 524518471 976294293 4261701 638201012 652635891 657287463 885432179 877837878 921175495 27034406 13052548 285888383 881236843 719170017 680724934 454623188 742289446 942868958 552996303 450574498 204109642 127032219 688455498 907300268 336691616 5116769 588026355 758763494 348365062 8337660 543079257 463215049 122677908 205546705 63741114 951662858 54132856 396740496 980074790 30952826 732484367 776794371 915907219 316583951 314074822 639458343 557797073 405228054 529821091 438514098 84080955 263796446 189945027 788332611 610992170 463720492 613344374 39617496 352901669 944767166 989780170 496920782 573838209 485971944 658858963 346450653 831902760 635147835 423630411 401542608 251726880 749479348 445261073 876582577 442266277 489731466 531038844 652552327 467319659 295536989 717802646 625402797 635993362 635239395 137703049 511974928 220906854 159846060 730229315 725309871 433387289 319664110 518037594 388214793 143623845 851543852 141143160 681125054 243910223 82670893 983832728 565379086 716835082 86920120 273404037 645456489 644713036 394652309 688156314 812998956 894251081 780178817 441561875 999708384 261734113 299170274 294008807