1000 913
378965485 163319302 93066914 372946735 36507990 260235071 947850746 570125396 762415188 840574998 434893846 356282726 168816723 516892959 980403891 49272959 434163271 24194374 544553910 367602548 75423798 752606134 279543358 214682156 262333935 369331061 139023973 145794347 894184398 73327359 193819163 639740243 30802589 715177876 985859803 90944190 939573569 939082905 722946467 182383057 841440962 509017617 156239868 459909135 79977499 141711477 864217507 724489239 358484701 667088640 322776273 957157572 688695096 111435532 757040601 626433539 613685740 891849573 95287872 824481208 365272620 885510973 13157738 19095446 97459441 68293242 728370402 813844205 272604548 862994025 159620385 999627911 980455594 979620904 820354873 111649202 682146607 428942287 325595408 371387134 167783059 281161249 816102860 820435538 926539394 631870084 863694055 986652864 252621974 704682412 89184667 651310409 504197752 891816047 773121540 152483306 981643085 813791761 915871831 208188690 31997991 218321059 22070485 437154783 631724013 403650056 127802177 679796687 607379402 3564162 9403612 829787698 741701453 218667378 387151986 312624840 757880703 814616077 692721212 764701200 477639935 440950107 508632715 502157086 90205054 227899588 648360188 159127929 640755080 395325687 815832083 802704925 49169086 370235175 187773587 680183304 662958433 433043155 551732624 299018251 414871119 454378600 26965107 786180237 834019511 112142170 290127890 810671518 364788932 600879958 455530900 879423554 544926989 97224084 240941033 487461829 498711226 948276854 925380762 216468373 201704317 506126887 550564216 90707835 973110133 811158139 479766810 819201966 905120596 141199593 37980286 622900150 523917439 282064560 2874513 504590654 270987652 597145807 916632861 303816664 415447028 417987437 463038463 768860263 403073787 480827553 739469141 193157550 398174095 330553370 510995853 275299348 63427218 160144299 713295643 785529563 534321358 412764367 973568213 607577353 871127043 828420047 345445565 394528318 372457626 354003315 660278270 585183439 458446547 483214808 554611384 115228386 970966122 520091852 90657668 980891116 594785638 37157735 677589925 311392040 219370738 390360015 586094733 596508731 774949656 705208705 285507888 595899111 977010939 773733233 130265617 352197412 473927107 894139241 728871098 740816364 440190795 842245964 514490793 999481362 474815724 171112255 53613070 931366800 321482379 292953862 82913431 783869131 760315127 754212970 477589651 858256582 407161622 754896516 760928929 981061855 657119231 397590993 413273538 963570514 133897948 174509348 482597101 453222401 192436961 108240927 419484423 844980146 880751771 975288375 275887687 87063868 433708322 645828079 31480624 251005009 894030031 553620314 79532988 514275966 634463361 552951125 971425828 187589868 913114125 450929473 30958354 688431714 270207112 422838992 107706045 639799087 405510307 520422407 452742402 646374711 167200262 450957074 774538065 985556148 348937989 720736512 399165580 726286365 297222768 104492697 286549744 700115210 419990073 60158820 410248073 915951972 515170393 444796147 708899197 952644794 111771256 835228248 93021911 760828912 155430409 461219145 96177299 513332307 162630603 942392753 31235049 454501082 827031233 202846304 801096633 321531321 23823822 570065330 325000043 663560104 626493731 519618649 153222179 17301421 171654068 511834167 67333980 433018724 157489737 262815225 647124666 883738520 629747051 812293904 267037513 310152675 258061658 45252732 415623154 831134609 478767583 702512978 917589979 602088760 677491468 760796936 319975465 753359075 765552172 660230355 442656773 708721954 589401623 679413071 656298085 435127962 325130197 485003659 500628768 687790692 101063478 732349109 847044481 844259212 952416674 443268554 901838620 84872572 44753632 839023893 852873652 998355178 842074079 478550854 130669033 534810315 720957731 879550431 53849428 953776916 811860751 253759128 802027149 127342650 967648526 193935531 433946770 304463882 496900645 861967719 431107708 738824376 510374313 591187281 815365926 724963337 868373198 806931957 15364313 510213854 668236803 66994031 624194610 848180947 611870595 444068492 749591297 601086746 733001158 237198249 107406892 740319677 710295058 848318429 829111748 21811588 12263524 835103842 319727032 676597501 200159146 637512136 18795103 614274944 868685685 344404799 537618717 454953312 736935715 833711657 217602269 271179196 124657681 688890617 155878110 372985779 845914040 899564462 258456841 133643616 617665215 10931056 354460976 201047545 440395565 948016132 855173827 531017885 734281475 680839117 335665452 3929882 897200487 680479369 315795454 670375857 750248840 185989484 789832488 191173497 360744120 742552034 524492893 277173878 459431939 264191531 624524654 79487677 729858005 827091315 912140713 632558563 583855866 20310245 902359440 59207587 992913927 338576881 545734178 306134096 252120023 874761770 642513400 569460475 729190875 93619156 648275574 94340606 55708889 641506241 188644429 375476318 238583617 940742305 245021893 159677011 939107283 850567407 668014856 182084022 232193503 311004421 165563086 709769027 48324359 9107773 283011902 575863120 336706758 179591842 280695485 839152899 719819271 628320642 566988790 636183954 103302683 450857341 649361058 501994233 310542066 970625611 741360052 711255900 488969264 602628237 140896103 813396813 182943471 729006562 551475075 113475805 284483542 988309162 382070616 116575059 785567194 764192928 555985051 856833877 877260288 519706623 688038401 41695707 153814406 738733450 99551463 205109494 643321323 104673442 535564970 360596147 734296860 808950351 554549906 734620248 987632223 951392887 981641878 302261720 272159275 896384548 791869568 527228942 766115510 302309350 840461432 958038099 420338821 91531425 927801398 626316869 376776264 14612772 713324363 616121785 602378011 732963067 363947277 881206794 227883268 83237177 685353533 84805612 902331831 239377105 398498292 51912154 96468636 643858352 280607642 864984415 400653526 120795961 407057653 193954077 637675066 900144844 115150218 787421602 112606480 923003325 173543283 137944281 165733300 667505859 175759384 334436535 5225104 686489353 274203275 149162438 565691155 196776802 992191833 203808649 411067856 527308771 846055639 380093638 209471474 670784028 939769724 595953725 17020247 42804257 27133211 852259809 362068800 858974538 875315358 813643160 566924469 839246050 35134578 28836204 840350405 772609022 162181183 384866144 375997972 110615791 85400441 998752841 931209218 658240933 6237428 813986177 878456574 167102383 168361989 248983848 202257710 406704872 220715304 502420424 142346696 439715237 143096822 261972685 871589547 10523157 417083663 39598319 362676641 661776541 245463607 681001279 904910434 530776784 584995261 156346515 345232923 398739664 197677021 912132883 912919288 509061464 204810407 546643406 65328991 927485933 630535711 969933774 277094345 685370477 177892157 461389694 605091121 286382463 456372058 363472337 157070301 377369353 574456435 355430977 667231649 617052105 693776658 250122983 252143846 262428971 518854814 391009913 337513855 266130345 926673853 896943498 481221508 30822885 570553137 653748669 531386632 820167100 998013229 401505469 895938627 169236775 987407477 213529092 240387594 773695723 482365975 364279424 452806919 721612497 701492062 937587663 722585158 525609980 418356033 1694876 526688886 330269051 465651714 645576139 765596001 24990364 494410434 996286767 678034983 671266934 823128319 382584236 678279911 523047362 364171593 970533946 478443038 719196732 466234547 793611750 959269137 352387351 435742680 258571155 913583759 686722068 909640950 542058904 746547039 781899161 202049231 691928803 425148938 198096921 645037646 647085479 256784831 741457959 160408237 454594216 482243562 821540999 599831513 547352450 647344481 932649395 611534182 844788696 291415375 630770274 348198623 441322681 382920152 769002403 204535245 324016447 206932124 256355015 458569198 124377031 128394716 223150621 109969042 464605968 505490020 890694686 47637235 474091203 402473371 204362351 748682946 293623510 974256998 795390534 499876749 747143891 257139786 950822954 627954348 7571826 144941295 195169937 930497972 863497554 755043724 817852433 150658550 177051633 97672574 881323176 926283325 231990951 956053562 76457012 251342835 723150010 171865901 51340435 689613998 858699926 993702048 782373482 257766172 35440618 360860190 988746065 359870475 562330405 465424358 73724583 262399919 976398714 558906530 880350151 831638712 980689513 400360966 901120965 280175025 556432277 934488980 896464467 549746054 235491923 232703216 879530938 347143507 404678632 500942640 312481866 88933434 980928461 33832380 231185697 710704458 844287728 742003602 334963244 470371224 105416972 864316225 33089777 588406142 698396327 757362555 86068304 935982506 495522200 790363616 385250869 310548699 779155949 118971366 445455443 39770637 675224976 390547909 587621940 7453035 200022632 737904989 924902096 451767624 119034966 732229983 467715663 497744154 492888085 14894231 520235927 872126098 675731923 920532327 18462729 601059680 130101443 699166295 457671583 60670628 250544508 695716665 99835601 84000413 585244600 320787866 619823988 298530770 252365574 841430258 775821271 462896694 949472483 62723811 75684057 242199863 899944249 444360727 858865662 947492270 389063819 241322143 400175802 775398668 603377748 174942565 734188063 642335959 230264443 225584160 261273116 771986932 646297502 542520361 623591051 892593452 441321272 106781400 725299801 189283660 169375345 766247875 925500800 335967273 654812342 69476093 218800577 703088417 852109706 135720278 221566393 119193859 803286802 502849014 874397578 411990376 146715337 173996736 178481836 670566806 518438070 415488064 936241438 685160230 574156547 382818997 536793078 825862672 998841162 574073217 782022407 811830037 658076197