1000 999 836450732579279454
340337419 529260456 698144944 230969771 352467800 376383658 633014992 252710290 26310868 749881053 88173675 322531443 679808220 597192254 767234128 245906761 252058118 395740051 296546860 803381878 822305121 182589871 836953029 271586569 254256569 679521963 760823352 943115770 579618513 307038508 704060224 418536811 943816872 535969185 572589680 24786406 951782071 202806660 638063221 445615523 346388783 967668374 753409622 801017280 518698045 312858660 232415414 200640393 114235208 553466950 657180430 358338479 772709935 235533596 835528949 558637970 430979724 849028625 359240538 155243642 780708597 72784666 974105029 1242839 533568568 551106549 921670555 278286726 760842908 769238892 382457689 801134860 840394532 64246929 636073942 126357722 802874060 724168706 52130691 45322377 82060236 606141731 352245163 409629981 585031378 342917480 797924789 339215940 192226890 284315018 609486431 883731350 547425175 883344079 116080898 123002836 214119512 44826180 281651922 829349930 937009574 34452484 571719197 802423150 796566866 352242288 386470281 915771232 258645801 506770293 943588695 305218538 49967665 932030411 813974180 50065504 738977259 666028595 48610981 942319294 496147345 628734134 551464936 154494190 93362006 254305770 226821015 587641857 430322091 634330669 837827253 994431859 168480886 788288745 408368480 969904233 77128794 906103761 714109967 558494963 738264563 616637984 980977364 908888908 489341208 24730078 123835545 886676247 24937498 994824988 491679844 801987745 143776001 119927604 807490708 508086820 709507795 162642444 780341283 775041279 94472398 921892177 533436899 103380224 961659819 156736958 519494595 234661788 589999323 633453140 70047242 878620979 793403851 430394785 693162648 76317263 261187361 196613883 927509545 851020515 504234494 122338756 47246739 664618893 39616315 170007205 948807428 511394518 720164014 896822484 119273799 702597742 415038564 780939088 370714365 722303090 69700582 152545313 780112358 194949800 642871670 795252635 934555160 529668543 469388112 702342041 933040451 806490258 885293803 166901955 530697205 459195235 837739576 624968650 582612689 506314017 959654111 899518121 531330520 442892452 903363974 752868835 681048994 124682733 510598923 953269193 695840419 23645033 536806343 587419571 186570856 702524204 142619339 797316419 799633113 521920056 898188067 689651111 202486135 57548725 337906967 434808022 725292700 918681656 952729447 855370447 271911103 907193598 38438028 188624095 638201775 626041135 357985788 414839513 154511829 793485597 684719972 603810397 379686260 644112260 454815213 709179411 849168874 615764170 120891769 909862639 665104622 759271997 637461988 905490284 994969553 566924633 637632069 769767635 446573759 271685378 918440492 954519155 733432829 886716611 902789859 325482728 912586538 297360407 794077359 261223253 893437568 703011230 868377102 683804843 402939921 974981732 859328249 289993442 511917324 294939423 1237025 518731325 13660407 419773296 642804274 521928328 246213876 811773214 439207700 802044507 480443134 584008544 270576423 441998421 159762730 954476049 816536196 858046563 250657513 429657339 495418433 956101368 862466626 654614287 563781035 945275989 351331610 223929257 76916106 359118784 965831277 596138958 651434338 836718798 47319955 461664110 444172974 170442906 136516990 46569636 795442213 35176717 354648056 123720947 448244471 621625878 686874343 290126472 898504718 208479473 100806539 368330620 887557455 48937314 466778044 988569873 25656024 171859192 592268078 344914162 120117313 78195276 555821742 12892277 412068829 612242497 721153379 678134746 107661304 340991299 314159632 471963018 775909400 532166282 404186702 254378842 398300221 573590358 179658196 9379783 556130850 870453298 918080433 218239802 181372540 391961650 346707853 687641923 858198584 330141239 102615789 80492512 149056958 385180199 572213358 403683508 474643506 634512951 358996231 887994962 966528687 78031907 402073417 343102321 501190540 896225906 271977120 375148086 587222425 399722932 906460816 552354671 421357408 159683525 344461818 96237524 806361190 937086217 144224855 19849030 264072296 43557807 632464633 623027730 747514017 785356529 113541710 301458477 91596544 210429008 773716766 305802358 954559860 837041881 655348170 65501688 523022114 274597476 97713549 701870375 622713258 753668305 314135996 582369568 389171815 39504203 135195911 837039851 983472045 956164487 137328823 281608378 48486411 968724227 864096752 10649897 629866377 409165897 534490350 191842429 356126952 790940203 70264393 353278439 942160614 482970374 710966835 417778368 918103929 812561921 489538998 907014092 68448529 612892748 604741112 469875321 181030872 736790627 16923512 336822815 528610035 221677899 904164688 950669119 163844031 309182929 745008242 197845701 266285334 119958480 245490413 183824711 327925898 762424169 550736680 917284421 670128550 736004681 334117667 943171433 489063730 540586216 59769274 523746758 297447533 680886726 272040419 553932059 643034194 856409263 143004140 258406671 698661077 509092854 864096960 481156724 938811941 191048122 804085537 899073669 489578473 483021093 926628588 856136745 261545605 16629673 341391450 678936368 715533396 39795267 194222395 547014034 769460461 249009850 789375546 87015605 38149215 445922527 370497566 495913637 372546678 936202188 807998212 52704604 698456566 879908647 343671719 400087033 133136348 454330973 362064538 734602250 250612386 706328553 8245643 698426564 458937722 812030092 445883520 202323015 834867087 823654036 723400986 278802652 935873865 977862935 21155286 737004088 936647559 151282999 237606216 570424504 888403172 809022813 717028704 635354277 899272948 883842175 13069991 776631151 819844998 669666140 871740800 649063667 255967713 778829756 349069673 530181815 821342216 534112690 486688825 116823338 661250040 699571419 814992225 368287463 751969511 422808479 69541165 859082736 138098820 977469036 687634434 410926836 528464443 753613056 261645215 637676683 10225776 423458717 310234718 731640438 395694016 97522772 640855665 313781474 215453765 382646333 257108263 74391971 853142224 972889786 715478566 910171003 288388655 534068409 855795376 854852946 329271910 584427505 7609568 82335100 666142199 77885473 110949100 995966200 429475612 551194709 451355746 999021742 517241609 878849059 970647916 62746798 585932589 399352552 69944846 362509684 160762479 357138189 595102564 456238376 532754034 652720453 55468775 881261784 312389843 289308110 122159014 548360126 491906151 19213229 710988687 526698622 852990592 77790196 843796645 935092325 836126759 959866622 640159304 753501869 924428128 204029871 648582258 944233910 432975467 966262966 353450230 601154636 864500478 960229323 957254849 367377125 236714893 388286707 621962011 95697633 513561221 114462649 877679844 235591114 587011978 837983348 93410265 885776531 26689214 376394630 953145294 594216667 922950651 814058649 141336050 464242729 922112533 871065569 390458896 27660078 438927386 295348062 898123722 26054408 694617747 716245528 245686238 390852219 688080578 239680867 447955299 82104631 214967268 648924699 71723274 760022295 762940014 107303398 319875678 746214238 279036242 969332855 389006086 198718457 192188217 926383814 576986112 424015041 360424903 296767066 438913765 829506744 529334491 676526721 513971498 548387145 797151182 768304532 719195482 807213449 505778865 665780790 874453598 327083386 352520593 241509011 153519287 612041029 903115700 291923363 932314560 12860029 574890203 542340198 362155246 302657376 607908992 510612262 720070417 777262614 574544151 103555258 963532178 254603250 724705102 74522047 396299189 875443886 445004622 167031263 587106262 839662513 2577913 456056587 106819757 249992010 182665260 21894338 340215436 456374771 340594172 539529546 497737373 876754832 570618874 241821939 348285478 730153135 96238193 273869657 439089094 850828232 995597476 376901792 600759991 293872764 748355603 270887096 29153292 68038360 903950772 307233944 363470322 97486992 140672315 815476100 958734064 496252998 699335764 273400904 849389864 682457794 910855141 760497276 471998358 893425209 2490703 265142720 646283597 775924103 466536364 87196927 829884607 668791671 302129423 595894189 455571699 574050296 646030793 431502091 832549070 372138854 514996640 775741791 975601229 27368905 759365911 912539454 169996230 329666062 298777770 827952324 947385132 140282193 135101968 863001816 353596746 915542037 398243193 652969579 26476292 361867144 495468752 700754871 631323803 489358018 651748088 626521473 958123239 510616067 766224656 604505688 159235740 671656954 382089649 526185430 610369416 157434618 896354348 41692124 243808721 653409348 354467790 903078359 41802040 21062978 511604509 479124991 60619866 286997703 208984857 155013780 195583979 771111505 589436030 372274465 509789691 696689481 156114174 424988603 73841971 584454720 801849482 906279489 857638422 95088177 361159303 759906203 761797698 79819203 573643034 264683260 811960238 287940230 452353631 53739809 173857771 852725298 607933867 223999889 983689061 931400173 565132495 931309532 865643169 262045571 602229077 203008223 228164990 285893293 695057346 140895228 569458806 661787213 177676501 389594724 316004827 287745454 702701252 826171470 409914140 276299206 394282115 50760766 424727551 499904628 1105150 23574081 429880806 996797380 708210779 102916397 475055373 448307496 819817786 181667299 655318983 923561150 528271863 654027918 350113221 304050830 101802980 757352420 230562641 62408139 201898129 327439457 715383948 229081103 648008966 138414992 293338806 334886048 705278213 969930051 709896548 942961072 507957834 945059032 930279881 437735318 22011852 449205364 808221679 679503895 909889275 256331849 544859133 181446561 174365953 466905553 500126576 491040908 68152835 975948562 534752355 532749913 615295071 966753241 537998025 522175732 600754158 695198977 656296879 14006772