1000 699
451251966 21341381 979664390 691665598 189573863 561824947 483773547 252183270 165853654 576869787 10180822 849543799 237875175 210651629 403187338 339648349 431130741 88310821 886505152 778373953 635677266 99343076 434441649 911990468 987997698 510855562 614224337 273252301 322662965 70026445 691310882 817790758 495699922 392288615 881167690 884829164 896511259 720551576 367350406 84154313 562339051 772124992 265773441 822630242 626636756 100185106 992346962 670248375 832588521 220981034 366409906 335351728 95380352 140406845 966681994 43797767 389584775 857506467 293380889 932882439 316335393 721772603 489923367 164377011 956751400 912915 986622322 363467153 296126726 545313994 351468711 416963454 511806556 667559013 8187291 278363396 174836564 289952640 936059026 6060539 29435235 641517300 100976280 845983875 420647011 916243043 731450252 587156513 268878236 191653137 305965592 410321510 305472980 357684350 872601928 57291481 226097607 14082691 562401824 310541716 999931146 709299484 728465494 650936504 336350651 765264585 765458965 875235420 953915704 948809261 373537803 798122026 708011243 40568116 75804262 968598611 895296837 314727806 96256725 883796823 372925097 134412532 542505844 655694305 263577648 321264731 649269325 794090340 554428729 128540833 717185240 507945848 354139359 982058876 546013889 725624536 812185403 127095348 810696347 658217280 714239973 671396673 541935884 825781332 673261100 296731810 86880291 146820327 471317201 846714520 860143505 364857311 607364824 439274973 941683104 959827154 262178521 458491164 96301803 81613889 626613433 661027980 90925930 716778908 782135368 467279406 256742406 703015155 538751859 396085209 811377037 900646872 788035363 770596580 495975031 279309863 975846413 472151702 497633158 722199737 278791419 534174755 302431247 519939795 743642719 842538555 437107037 652703133 418788485 940471069 20486599 271586153 305278165 99732758 860383085 185983070 803504498 189827696 746510856 554198762 23128389 511920616 26990291 594019733 311464961 201056528 474453278 239283379 909741274 56956275 384629817 25321541 288525005 355450961 571152968 746314543 914694296 700111422 738638714 665310765 856666286 21470412 182197641 948520220 125664444 340397463 544071136 434107471 697370825 801253263 954988053 91529595 371534411 176852586 346556855 325611949 515854294 843385862 684937939 685782273 566023775 358394398 723030694 933365800 380314935 783701348 862197633 10447361 182975595 450290467 315904642 425069680 773677664 235599933 335672253 281753466 668154602 682846861 287797612 240448520 187104340 740330548 300732565 469407005 886993303 79653396 460883129 406533209 225415154 791515742 321438591 129257621 2770954 502685587 755808291 186318614 225677449 926358750 597921043 548503345 25109542 165265414 834498433 559048076 187444747 958591339 4768379 829766044 301187812 340106826 920487116 743604624 262614218 686447624 503478836 748265871 407229844 483484713 294249257 919017762 927353579 372572270 788994905 962540098 761913315 122426595 526107120 932485179 824861676 762296047 458428652 955203019 465189549 553633527 493774059 936683035 236910229 169610203 923651861 29897269 258750677 700665550 198159496 863491142 243751794 896890935 817352122 61471500 768545637 353232461 427106810 444304668 13781904 926224158 975735036 292938347 132530973 688375713 851422676 219889164 781723089 612726768 938075785 113123370 773398539 754546664 331371592 44549432 231914044 998343192 377690817 801405054 203087172 612696654 719574745 768500421 826518633 3026493 646438894 428395120 186092731 593622154 37384706 976201379 580401267 365863477 462673104 970491001 199703931 515549271 368083903 69381633 541466256 616500960 632917111 822083415 476643773 887134493 971392825 528835471 46226403 444816435 658207910 638091910 909557908 62409105 236564211 941729413 213707188 239908375 762232805 627373581 486373794 603544569 992177503 721694501 589123620 853531860 923441937 252685505 12210523 206923818 154539621 746231427 684419047 186488698 416466369 956042805 835964575 197255992 428898096 526469578 712996695 656272061 566160022 170672073 119903568 385942795 717951207 779076255 706371803 300155385 115718156 344198125 561911463 204121253 335650017 758549116 458849784 239479197 422758698 270840188 104774408 490879649 158022990 191790722 86808622 229624859 192447013 926228332 852444384 802081292 24522655 268611738 431617248 699109176 800936388 364253709 100258207 425025620 227713590 705859393 727439709 805457707 647552438 263552945 563023836 173752582 171640818 439899046 794531011 251599312 141414109 803845363 134797900 168912879 795035049 326775574 369223329 193199642 312617119 33144248 278672055 583959366 324972105 780033798 340587597 817728251 696367694 688469877 240262202 762802789 325326452 443565227 776211508 114305043 913150574 272063879 612835974 560735828 105118226 929880624 541584662 679962239 627778877 184797577 314052698 464544902 828000372 837400855 782078813 96770418 575306713 79159654 145015583 937487786 697381465 873428752 895348667 428644857 250101108 724042385 958685895 784352590 771302399 330358614 300321579 436234567 616821123 860662526 307847934 13369139 99467875 338307991 824148665 970711037 665807034 458219927 614000652 405418787 142172884 32545218 377377112 728849041 876636075 941085411 163304458 697741481 47902883 657394000 191151473 932043848 250180011 154033958 783642530 104042886 648141471 685609523 17342752 73646650 17289652 908832397 566896428 684857210 633292439 775584843 125421875 897972219 610462154 82645791 240351914 336970202 336721340 554164578 408831576 853835658 116194793 555987978 963093602 574150302 973764451 573052606 445001686 665742665 257466477 724096277 958594443 686044771 818057396 138158996 724228601 990634077 461811788 852024059 410578705 472624454 779349271 643452442 519613680 267292320 660582139 829909461 566192984 601026848 712185406 262610888 94104999 840833712 377621093 98452850 167089193 255157809 242043898 337418102 200824283 124198341 503322302 464300769 18992984 765731402 963967606 407181616 518963824 694879046 52571514 194032833 682053841 827030026 268888056 170487174 106767590 701248695 830303689 281589278 197907598 817086779 104754265 964640880 56906449 777026019 728557751 53962595 655271253 39388010 8199143 21015458 221480535 935183436 704682038 178915432 152140851 854342598 576750778 733414556 213156463 675975388 449234287 47008786 867423064 569838651 302596421 973255528 685972391 646494638 438281233 289146703 96155253 767607999 360634997 485239153 841280066 116932272 973046236 876179162 845081667 804524588 162228395 26722141 345509303 40710074 831188159 188701649 553895934 863036695 776185799 194564829 777783264 921723821 71087898 510864432 342406564 287252287 479021512 125036867 945224718 579952241 898228796 896532193 423031982 620363102 95665929 434306496 404542288 625009052 535903329 734740950 904397195 239159128 294879270 269999213 308864145 892352535 627183232 780702324 505191555 726467374 195868958 670598031 144727252 519341636 489497212 362412958 779390960 391792710 778831252 79348475 975803688 886192102 382718206 21019840 391989325 844722727 1819494 455550497 829917367 184284843 646628442 622988847 769922117 513140648 470623198 640681204 920193488 365770695 29113794 798558252 115281185 428232208 376017335 388490097 85105910 626380414 87887880 836084134 566872682 87702684 216122023 437445872 626535208 472979533 929399823 531940650 823882214 325973558 248430389 183631633 89662930 228493656 950192470 246653050 994495933 414171588 374494901 553804776 460677259 331817226 145333659 825642995 710180792 475859201 421833609 305833545 803015149 345636815 577296706 989277488 42783810 661531163 334954538 409676827 808596167 896848272 688113882 764612168 632531946 864613608 672504645 161116683 605036873 802417945 641124330 480114248 620421110 68147960 533427941 92036687 757747122 573398421 369492566 388715434 475238345 70822735 401449556 436367466 209210487 792149279 321888968 215011683 55015079 722544540 325527635 426308547 390583097 328697445 93384101 417755280 220455127 635902921 249541749 382927939 227470205 533457163 350221704 74838619 144876102 663981177 731501359 144579249 342654862 168917556 122365236 696580612 593599775 990977639 179648176 903606613 58056322 457399478 163292147 302814311 419994813 445022864 693508970 559716218 641500889 263988342 5205977 721690628 793290657 24078127 335687778 942603294 679715690 726006732 32673168 873058417 393788248 338542622 19610498 931991021 816345529 990121525 186967187 179445451 674547907 574366615 277066160 866776983 135351120 48667312 930295334 775821201 595024623 34953370 890631050 654717989 306599408 95708250 829835339 100435992 941682336 287529730 395183827 373668264 904131053 506107227 335085747 67582776 324600003 391667003 995732672 957394532 952410449 477825982 228618344 975409340 837202026 945920239 342457878 272663885 979243375 814385094 849817631 346523160 904919300 645516297 573673513 325910445 294151353 196676361 197525009 579067538 527871918 850698509 671515726 957043165 741788640 262524107 170383210 679541932 535887994 825368850 436109821 211668924 208224213 512034589 552962316 905516312 275913722 864886777 535054562 11290084 200109344 624164137 899942534 635395504 338102819 991089226 610334605 688511750 121932990 539751015 630017193 182109450 272040344 264041971 956531591 819844741 394154272 69574984 607406562 14168732 215813367 611360862 861476201 676137488 804332917 825739012 245635316 530224575 911048508 842369331 40155020 825210567 752573119 389627009 457868790 90809424 835459391 762953863 465485962 965142995 65582091 878360127 226545534 633299204 994374838 96083013 334177606 592191183 160305223 15700533 805830825 591976480 45069824 833705190 66408750 741453985 297518779 615698100 47400978 120548588 995712684 172807466 691128885 845114656 519586444 591480859 805166392 521891736