1000 497234818
877827424 54406462 797737485 846479797 570147956 935697495 902403735 60243779 548622888 813861541 9486825 806159672 809284065 738554844 853841352 122740916 453781584 164374792 198409405 859358800 813605987 75990306 95054862 487585057 94395135 384416133 176452660 513899624 354965767 567982547 281609742 542770279 162827135 581168592 313990601 480842805 431293989 928817878 982547422 595943735 830058138 884372471 491546613 227197455 845752065 133625795 936933275 792982438 873237964 912911110 550138961 618240131 267170765 613874748 118802263 840840802 525899005 608644658 869412610 748055793 434039404 357485925 247176337 725108203 165651430 545940491 300996631 91805229 9091733 428048436 359175279 534383896 366580718 96112295 217811845 6236462 612149630 119730792 260120172 161918041 782530262 709004411 242793057 162415940 80234108 376029317 314146028 898506458 178137297 128078679 154646925 301404685 342253236 552316240 810066676 792759881 101343883 433726037 827276337 432500878 58483365 241480647 257765574 818302874 92688149 612613940 184593293 792426674 291267431 669827692 984906057 881528478 731644352 352445337 235140819 161864086 952107691 696096424 941795722 134046765 438745972 774634720 291834084 340295571 813899966 75451005 370558942 996377061 628074756 728247325 405163794 134854609 273557548 600392945 750484518 662240546 166555707 116255661 659882366 644119406 90605963 897801529 932247017 267476458 264897230 774589735 294462329 731165510 875450294 838488536 147389674 626882082 69990032 673613157 424081689 359970006 89170278 724920132 126515256 516999844 880537330 626598229 439050226 885983229 157468237 31424062 901599424 320781216 17049108 977538469 49172898 826083397 164753842 913222456 800923519 798970908 744785779 776952692 671961748 473611656 975089628 393169991 960816781 69772131 213281028 85124288 527075887 158864150 750297765 557861910 585791284 890356139 948541138 891111453 60505423 828925061 268727992 378163580 949677119 702894486 473739462 363585676 702588601 559093590 67958261 123778950 297333898 748384028 343110889 990207133 256699928 715728800 206543353 611834460 818334618 141438412 757134758 374913385 160824168 813366404 657035629 140482702 112908982 617219075 176470241 145066683 173994486 56287372 578257151 981627049 16175433 761338995 622406598 434718902 715701727 328189744 683133471 29979270 49717629 9218005 486706608 804523388 565943061 801035517 84778934 371134513 300202732 728678223 205173139 858405364 998306276 492438046 938113074 830833646 805775798 70490387 441007171 601557454 737158829 237209201 605074068 370179105 670094848 685788708 776809284 24179949 602477875 959324040 706721767 979268633 972746878 596654028 260430399 85071217 671310506 819471016 50137793 575224220 255088882 56245371 613058655 83579871 738576514 735468004 902551395 254820746 756961188 546764680 548697149 260763368 423774601 942477360 261886056 200555856 608182451 291026369 262143506 330845060 47834550 511126678 766076370 684873698 675734119 703316267 576270502 290891515 132785937 74163210 24032653 951135023 190363010 564882737 495909360 960172920 123581132 431686196 910001714 478768895 512813217 522443906 280783333 449840165 423814407 118683582 787688769 74990502 61146300 111922918 487487568 94442063 615279313 64115285 708280442 637018038 633831816 51599107 220707594 920642679 35182816 97700072 391042122 686752722 166308635 404312851 780047448 972329133 352352503 108351259 181555989 843634907 974716701 762116976 415692597 728231606 575105779 534513929 548565167 82976740 568309633 692001031 517784666 633779733 277159019 68263119 882533226 273788763 391263206 466400571 179664966 995003400 769365207 281224257 572598206 470409910 889253053 993930741 218277739 433478787 470140987 498280201 140177543 950202737 421020756 154829838 221167779 200420250 421485151 809345126 711328544 690564109 245294350 168007253 190122173 79584493 302612007 189284107 752820380 105397837 804436394 868966047 755238272 277525667 671594756 43402818 195178316 976787533 540496945 433058294 434548265 652407997 816782615 974012947 799345612 50822355 487295649 561426570 559473521 34793095 757980137 384439873 499361432 954580379 727549789 220315488 426316523 369709694 922310397 97571721 480658916 252903434 860833483 301944192 426759854 824076639 32193581 232912929 231449483 27255011 279484852 463414931 771966642 947854511 128745883 146054870 264591082 47840508 21457404 8103082 138617485 773878376 98813920 916130571 924984128 991676235 239885931 790181087 735000686 81594364 294300428 717348428 185484430 120416184 785115121 323082153 259980780 878559750 52327376 625389484 648862171 474470228 420779616 22928587 891722055 427551952 267410603 932286966 800494021 429458918 214952671 107047240 484038110 139945889 334517392 261653080 266218983 106148590 617908336 527477597 796765456 410746075 179726613 181255395 685825956 613063952 90479852 213974160 651460828 882256516 755672089 358880011 919057778 187410576 627249246 235796531 178485459 165681635 581637212 373519621 84914750 439228972 424720348 956634827 124689474 759534708 712629830 765958921 497457737 161388074 665991179 185569058 939991116 71539872 909246248 614330582 863022192 10642000 204392644 344549095 940735213 134595664 143507426 976617315 225121838 93236729 661624663 776713705 21876258 904124580 306069075 940058182 451356607 386722798 494202863 936519054 434590637 94491363 229707396 154323468 846273385 757629943 373979747 226318843 729753482 411784382 688586906 777919952 768585822 646183776 369797896 845192238 175019576 382371307 853104683 443616636 350140461 874288162 728242293 264957498 791955952 251530036 864152 837843204 256986564 106219401 316286299 664771864 463489341 372241450 616810340 165253412 270578411 762414791 388755794 112382961 739575137 909702852 138514622 123013853 237846759 335787721 993581638 345342585 612918676 545805148 428004633 189021647 546886879 484487654 236444925 410620003 342438380 61988544 953999345 53125767 641308428 473023664 624745854 13717377 113125357 247943175 51487895 110919955 956437199 969309431 584186551 236846950 474045468 879589751 436451228 917217657 676136730 189783299 306260493 876301490 946719348 441740431 593710002 429241725 70463407 785577423 563618295 676425268 646941114 642505917 654065020 41483551 21026764 384683536 581105329 451271721 47903790 557478312 180595965 399056295 381789414 920807521 233816135 437450727 562159980 204553846 734608099 27787868 364200179 527075778 83890424 320870003 220747093 111290214 870304228 201672324 854324719 402633107 826791280 941374513 947945699 750518418 19003614 415722990 707103329 755634043 379756429 179146989 810071782 390142653 626824353 454502467 381267359 207019764 622530873 377784263 925076605 90704975 522611548 409514637 800164843 150073394 109163374 325402648 171681881 907112453 752285797 637953016 276453060 150688866 131736892 873051315 537347347 491531213 376553949 841019638 786291185 729466109 572817424 656925778 964332297 80786562 222698485 220815181 103355284 266032029 627022604 491898572 308154840 242638417 68857428 351621988 340374114 63029095 930106285 299851079 747774921 747121953 759165766 459854420 646327055 74866951 83564277 110079238 502869239 781348833 946506502 188566253 266059892 541557596 742911644 596963041 477973349 282237977 980315063 692263709 548044910 865800241 107388520 350214332 975155365 465852427 200050246 261157068 78753144 903052062 792239148 168170083 868255569 86132861 371112673 96692416 754919634 228307647 590367976 829918287 176488368 741870752 84596218 347187152 506514676 554744710 353558131 343794646 155380120 872817262 544422416 669835423 685554407 130039692 140836225 704766394 829413597 635545750 767690428 501079575 596034556 240278996 866256690 115366212 997350615 765228672 171785120 638984847 581931763 26224482 300469393 843299659 76921747 473406820 735095308 318903304 737470926 658008945 757953880 787382849 262222632 260246847 367375656 128098801 389741697 36490 956308787 236208558 397043197 523183340 582770498 989193186 871926440 36887521 349089420 923558682 388894155 104698471 480252391 41104581 595731315 6667985 271192745 731859641 818669242 157772249 64795574 1410307 229932930 133833769 253772925 380826361 61784716 778937959 867650487 85911730 113090885 781534789 270919974 570302098 603302557 242453911 64848218 894538837 16003982 408007410 303700030 800411143 16692030 850924081 203627780 520328420 525576739 548557457 568407933 547624135 126737086 242493290 67081496 613182743 972762688 568647413 955040878 276272416 718521415 81978125 22750342 882088481 865480962 981828189 702678727 163511040 649394283 161007362 652337385 503848044 503874749 617846118 76716816 951472134 521380978 401240772 234354212 14721622 77992220 235562885 401075378 190519333 423680742 217467808 7524744 194979863 650558304 361052556 243001359 491232619 475495040 322668770 125006515 554679420 949594344 938432340 897016372 176195789 574602520 42291829 652035608 496477294 9926543 665925265 763270964 139267419 119818645 949148559 291641049 438067914 167485092 846776000 851481000 704130591 408548055 306924395 822747044 820501795 569447807 731197676 106579036 671887313 98530082 443153936 431348270 508343910 313308974 153723011 25295839 206132397 61992956 818285810 407392551 493701193 102428033 300149963 674673396 151854238 287759705 424610644 153972038 42996547 611991874 297421838 299592572 431032323 156844296 949469797 274328709 626298493 813960545 961557692 204178229 75163531 80920103 199664587 861333813 96565282 580274498 62726354 180253555 795901377 89026189 801050336 152916616 4292093 70730724 808949493 441981168 314843590 720296510 516243914 343991097 439663128 51344202 103197634 196817989 309435689 541167173 345148973 192262162 737158964 643308687 141324351 847483038 208563311 975832383 707745980 363831950 762553870 454641182 266575383 928178032 476189325