1000 432
754097252 786325039 762025335 907518268 279112487 493973763 36836162 771289229 855105738 143940968 86098623 252409115 442358242 692990314 430874734 926747107 379804701 117208744 372301015 134387192 808751080 975227240 55606860 91236357 842581853 42895893 873982025 531754336 757272776 224411317 635478891 297626568 706905469 617893689 671148462 351246434 697455923 995654213 565617803 228221031 330325014 865275403 974293392 875222770 588994666 437586404 280009556 997336311 630983261 282800301 731306565 91063732 914255058 567194974 811560535 7471775 617285220 474163752 881034476 836803787 658565282 419707077 142900775 203992371 301051510 255655553 147815110 913808233 105065648 662212707 601081851 161311866 190873666 463193457 926254659 614593793 585723076 505140412 253928827 785088873 557249083 6292451 708120567 281064348 468403328 574590708 905153625 538899750 570782900 104080200 563622441 175216115 210324909 752958729 87373199 534785483 767111387 639967370 526313958 816752224 426501899 583826683 781599751 313949417 401448161 523250295 587736149 130391700 113761532 272077228 986607603 655130402 164363633 41111001 169058635 850938 440423797 887072425 258598383 964328815 629582115 905612664 12959027 215461561 529170737 754657798 814965427 456468001 949691975 70943863 739895135 794986145 187237873 808174758 668865013 721977503 678864660 996550748 491443374 992117133 763214670 179420403 773337502 795412465 705120337 659824100 257209651 726467935 926481908 990900507 46114095 836619249 971035373 391517293 531795486 937465623 652713591 875165475 831704624 706233576 162548387 936959331 896543490 462266773 9476821 713256227 929773668 4087296 411407321 568581081 995433597 723689066 230775773 383011882 665982833 867918270 849180209 485067808 22364570 282551360 24025743 549445033 33127323 905515771 5964898 682448866 213543077 950079345 804295206 447619279 220413908 658479495 355279644 628393625 46574740 239123174 306162873 744575506 79812399 67991688 284672770 575124180 575275084 178014959 262776903 188343560 625391567 979831543 653323760 384520670 577441697 519611436 447240131 665113787 262267456 498290921 147085302 725876439 460933767 26030225 615198878 676701553 114685514 324393503 215008283 879364101 179101463 143407919 230306774 30643470 116594764 60951093 420910033 522185164 320712626 215248670 608988323 753177690 903792247 55526002 598239002 234828902 181016112 830241627 111385003 45641160 654534631 787612813 819823427 111765064 322138380 842759007 510442055 784042180 786582174 218755818 16890992 401972455 696596814 458004560 508930669 393776519 726412632 211031617 872370856 226157871 494576161 690695863 855877691 151557132 12696939 281986593 630081124 63025819 986909210 218108335 293648354 37808546 723158946 698338736 224441005 404429081 973065738 377668290 444101985 485638236 676891587 261294614 507249315 360333595 80772940 590965670 796987234 224523870 242479471 461967946 279150593 574922653 30432665 138093999 555114714 306969936 537590317 552212283 184070751 401259816 723950444 715994607 46502045 231321783 784315368 470723709 993717760 821046072 160092951 142769320 314731757 894927916 292400198 447245888 545792597 479840300 100075245 635908409 501044800 541833567 897282818 823250133 446615982 186640093 675533432 129904633 829872721 263484668 666998101 997813358 310991106 98864418 326786160 530451812 662498481 773380736 167751955 832596154 43567064 957424694 24987938 995166900 364424528 552256156 758860218 240786838 728919274 519896446 446283406 736032188 285003719 476667709 50920977 272310204 14298952 822093025 12119249 829114890 569710680 550647889 900755135 601560003 855064289 513534170 176520008 782137334 341224414 887078196 238266330 2011924 394613256 973626999 360695570 344120740 474190248 399127342 981921376 367683197 787051226 844363383 916796338 736792646 5718654 178910891 518523431 408093555 865272112 2726728 715120011 803113322 302892440 236280475 688929446 83016692 557262811 660768965 709740516 219095606 475130982 549007684 958047734 161204900 993604133 790108347 981886631 981973523 511338538 107492053 827888923 841412610 941834560 489789550 878009030 51410869 534763767 521307593 995662590 481922923 289295262 891412999 963071185 340391789 308351213 757492164 575705074 132306011 68943612 388503248 878930092 539358833 602028566 181522308 397973168 197770037 64135636 245340882 729384191 742796451 432075373 943490902 780091348 127155297 778715402 547939939 851126571 147103778 444616561 54255837 80875831 39457071 603748709 428906479 692806504 425322759 419001305 664192438 855461349 389931756 898085822 229716414 926073430 96303304 863129811 571157757 853845061 217338531 730688549 377150516 397203929 17530340 199551428 249042063 308927152 651002815 119227966 123137810 660714163 661355389 67785979 860420836 368398135 869368929 167891443 157395850 265886803 467332649 827922565 894563654 597418794 729926201 213486850 866386383 289778000 386893013 93571653 499012668 51452922 895114053 479038503 429013709 550538207 670167703 596846326 424590772 748737515 708006483 195850950 613224817 521889813 441603490 532480913 549022001 197593284 598148894 523190645 879058205 733378848 676871192 102133022 713754470 739766276 969926595 493935761 67661757 292833994 187613567 223939822 318122291 403753892 946067342 400649447 228555029 280537799 565094575 663446640 117761130 378582502 270667207 130834472 276109717 587487001 708466263 174715762 108829085 117870407 756984495 925121622 303546186 404924711 733470418 613178210 366561119 84046647 426401060 318311611 125830758 706800471 106841909 357562671 541841842 760444950 637070150 571004872 92130672 250518542 139432240 971220833 32442756 332439486 162408699 434456411 222577522 155558229 690703100 194273019 65214647 781737031 687406506 868741499 405428474 601402712 142953720 953662819 982329174 785972041 504269023 444754859 294184282 343365968 55505176 2762307 314321644 931423191 612456226 863465899 245772909 837490164 569241450 231262747 278278120 876907837 44454427 247252967 413166260 958771142 356620286 775167478 245890160 555039314 528971829 407897609 389622828 257469436 949945471 411747540 621229127 512227464 358154147 337677937 214336697 21298571 665123860 145840092 920128722 151641795 627113110 920367344 829392246 428476413 684228674 667228964 947181502 538750105 407208905 199180308 772725250 176156952 509185966 851315112 49491471 277015069 13262241 755025274 425123468 595117082 659974391 229656154 863272535 612801130 32623161 378600410 941844101 410114279 884760508 743250496 873617203 342845132 642669781 854903806 466658063 878940035 803993943 494158263 206174200 590832196 292291569 967530414 172693305 359512490 997981817 404660934 192181284 270965715 700750919 191655676 462072274 211863873 33295283 496078443 81263540 256848756 929428366 416171108 744542685 926649677 546009787 795937053 209464799 891379362 6356139 595943728 772649917 427549931 312298618 841457792 214040580 303122992 172311523 678475468 808796390 179977786 620632909 590591229 641300781 395974533 925437261 374974652 891799044 461806027 680461231 934625785 961026943 79187508 228961010 309961984 19602238 185298964 921706779 615663374 264327980 352015046 973102971 363943777 224039060 462664628 278459600 233089863 909449822 942868360 812655158 923034380 97391227 62862627 575471251 506692488 157751610 175668594 71671574 995537132 612381829 730645454 78052521 946040484 471894987 856189920 614512760 643374112 939102665 953764378 921272201 432214841 607457457 398097767 502712521 152171490 650391182 793256574 924965492 926178435 990940419 740205579 33090336 301865510 969552086 531511647 803185979 321948065 75004842 187265473 800167875 658624458 662632913 724354779 905737944 652411780 457797289 30679425 503338458 915932854 837313314 362230942 483787797 614509578 526367900 815394905 244358880 555463586 330422507 849300167 287648376 406782748 45663222 355232698 583033791 608848484 842651504 341515747 770312656 202175561 246585642 299944744 586309692 364199596 490430660 432634263 816553926 326707168 353479924 172691395 36596953 624581966 887275815 598713455 670280434 180046780 181858462 357940663 205704157 705826017 398199852 822447342 476388239 391682240 330300145 508525806 515670451 396741014 892450244 934511251 629960704 887187911 369529143 956468194 860443078 296620029 695723050 219116968 593723848 975246919 516518167 653309097 87837055 262109333 592935144 16967759 398259276 448691932 550329038 968926689 124065022 223410856 786177561 417221315 511956050 388033206 830930555 551759018 206812256 608738355 938084160 756220831 578184693 905435015 75685709 459479407 313717664 972188627 982684905 629420441 613334124 8936671 419747054 626429560 915691417 317351725 361284619 623929005 747145762 470292091 146265078 894008253 697159700 427117764 491439749 299206835 424629243 36186492 231609188 26348706 987455850 881477142 123619352 560561254 203491903 439747770 377411322 756955263 131120377 710920953 935324475 870346384 910381385 876659727 438192784 400392975 492400694 598689026 62090596 924626850 839372868 41824933 780487541 79021792 393288943 671981627 477087265 691532341 659361796 291623352 465579035 525537923 273190397 850642 297485448 281698130 517313009 601350928 994531034 376769590 489925683 489704001 55797418 933473028 938695421 55947318 305970900 507568024 39825375 581996568 72285764 661292233 171134601 745767145 634156413 147597210 367986078 923002437 917300046 413908088 793273562 488968348 320836839 661940630 986115800 530539001 666498801 422343578 17438759 672676325 463088247 670541042 910323879 222654307 295960347 425797059 926866396 19300027 615363158 457448220 583043636 890812248 365827104 641595388 956923608 893128648 430616173 7270741 634386239 774089931 637085364 786214321 643393390 393021915 306042780 364556389 864741477 918602016 593603537 539281405 388445579 455345916 322274363 333899018 113684738