1000 1000 291517183710823305
379608656 799855005 698085693 612639011 807229276 531872131 626996322 812272553 862975551 542754627 652727444 969937721 710093489 511694794 813414985 442459204 871338165 95826016 14916833 744721720 296805847 671118309 191620070 745321401 908132974 279366166 51216459 112562153 239088348 141992647 967276463 657905058 144847563 390429479 94974361 198310840 264869487 922529537 614994618 217695033 235186120 61472247 684420144 325610158 647057374 448609991 630281407 82049369 405665285 561984648 915574295 251862135 173489945 564414443 486764051 393904253 826572480 474661499 888446966 455007325 34758828 888049119 394835885 144557759 89333208 584749333 67218705 267187530 481045960 876843446 144956196 375849946 131296203 720762167 705319248 610173385 379225146 250028067 63860909 675113256 93893560 443263331 405188922 177405956 17091185 694483320 446415137 287821219 172953949 41306557 503798261 160367046 41529724 778167207 489171956 258446823 209021720 526452230 237926214 597671546 99469064 70654531 909453630 940207661 234554857 821303202 586434966 246584617 884725093 530277503 722788276 576984144 946945901 158255506 233374186 189970047 793265024 862884141 443791535 535129547 100753892 648500858 357166056 262074565 145737449 804958399 281303075 105783736 307430955 794528411 113527256 430906343 589173710 565114696 708517544 253899985 38672833 75554777 758052512 303392111 587820286 881472123 800004980 74242418 781383365 48078261 744860102 85802119 873002982 590472105 708895838 373426068 487384054 947201362 222880624 996503546 245923990 185665990 814989275 188032211 131111600 354367348 695635558 94822450 38898107 27873124 976141059 494504039 521380084 805002363 948860430 37627194 883912357 397382326 513657741 278267181 930739552 11602027 350887022 17928893 678879042 344229261 861149133 480428959 192650034 474898663 101277229 391906820 801426977 973506397 720155836 997718487 168451657 688397616 803556497 327534075 641775215 227246392 362107375 366174095 202165538 803748905 625182593 559915820 817025019 576969681 649747358 282465827 242374366 691174997 447778180 524824000 756901685 99188601 726172317 257654924 136930617 255977943 90826687 607920004 467037994 322552868 527843941 544541541 726468755 32376944 154891769 414565345 45687177 662783844 353943308 222651112 95805931 18814339 627744921 731016674 248902304 705979499 860748615 626245361 856525021 118464019 481213606 35761714 730464095 273243148 835348590 637611770 828310443 811116226 906895813 292730650 882400082 731120826 728947831 42247708 445258544 218529235 184658493 167638661 670958250 615413383 961108473 666070803 375036141 373123880 980369654 899168255 502533172 863590181 274603561 492845114 996997376 216920644 730942836 733858480 189381471 873799655 243290848 43955593 89372711 950249033 374624736 483963749 531657273 326166464 695602322 34399389 659143104 445349882 247084286 806783623 260093297 641134402 722980439 403558576 126953419 207259577 403292215 74204705 443332182 553851039 216143332 65674396 841281253 893018505 241817999 917775837 135179990 634231210 558659986 220457691 760368206 135613708 246487471 849179398 158117759 71341013 320130645 301721992 115022307 191472005 606243804 7595142 952403840 198227508 583390149 852129886 774880291 149830102 706585084 523511528 984904359 415790968 118513176 1597623 779985965 127967874 725178007 87493719 765513059 313219572 728560676 763840910 371848127 515523499 834301139 491175068 678063299 598461339 375050081 993964925 311747896 504677139 267638390 798472483 549390452 702329342 733868004 169062078 949180822 162027550 746611687 65072374 517093574 845132369 131069540 265807148 802395256 415820750 359653420 580578495 75285671 102141286 662239800 389105218 630373403 604152517 157084908 931993800 276411301 142371247 917990741 655292187 127410528 531989317 514398317 18628862 887281648 78394176 308996179 355665007 801489859 371778866 177615254 486501097 111575124 69343178 234708073 384636059 431629669 569942030 970262509 392428980 750076482 552688287 104287083 134325145 894022914 415411962 448247193 29491754 109842887 272309940 833143762 622557954 106813434 996772539 652317024 585545910 737472914 821726873 523935924 816649234 814591052 879754674 77874345 664311649 247816945 645900930 407995846 744656292 383260308 416231905 595187066 984061911 625870803 496681024 481065312 389686833 716781588 655915244 80712827 310473569 847861447 403971400 172095096 664665556 951752871 6536724 588162800 467669739 717099770 97016490 484191909 52257863 929312462 516900413 24811713 64976639 561225276 508792090 327228956 847064806 502044583 575563240 677604981 608006599 352972539 161022697 265249717 495095466 822918896 18321209 471305009 349359886 492592197 880000011 397360870 324423727 530914055 979950577 825311421 888667711 833571273 885914642 565319110 779016621 71420652 220730739 697116030 367586403 52159958 375711793 860603659 785077506 188770364 600140995 682241148 730058790 490793818 151463226 14863883 380921253 703277366 369094273 189574492 549731793 411932642 176471455 270293181 377350323 257999033 440404721 656026214 410017616 720922527 693259123 72257976 90609893 718021699 71944694 538211967 470556204 302824287 152728168 529726002 409510551 252705779 807840017 398465327 61781393 91999887 845265361 262296577 540341186 392526471 217884005 602545308 378460233 938879806 171609249 955349405 886025729 165573470 791708085 971263372 939511998 708825628 502046570 401581595 344601743 448489078 25253476 466015590 569472763 115994742 987835999 272457010 337430086 130021486 424656755 625312816 156035243 879325243 523138385 95890744 737801632 748709507 823258757 733698704 42763543 484447737 228815796 565649189 775568057 804659350 68788445 88008654 836508971 92013791 559423130 779844750 582948170 283613987 930865501 749345232 1321840 601682619 762166453 783231914 15371950 816007498 977282184 627405084 216748050 482850813 2711640 752419664 307139552 826390218 921721472 363040473 476751066 490640818 346457974 471146742 553169274 400608256 298118408 730600141 456211252 613190537 95368609 362633394 751275959 934101483 44841859 757526879 355406378 167250384 635632651 366969659 542164081 450698282 994675953 710830486 647816806 378272118 398746503 866118120 564391714 348052219 707734007 147093271 25945140 152820746 548736136 553053359 900072677 338795837 175293143 9381417 953857404 931837881 443504415 695201831 613746293 585117294 457701235 371073459 416169930 22490451 994833153 511161733 231016493 413569196 745247566 700839228 45691465 95623750 4195710 182348961 413619717 640886967 252769674 93698281 16294850 95102112 753238921 805403633 501002138 738912236 885296874 552453506 920065185 409557264 595791798 77936780 499070501 676039755 509192144 962306668 493833968 901067493 698525238 475626536 878493314 451714673 711179839 947438511 166694489 715782668 530456796 519131419 135959850 263894429 958600664 662492656 202409511 379334933 133259546 936345692 987526200 863902126 829721568 430168183 11245892 9345326 835766788 693683586 660770151 891169058 874549048 378581289 255068731 363953701 75169355 400372931 350770705 296762648 981001827 122088590 321318198 108632681 879291457 330378485 370182449 348778318 752112514 3422667 821132801 967559432 737011675 95416719 236231520 572311587 913518170 240251560 318533124 680593330 293924521 133430440 727539419 136603797 979950668 334545803 34868812 12962996 415988191 7507190 3038074 524378690 762255962 860614010 647122817 17928956 955758159 546234832 773772985 571655018 521336104 76736028 520570864 151665179 480483435 203899691 847861682 712985322 105216759 191764407 407576450 342648893 981295686 343079327 981478687 921500738 694593963 879927089 239015874 475185201 818935187 115329122 149837660 416506767 197007045 510258706 428538842 93300071 468684196 252985675 543785059 962693008 870756713 579272320 686859413 866788844 480037739 245740240 389071309 601447332 335386712 456640321 301438558 501585006 414806907 896272391 385520854 395889609 48584182 304971196 805011262 356884029 540362247 320724135 126434904 460448926 174681668 123983864 208657633 40569671 235690208 573244679 604658382 992233825 554400486 734156954 115815056 237644827 488403322 329229341 329011794 957151217 293145373 455289577 156951863 965087718 735143143 346023295 748140190 341382347 246269389 973171404 508955488 895373432 333339610 480187749 699591950 534626064 639669111 294068425 398796085 577004095 521696420 540727972 572208795 270538364 730013758 369780232 119983233 835503689 279175481 71243955 791252960 581504368 797881317 114813517 194208942 736937029 215436587 150675880 463275800 889986792 272865231 660808192 164585159 980632194 383165869 660004411 377276957 710976644 546439421 1868840 467794806 278449133 784824720 124980161 908374634 19939459 95608850 823903338 590840071 363654678 644189000 593472561 989239064 464376257 677789521 252451086 412769122 345862954 493541095 576992290 344742115 18205120 461505693 826923257 786501652 151788538 658558495 607548106 919539750 427846811 621578615 769048499 860792902 791067122 5180996 97043455 794142426 990541587 30118658 959439713 431619778 365186849 251281991 87211064 504947354 177766534 354535425 597504715 939566068 349475894 579591354 362843788 159989921 285362418 292473558 847485271 956206566 2506880 136038866 211628721 974000584 505329909 488164740 959512331 150935619 286551021 765574495 618578173 232392844 276228559 203205549 633574541 289218132 494553355 260156117 928519272 792060677 301314397 543494292 137196325 762369796 109406473 687935813 362922119 55137519 633283614 134162203 487007417 935689439 770352566 703466851 705118609 846362020 732054833 860530117 945632207 461538317 959723903 194268546 824547933 389570591 839812693 4790964 745245582 607766619 422477172 292293010 297176672 610327290 457801703 7673259 878956988 702959922 851211586 940004648 471066546 825463920