1000
163590991 591676119 34299360 677706643 549707280 548157828 659872377 93834922 417307998 36599675 545580951 947395265 380486243 718550136 89754838 48656110 748628652 99683884 454082196 670978688 681524642 817920577 485063478 171041045 790551964 450987326 632854073 704173974 352331904 528181026 55154133 321869219 799420447 372857045 287234897 800537160 344246376 608306834 966358023 511846825 273716109 281055311 762958396 889974160 373155818 514014385 33661287 228403861 779557329 206545971 769199884 376645427 332229280 612551550 33533694 426492644 213535273 819602062 122120870 588436217 139225041 312169058 197208623 80159318 370098137 785560474 842761811 316417824 116811948 59437953 730241672 886721489 92503426 928673121 174203958 979996366 443903141 602981604 20901892 367201543 64956430 227484789 406703960 253509787 25468194 172476572 515907058 90307402 821519135 456287374 73930147 747319880 102014352 78815755 74296219 542715181 124318848 666980643 658181928 938960599 11958201 990222826 420187614 442623954 276539933 806769000 347402723 527732477 563526456 174368755 28219104 161133574 40770355 612160900 868853254 283904140 65666772 656531100 840590242 836621556 862439316 427676999 989988695 32649893 436399025 354997898 443230499 258215764 814202246 648558103 747759055 555536362 751670772 304996571 693133526 891138748 493510724 385527688 80453980 956595644 603729497 313257975 60912280 907670810 472737015 734638448 57395723 227587105 572118034 476456773 635907795 78812929 624043779 76972545 717896087 553589772 830050680 765351630 138581708 756419315 169546132 824462129 769254766 485428761 203908653 456333360 85214025 600394996 116295370 7337397 757550389 855819751 932245624 897024320 988800812 727199283 51366207 600232327 426880687 377334538 280031627 369351236 182503400 361895559 647698476 917262735 538638201 435403368 921164319 116703438 568835104 36383936 876050233 148993005 212780313 416573311 998468961 114017488 245210832 108391054 134902764 512170749 885414663 964241513 384012924 472431314 470188893 428262265 867464765 505381390 158893092 369931689 183146417 779605883 961666157 8952716 23739773 51805996 798815824 503368251 553464358 711206380 462360665 150714998 44827065 366406280 994424746 479250457 858838083 144600395 691615102 695543921 309578920 983847830 998115177 771086673 33877186 92546456 40061310 17192240 832149677 845788247 823715754 899131873 898494525 340774737 972763815 440429590 410731544 581357470 279104507 830563473 581824270 175395462 508688277 441259432 986588554 530618955 253509559 458985922 513168448 924556458 455966312 761395283 822963699 483073626 227740722 524346431 641600769 335073728 986963969 576664330 792979830 962475182 731032961 590866982 950465087 306066222 506740529 492090207 812611887 530232987 988586594 557378144 61156494 209344250 310373709 225828443 821753692 29382238 871105153 848551846 406650177 623723676 831544869 792281878 999138900 888194896 62185257 287900174 733856942 834910571 830305310 504384 157179507 627036947 921057102 588290626 660317493 390397454 246886876 702742271 227810605 463614181 485129415 22126024 924506003 103660260 770401434 415383590 372362858 346660667 582341979 254719086 202029248 987105370 509373953 223770485 955248955 728512451 222487538 77387421 651781944 919802741 763779167 266186975 964605035 644855922 493441707 691441611 204361640 659807080 364317577 913572660 973616335 510533358 85320291 274786837 823471605 446527056 546871623 141245219 411181106 248131295 751570301 850929095 178322357 92636767 779736512 820814455 107458402 333302290 499633984 649025532 626913429 854820936 146591297 961587322 331888226 695351103 864608400 655567133 22949525 822607527 223183670 562317604 267627232 842241950 876374977 904920902 127553839 787786582 576042113 841544440 481528398 729014224 14848180 647545499 713793217 815973138 679721170 994812393 809847412 104003227 242253351 321398345 278364939 820508554 370749981 536859160 798015959 872767806 838408411 801416538 284911872 13344769 60668088 358702011 822445052 976472939 850446469 60751931 829731152 896871843 452427283 6250215 312518360 494462114 811337575 982287607 624979299 61906482 691934086 758789863 910413754 440244562 146356182 434070324 765501637 715701619 692934375 970838404 466105554 66834783 201673814 915346162 395362373 211877228 181055420 841305034 635709581 510907149 591427415 431577740 941493592 494614778 760566867 701079097 703733831 228403575 716972017 836751648 311399251 810041140 269788424 458750913 878821236 538731435 93692712 954674825 93636973 455390786 968209303 539352066 336931082 459586692 189225054 563581397 72590432 506854011 744215145 759541866 937657585 874889349 229159850 119601626 502359271 378020767 649150793 221254985 730837436 207708521 7542598 465503346 359445334 714611054 418854398 64033966 143711441 635136036 582132164 660545701 308546053 136318714 37754903 485524352 650032261 974241753 55462334 884899103 502838980 800011046 280200602 611753990 73016860 173288689 903624430 222236122 730765350 551776692 602161017 129950778 525082262 893198813 729615465 884192113 555500068 631555746 610357708 431407374 403060288 201601502 810345983 424112112 354099325 126130163 70233666 598000479 329922204 889688646 91098674 947410225 952644520 418544402 968265073 57626501 915344045 115595898 799432423 89559440 371800135 37927649 597451392 570130470 754709820 692439106 685950822 544042474 80006013 155663478 501174979 540941869 554528177 803287713 234242326 549624882 573990212 287610514 829813537 143441965 902878086 385828872 509972139 733061445 788119599 966694548 756435074 131344857 876234374 137461146 296218991 349794207 333958558 702023789 609532419 604648999 751111966 166307176 359606344 887365995 802823766 695004485 217704450 258217475 567795799 999957543 493761280 37817205 400000063 267920105 691022574 615024952 220405876 320690419 608756352 235641708 229188003 295775587 779799448 497757176 646498235 962149417 706989974 671130711 746735089 326685698 709344989 493450264 168597458 895892843 761250392 506865826 21105370 699018122 432126016 61653493 551162709 11300746 249981868 105856808 994790565 386752617 877953454 14918628 328849912 10472999 687296052 286629620 272825798 520241966 336060790 860641267 592785404 543116957 645369882 910811657 46157380 924651655 320501455 536687505 92484058 346348276 918149865 764770844 227686609 844308516 747813723 832415554 462733630 868171896 231696929 62927464 378137674 559662583 903341977 605234830 598794114 184460109 187551460 797173910 861635958 225956817 845410058 514425923 885716439 544796272 110006778 516911142 86004324 557084557 696739298 641503306 139323356 171880216 623695184 312929028 88107096 385064837 226374531 123885757 59647397 395466611 453282633 72395052 654456320 920482046 298910147 763756250 179902232 368567510 983423616 942870580 701517351 45276527 549496367 542208208 897825880 58377770 626185836 242150819 999412996 424907997 901952125 545463598 780670586 917729481 79312273 110612983 742484051 786530844 629643485 259403767 438856479 121995764 165187755 646996456 861924642 154392766 268059574 897075683 707634113 996363838 799598014 114601226 479941104 725616721 150773572 446357656 710061881 1833237 965402834 432809534 576165953 998617317 881279136 172243177 896037926 987606906 394508071 519615738 433159483 78806968 224959681 653801402 363542112 75816560 242049761 307997098 611658986 920874975 965335666 891094365 178651044 648866423 375136637 535541497 250796683 964018158 409284710 698443602 996822327 67916609 635702202 234923078 792960468 694645561 741836402 756244228 954176431 412544669 41144658 408969156 78851388 647017442 245647684 706381389 927541952 747193988 421455172 154583052 27937803 363317864 896840343 103715791 29989277 552277589 331906540 831507851 39447201 92564441 950499254 55734077 614026519 280350554 256597749 821845012 139230019 846816180 330691438 335840007 763513361 646488010 15452004 866071439 895284862 25467634 818328526 555624871 521896644 150190818 783140424 293692131 957509792 797798279 438689852 620926750 635498134 509043460 108218914 131511028 319914540 225530572 614132033 631763534 748389038 151028095 406370864 238544126 119730253 385449589 428424782 544741219 858526612 587113020 327622665 546756535 979154203 536588475 850747556 857832268 686735543 36005284 857160188 560837209 580929691 274026596 753251972 52774605 180540805 371384897 907170224 773735706 892949951 210802066 86805119 572900653 547331266 104830743 566213331 383678286 7167129 249186581 791909043 168882152 679643319 282394488 472213476 285997604 402828189 92862480 72371299 189583026 719697472 443685617 832155927 785346931 164699509 338305324 139737063 756082052 145868300 143264652 382635945 814908669 846832794 633541427 486653888 291008034 358073037 20816785 356572259 539076178 489678775 316935801 699091343 486026226 591000915 444983758 51335887 49640391 194561319 411184318 648285412 208083653 345377301 410426781 350370625 716311533 104514250 914751941 173766664 870199213 230156006 991712202 979894283 56884102 282598523 822611804 207392975 443557948 539785050 187321172 438503307 444087593 251004889 461836844 891761440 995797781 411048897 334299827 298261293 421270092 838714107 449799245 141497513 423064199 239164398 528405714 299824971 453562292 661183811 798800810 79455390 227464203 867258980 686892798 440728830 377623004 823080927 568631258 764201787 322436434 347357654 842747462 501606526 419801360 777476404 687377251 329393177 574854293 274001199 74628626 878026280 911953462 310099622 382857006 989191599 905028353 196033389 707440925 854391336 554316212 245783240 596267871 257826470 872906907 727831046 10453108 999495306 723699567 379841918 379934639 924216021 411542236 327065951 323126115 83012582 226507478 416031336 180294336 59183346 915624159 613456544 803801548 677099715 158839719 708922500 218555048 110110700 80481208