1000 1000 945807043176205774
798179231 446550560 468308547 62672255 636261014 787507541 487797828 859724187 33697201 392650100 77070954 350335479 672480957 393988874 483196516 330700393 178776156 370823366 285333972 79357195 58571841 486877627 67829390 178315382 199307633 714638747 148415705 446576647 317461635 991783676 846547372 570115102 568539105 217133974 163216114 532758105 65593861 944974467 555588038 989069789 720818620 581126782 800311991 547442061 975509093 835759140 959607813 230900304 966436403 943405109 371995105 822255439 49252966 216517587 477756592 675974195 88882582 531863745 384778056 559974251 655184872 880084900 234010929 931974244 248851285 700489285 977260774 503764942 621436394 30455245 175491601 45829085 374200834 49739528 773324753 205105797 710759053 689343138 517757175 173439933 379341645 810524012 339909187 876384700 544400147 347036311 562378924 763548479 331085318 542165495 616307605 10197952 38469595 291796544 304017688 251913664 883890205 983347020 952514111 683495677 554430566 31237203 627734853 299346620 305574052 797214258 541355992 150781440 795611477 450481060 708354906 811600336 849021898 190141835 817856795 185558389 815358055 286772519 439441568 657857720 869973729 313353309 876228063 782447144 618772606 969723377 404706688 432695122 452512344 657785803 991867165 457942278 787475866 186744630 139027842 410034584 447097280 550773020 715536109 589208861 758395611 535334474 215442766 772819369 296114634 6428082 426342536 256136599 794094722 998015651 398492333 691368384 752678983 260897555 447879750 445842370 392799216 283210197 984524937 879709754 305522214 551452899 153687456 790691594 602474916 441312148 648966888 438116243 47749496 791098086 438076718 116693243 263184704 344058805 37709043 463994472 208044910 567431425 812854441 306515779 996474244 165527596 849450228 154177398 776394328 792548153 561038058 951990702 179712081 126326542 664022098 302686616 682209191 498798002 994267624 949717543 64974502 464775311 676681111 672224204 88787435 858845360 128468669 891496636 847055013 982302980 277537898 583801646 711023317 718064793 448985504 236339098 13965709 894470881 501847444 744967930 241014068 241309679 351290859 454229259 654282177 804343994 884985086 595453069 94053627 678483801 921161238 509148543 78867135 716952902 857724847 316883299 921457977 999123355 339983289 344933247 501300520 185515862 95073746 993455385 118729758 910586776 715334028 90468282 493335230 6899169 515041453 688445292 451718396 779177558 705413993 760695036 502393440 660987387 736906410 61951543 717813826 805296377 465655368 273184304 417468943 770669272 491723089 534049656 708749186 671909573 368110657 30500452 232655595 965197773 247425354 421633355 646146411 913562400 609820301 305905861 606580533 77515342 556266591 120835564 343643599 836798861 518661509 477975710 455767118 247142896 415772535 815958456 898163101 205660081 710601376 797821788 7731382 958706791 419353243 507587372 622225126 982561104 108634231 338672780 679840781 649878408 864434420 320240355 609114331 402303055 515845316 347284442 935039764 207944007 104422090 56005019 497647053 626792115 23195229 340729618 326276012 179878841 74566022 980807727 606233898 377503904 935362365 36306978 739340500 167831826 524868527 506581917 169364870 606199387 994108027 429565717 754552494 878236071 324956399 591107329 367676558 503088199 936900687 890591257 972397690 863105517 237190158 479824279 2772245 166079210 742190099 982861689 415403160 563124342 802012405 940052668 816545547 578203368 696776255 738298274 270393481 928884218 457244332 174054893 184234880 758514438 751829099 467688225 56365294 380439371 266658139 675784389 3416741 142797863 524363600 697205410 710881671 303892830 290729548 379485442 646543818 853365073 870164166 547867889 334862132 562334024 303824358 946568831 967121759 150417832 465751494 976387324 452725750 797792317 602333106 981581114 824529654 868044913 346407016 758509518 157816045 675613074 357677657 787888463 618707774 621687056 847437797 945792149 504692315 327209147 772502946 896545018 884313097 38541577 426467990 741354652 599623583 356422477 38656120 321315481 659938374 484766721 594705394 864263504 88699706 361376508 958958817 555593894 892542470 616958396 270364307 818472510 614445772 181218717 558526471 469381055 379746939 107556384 627110960 255397138 795331350 218603301 146545714 730975393 235715571 348062512 403845027 424881049 723987961 731943847 260525259 768157224 41273824 992020753 551558883 974228927 702646388 464788312 314974809 676814672 305469138 292070920 919432970 637135760 949711529 103126157 945649799 351912246 183007354 513217656 500890704 631309114 801255384 539688890 180526619 914954518 147135912 356709095 633046029 554066184 704718946 812294516 844803839 3093069 900238925 953625593 77521082 726436711 782967750 366370928 938284091 902964824 404395385 18232947 835773423 116649188 48800422 237290369 29748215 361711826 51919197 220174649 114483301 952379435 956588226 894952348 73365373 429858169 89499465 485509967 812458484 174279177 298424570 876883926 68744500 431761961 616400302 910050778 108861333 218044778 382060879 618230628 85455013 230365406 349352475 331327519 517370209 222630746 109582562 467013017 384472697 839098293 120062787 773273985 827850895 904148231 845966834 918556138 125813368 940199659 318375669 276311942 125135225 388052412 351248865 216046572 809946506 604007643 110140449 701659603 424526230 145969383 541234991 648418132 366962105 570738690 307114201 576395306 448310144 109025811 869426557 922784245 72379948 938235134 149040204 464366706 333627118 71094509 604909962 88528324 813911340 448212618 440513739 873542318 700397754 895584066 867831096 946379990 127497762 826814339 727083464 723817220 757504732 217621758 931238790 188572000 17253781 496206565 515954129 74400182 452990572 481924653 702950039 718092213 269794608 662353869 300987032 141371179 714560931 811083517 996942761 283985482 981788089 114336119 889589997 346161126 275986905 707034041 915801885 975549876 777182490 732396353 608244417 465258636 227244935 581569743 271219317 813990568 325450331 337726117 389156645 226073058 485590085 444584650 686221392 152127481 350415781 504317762 694034503 447326412 979905740 150492247 807873135 309559965 683348544 282012883 512258426 161205838 688218869 894460995 942328242 742379943 775367828 961109813 304408878 696852366 302849463 912494970 454562842 816671820 134921770 951862372 115548915 500381646 386877740 401407240 211456200 110022113 99427755 568390269 111623546 974063221 764698251 235720731 126819324 115546075 557887199 761646525 846773395 811187974 924686382 701447166 57862934 387819469 521401519 696470655 879867694 845229351 655281548 628913695 699179671 248774509 775115554 859073857 667428701 624919707 93473087 644211209 988021279 174489742 313918307 675024030 52318287 993349446 632118527 236669289 453870704 591001381 251986872 960773973 171006038 680447791 431600036 330366476 404589929 570281288 420177291 837898815 917347041 729371768 200327463 568754654 805832715 753548585 212007268 562829404 607258754 282355047 47787680 708384492 593933430 398539551 433147115 721177286 979413736 954416224 477115464 854669154 721479147 761231260 496332010 809857722 639675620 874194407 757110135 599834508 657633483 407099190 985017672 787840918 519381607 646739106 223995558 487051224 212839061 830774946 439634702 746572501 186658946 189553491 13102958 734919377 272960492 337349299 976484453 557852179 692009828 170734305 278682246 76902692 885173902 870652511 44553365 630562575 775502942 696569424 242420167 318078366 35338588 268091577 772462086 318935971 825671649 641112771 34928171 769862956 43717207 396762359 470328386 951003084 914552701 103990144 308847560 71890648 106866848 349975660 448997872 395533223 771743715 528221675 988795353 863517137 220405367 346248846 885541593 924675441 835951843 169723784 723787445 593518947 444574524 886276848 285765605 330325893 103261037 369003005 415580116 260006649 667537265 604390728 38468382 938040417 749482899 650015501 840875472 81887266 456608948 512296297 847107499 690077345 784605829 230698653 705366625 780854408 651364296 346919241 351549910 118932225 395446930 856489649 158179423 153980921 554213004 500564219 848748806 847308894 285668653 593991023 250596803 541397601 627637249 906497205 382292932 376456629 724177636 467545370 444376998 466665933 635710535 417590474 563486648 399095329 196416362 447157271 716130367 459054697 97466528 581023152 789460908 405838048 445700493 290652394 128149735 734782594 437042538 504503290 533330311 347935565 357347648 716059193 591961111 931779203 791221800 24089182 789694547 646717158 812086673 212103879 712513384 236309243 848068985 936792496 656428599 399097671 105897138 270157177 503090577 162088596 77624606 128034531 921747068 54394924 832019955 747722067 786495596 23211548 734310904 354945806 317866890 855986034 898021829 119135611 809589488 263675007 866439687 154268515 91019499 610900246 697857465 211421492 252782391 106867914 397105259 620990265 759952198 945778995 483668093 553441251 360459385 67064873 136499556 688814083 341701220 12374023 93998565 15294732 39873294 428127209 971860053 558625109 488702254 892831726 408466142 676390485 551104623 120185206 18467260 561450725 890381740 241501028 92414843 542985601 541946164 537235548 942571323 515838598 366792454 325192966 961738476 567146613 697904406 576885833 269589394 733042734 204695430 809923472 393914753 81797430 697358573 783629064 400261281 980406257 105457811 532821983 494418602 797608423 154327218 499267206 388159337 394738690 805604534 246812912 792312057 23196366 587257213 805530320 328187402 524207800 787393944 377234398 69557790 850416207 558385032 91646994 214867910 73013894 862543361 423736295 619318504 889594095 975322665 886889625 351687420 734282240 113706457 158021222 730394954 623634258 509205978 892324561 453015341 662914012 97616425 109111002