1000 274049675651039079 594545682 501768 433159057 199697 812382189 138481 863581252 928066 927088281 608258 190361522 802690 365312629 109810 27020035 282446 139756616 591979 367740455 236980 804464839 768440 27045246 237729 516992791 812536 447911489 786582 618653324 468801 234467491 800016 953115702 946915 325040442 620865 804310001 235695 915994544 742858 850394809 163907 579071070 598543 511266973 787311 424911352 138296 518750191 663849 508865505 107401 835524357 779560 530042545 754942 724093527 987322 542393751 516899 717823566 629534 886077230 584114 549273220 434546 846141936 842244 16108956 538421 907144242 409384 74206761 37238 674757672 659260 618537709 966513 951831293 505082 285514277 890742 401062628 467427 465231241 30344 30511568 255116 657037976 870145 210007125 767222 868768008 150131 28335384 91803 562456073 152195 123041148 954256 964356358 846507 128618166 128957 738976890 34636 74792487 708683 230929706 236687 662567929 608178 566536217 855292 586726179 474733 805679757 298136 481909842 691005 185784393 178255 253352918 578584 76917008 361564 211435393 288255 56885126 957321 467234379 224109 293173529 434383 812815763 660441 76108607 869428 869487473 917577 3470513 517395 302848524 337800 253432452 552649 109555898 793336 367577297 837861 439495779 971579 831029560 733757 328119400 546997 52802073 662056 847776062 203656 53273606 832628 783594224 132239 150176239 234064 703527735 305122 80395490 981681 588817261 298518 934149356 812641 877188281 718312 738401093 98666 211941546 739772 743884756 907380 501732467 462376 717713278 193975 673158346 867037 476368550 598254 965091695 490014 961560127 983451 783369632 744998 742345966 292032 284906304 891068 747799166 463283 123974733 374310 362253863 297916 381341344 348495 65211390 95239 698973701 884231 282122157 575951 736033147 654993 317156434 904936 710216543 306175 751580947 922831 830759493 848665 83489419 80656 908816284 68254 609335413 39680 967037138 740148 47632168 425064 805491552 805825 509382956 319115 359043714 994787 443974920 337522 94274171 220442 346662632 502891 585628664 393823 778482155 150236 807100396 593189 301820625 721339 582275216 590535 9590728 105309 353550606 746618 323749441 630705 776808148 169902 64432421 122583 447884969 679688 577149856 688743 747172069 501963 151638301 831429 200051745 300270 709696045 626335 110272596 113881 232400617 726526 510323592 169864 674102619 923209 396705018 830549 329915159 810731 11525621 207359 789786152 251736 228050462 657889 329790627 695796 102464809 701398 893656945 68752 649236413 615361 546212226 637311 347610394 375369 368148943 407895 192966549 903676 275397162 615217 660548388 352481 329512020 169940 421886527 48381 472462391 381090 604023434 577142 600758659 434065 706869243 820164 419875514 414414 979603805 319861 150499291 110320 24776422 637503 544963978 708761 35170266 759980 574463815 351274 769055201 586163 320183149 307300 306857503 95158 805296208 451833 389296855 158290 800601336 535632 81197494 248242 355219336 148909 396959839 702205 995153016 620929 353369946 670485 481176388 815696 111065227 995677 834277863 441914 408445895 370194 427511070 844505 584588917 904502 385689900 805383 322822376 492995 739506866 466542 338701366 920389 680984490 170685 183316877 162425 188810533 836157 956490280 6693 998995782 365574 597615641 496919 559166222 265304 26704218 142982 914111440 554655 692497255 859634 670401184 704645 726971797 447781 524153009 328537 575529459 9927 426133497 82642 203022937 787459 431283384 234261 36754421 751620 371132337 312617 951314294 787611 897422690 295903 62029442 686894 461219350 96212 909933623 708492 375228135 49238 364221856 189131 148710528 362350 37714491 682517 400732631 199963 137104776 21360 965225433 857042 602216125 14795 340121784 567548 465255866 651005 538128050 922023 802031342 699054 220717905 911752 829499066 458076 409847946 595188 567414557 591393 28913059 248873 463877967 587819 636270604 67348 865597450 780588 902590186 997950 822254790 843313 71239970 554293 249269362 131540 39245025 606546 963636236 510127 44275907 93743 624047757 916625 885078438 669797 848143097 691929 998807586 400697 989136840 969623 308994723 967206 670503190 469591 131661855 953478 491492515 909348 333540637 88097 48217734 352563 218993335 290990 660285164 134970 583511539 444070 966444289 326524 219374294 534367 50987594 556298 401099555 886144 501699804 403450 932887082 375311 458544486 498449 537596722 192675 112990687 778591 287205055 595536 168504068 163820 754253404 136557 855423372 469966 562511779 837833 264984079 963786 57574986 44320 230551547 553841 526525401 895387 129073904 621825 57263123 633090 56880362 696194 363059235 221140 748016521 929491 812212400 848304 102775711 897721 892076505 225827 885313873 38419 720515106 150291 204121053 938625 805052529 752342 898071322 964143 234438781 625290 240540308 752947 587826424 739795 315482425 956148 846952921 392427 733231359 549221 697399074 218996 870479232 801319 358949617 943044 787707467 132503 427874702 71472 539325544 573514 29037534 737631 137812605 800820 738170249 293322 3712735 130457 800510034 567491 147504322 84307 882631780 874910 8414362 119124 765400501 943626 465247908 977683 216040780 616271 505268611 291827 264491342 380601 838552716 895472 892218803 306718 333539492 849657 215794622 566147 824522672 344585 811155965 876364 243251699 57509 401610855 878356 303284752 443983 255400734 55904 76955737 134158 311501028 812248 186858230 724919 453993664 811342 150982094 113906 799022983 469489 39372012 240165 881942171 808728 963124276 645001 160838272 613000 980647040 356841 45228519 934887 355297948 918768 591009567 319911 731337230 593400 778309747 602706 982445498 142042 358543903 991356 327740570 428653 958120171 539484 378778539 436596 852764965 930537 998150255 426579 348501182 89434 757437461 566599 560387238 386671 551370350 137041 858583159 321088 286705677 649183 33844198 406697 319086751 797028 4309424 935541 160541180 174482 772860122 209335 426471282 247713 426550674 202080 378430980 189384 788169899 951184 518342511 234365 439120427 804 726252788 363554 207591838 73671 265598022 824469 443102001 374455 274900463 853430 851001207 289244 350658248 291746 756208378 927683 348312508 148120 957991557 506106 176805505 708009 949386845 219361 443842138 213732 332991319 289700 295289673 378549 336821659 428240 596246533 667055 924695222 454192 263952502 568210 584308744 148775 822281161 42333 79621316 477873 154386844 146238 51082868 149582 937181284 982540 190049874 824384 659404355 634126 981561086 273754 169355958 604524 605387201 371621 983991663 852997 882010702 622417 622041687 628121 999552936 33225 755865930 25968 230323646 410933 348029883 266701 430088211 588908 629860162 347350 166574723 862242 446683409 27584 226176543 640001 402222584 934178 756516789 466927 593303979 125160 140828547 895786 217696550 404093 329721431 300115 342836891 819712 242382576 349023 59560342 244832 801377416 83421 620111575 364345 794178402 521967 198932937 112476 296896513 302446 237322413 540294 724620900 935763 185343296 274884 605531619 739458 366295965 626297 816814867 291153 58521499 21892 29962845 399610 946761251 599797 413683448 954982 284812360 528126 851336122 679486 780935133 143395 225027103 554835 716417414 978890 692058946 898643 437741837 854443 641747128 683434 93960231 124603 600815150 59689 370345469 344117 838699868 240825 437855108 596308 903733933 170114 668766012 698986 557266554 382142 979791920 553714 319491620 971519 342662969 614246 78848031 141692 730973493 185396 238795746 65576 209111715 147931 525001551 331792 226206747 312892 670532077 848922 268766621 951135 24279208 522617 266995554 733470 233304149 924862 807600303 609951 775791984 501971 952064009 327355 837379987 112776 788605119 531674 478470143 176939 871190540 393923 306164823 997538 987513966 391638 251189559 558465 810802639 720359 583121236 849651 868367647 261264 861053889 867576 107353529 44028 847130140 220203 708953833 991315 718692494 365734 17919226 104797 474235099 642493 739823046 923038 187016847 664725 554198700 861906 830401788 820758 815326588 904977 241613698 463746 965938669 995301 37765740 696903 883151097 549760 535371620 173559 455565955 661839 792226700 863894 160520668 63906 4287681 244944 308585876 342423 985432512 173364 502093830 356080 965721325 650880 298276401 516856 647305843 962861 728745906 504771 52246853 668714 588047900 257375 406118596 600023 670674667 739155 463700191 934770 112764405 650565 173380736 187532 694923104 153652 818057692 865506 841810513 934716 835971927 261138 293871414 849373 601167798 234071 991271308 512931 936873852 999889 103426849 710715 752923292 674750 348852042 297971 927524135 338048 559644137 918944 351294545 448240 882593664 192520 815021083 117223 170628349 712853 923704907 413559 81202668 476933 410967136 862004 292641801 346542 719655278 614694 514448004 177332 411638843 164839 159973133 173913 122198327 526671 291042775 716074 974517808 351987 667908988 845373 564199310 579600 152084189 294294 591528311 48431 315741845 405901 577384558 111513 722113503 789548 164804798 694137 65931607 790917 945575831 794402 340963508 934453 932462121 315081 648842480 957997 162829127 592519 340488336 911265 189560591 281779 3407947 490565 906822046 779337 456245728 835283 854803376 17914 835685291 360197 102783165 97084 476062134 164886 33743552 48280 135304899 46952 438796974 843115 347309848 620336 791221327 715285 845703333 207461 686793981 421033 849773127 241645 359793504 410869 596248844 149263 956151862 416833 53574745 536902 589002803 799123 661275863 735391 746707077 933176 845913127 825284 573626004 702160 24551639 288680 530966872 628504 510641782 580888 605318625 370390 551194235 867071 128166553 596362 951881989 54090 75282807 10502 144228885 639734 54141481 986329 201138714 737372 997921381 911495 404510843 16561 562775110 173150 856207679 172754 737966084 905633 919521443 32771 373518347 423428 208976401 670378 692100980 79134 151673351 169620 967502039 964353 724060905 37590 21387917 908042 207665191 995203 122027814 796474 236789266 581141 853428544 834026 374794797 950451 985016645 482387 262362526 487640 722041773 328728 260417696 140889 166368949 374147 220255434 381754 437700512 496843 909294128 10063 643944457 756879 959088583 96160 18199761 246352 123548793 512453 399481758 27701 80365777 524339 834916858 161712 734596255 493629 110910705 262301 184974835 3916 44637506 61673 537168563 756787 822125972 3367 216221462 611703 600653028 6421 278649883 797688 544866833 722024 71008910 8257 619351893 756806 422230110 732041 522968392 878616 625487924 104725 922769977 68716 886374775 614424 728319281 720990 570507015 566922 232769350 166093 575114628 87203 405163975 612435 747536144 497064 934880566 17040 259675749 758684 796916759 46003 795868682 514707 242767860 766329 809010836 602225 320672362 962946 807474172 50900 193407242 738818 66168661 642781 635233738 493699 124878132 217033 864544731 221537 708295315 301726 691432520 695111 503262333 624566 174311827 777780 584074078 200947 861408331 790098 850247386 442937 90228777 965157 747015200 763361 863136513 423800 69635939 578603 681741678 808962 405636586 360283 940898054 607218 384130307 815025 552271254 93779 505247643 815206 624768457 958365 284858084 39896 292082957 59999 322311206 382812 143521270 439593 410775342 286730 82169680 459043 974994341 265081 693984603 766212 182171316 167192 971355311 633935 775780022 165302 113340599 359423 508666532 884899 178358732 61864 648774580 994076 808823290 80605 860699177 984843 353151874 473069 530207999 396139 52333745 873058 133809736 563866 891209568 93383 595812481 969923 987522514 126304 110278979 370919 664414388 208209 539808292 518971 618149983 553960 442516801 882856 474028431 543864 202788504 418354 599688506 957770 12396867 721635 566982574 330368 886465557 816616 792261647 673445 996013625 507288 894789129 21166 809692015 364055 866391055 853385 640436893 763684 393391772 755399 356423677 626012 734304140 697058 260963336 204314 975080678 291851 469426112 70639 877431073 377404 650683522 537119 827088723 219464 246820066 156813 313506599 938265 658592249 149809 548996892 446589 101149090 929265 239896140 464361 646067244 155968 307928745 619690 86335653 892556 840713942 321399 203552737 727865 854399520 462763 189630728 972631 125211718 836612 406300041 587615 935464895 142767 468606687 425978 651891158 91181 1960794 626818 373413639 993522 499660039 840954 637894335 52320 839811975 342205 565036646 130999 431976928 525799 364143864 220855 823836580 311980 364203685 946057 384656063 778232 637402517 667510 986751582 452612 309329515 423391 720530904 912646 508880500 207231 42431879 519967 721928169 1000000 476540814 947669 393589628 875173 39876130 122557 490684064 61467 458006940 768982 673394750 857029 438742345 861413 965571675 943278 751921803 511641 168646628 536905 295621088 301023 725011737 436241 554889274 487413 508137115 679362 237659082 75386 324101096 806868 464929512 116491 770728536 531768 807354064 30929 919412935 911669 464159201 381916 268858947 258806 870544341 656861 945522780 265135 395450699 665773 514221819 476815 595231807 785752 926320692 714929 386415017 619524 228404007 740942 143118427 16182 70111324 850678 448454535 541881 588783333 222344 495705515 476426 396736582 624616 124089764 213938 176576873 133400 902911984 699013 851030877 820153 467121272 33712 211488342 385955 263245221 660287 345529042 927901 135837261 65431 793313146 593663 707807102 593080 823740000 147763 777885913 547580 247795913 22771 511708503 51757 790862039 471319 245183963 528925 137347294 80728 792051774 397373 851207697 700212 111181324 909940 386356310 142999 754106445 466753 959955907 718036 828593739 375622 902578539 52657 871476251 254211 943202213 129924 461456220 709589 629203566 325508 479435610 68830 335066529 535389 574266686 947065 208190293 276434 356741962 183375 15028297 831578 166549977 292445 913374947 521237 177858019 579904 85925629 393560 706564536 493 93064466 778081 253949888 902458 105915073 974792 591109380 235948 11279282 926431 933261497 710562 547893128 253334 381271295 895790 410859516 917770 523226838 691242 61641109 44483 737712749 22639 530903786 199549 680978966 353521 772825415 868758 824886800 810843 231513575 981525 629754479 487750 500036853 73810 156786061 886618 862928308 706367 876598773 46616 378836144 487206 623475044 261440 240331411 884938 336161814 436870 887864023 222020 981126835 137195 142835479 722906 568357470 702960 285936597 115334 600327577 624397 679879461 364994 681536734 709612 459264459 655620 731827862 950167 14699489 186980 409528487 354487 876554432 925707 465732013 65652 50423996 22083 167338460 360586 129741050 809868 41397842 926244 890675737 713339 884761836 53616 47010513 117690 274581282 455171 155884083 61837 735370659 187637 18689570 306549 673018590 161707 220391253 892581 268666062 122740 769391066 209898 499366514 351130 473092283 199255 347092235 954226 952649789 55737 388057223 352863 760932183 811087 929398448 601562 673441263 239553 677036351 467140 805536933 506756 744621083 299414 804280432 927322 216974012 387633 725097281 269776 382647532 469174 538523600 217273 918091349 571706 465471473 587911 760690858 481639 774621177 103970 754655056 984079 538281415 173957 484800240 472256 38081779 949772 604531969 75276 670515247 285056 384140391 95996 991880494 76721 508019934 805138 251879120 544781 866898052 678678 194598309 194685 799897882 669310 532685795 650069 622618604 67616 697978383 811943 357853070 291542 938820654 523856 765763013 603035 863808222 955432 398735329 7949 920819761 116671 93069166 695692 311573098 385845 94997355 428840 365827803 57683 783198979 17802 108530005 468487 33099187 418584 752943732 651192 665270198 322047 746125820 443420 810530233 977302 599952597 613758 979536823 465201 656891209 347703 348525732 521088 918418490 874078 658868750 898039 438435349 272526 593509002 533423 578227123 31456 126395079 769397 393107577 762804 165355497 692362 855918787 518450 447430521 719569 718466112 971033 472100019 763482 609483080 43879 314154566 23117 829969138 96477 297027853 535321 859918641 871869 225840427 439456 348622783 696118 492446023 888819 206519220 757781 630015201 288348 96622045 543094 186356375 565868 384769717 561273 102086351 621616 442225715 816008 85410772 656125 785675890 857734 98206040 19456 229865155 383267 854094710 410014 651904045 753440 45398067 890248 287892170 699528 197250645 3357 764458115 681315 443195351 101271 776108807 973326 233286656 538929 762148510 775782 317112829 697447 460717361 845492 492417778 272674 163554086 151434 339412377 21133 685309829 517780 909573268 465243 647131246 751920 423035267 716737 835826756 181103 938307091 977528