1 1000
817979395 100365464 603289790 714083489 865017934 89794241 927670484 718787880 23964967 38582916 935976942 456658302 707999926 743154861 195097137 429477812 814983922 591251368 735018393 33550041 746003502 265864031 85123600 245946450 322444885 631170008 29905719 750208436 648986945 133196931 93608800 319482691 233562394 696898589 33566179 98580328 786692829 813753014 669884559 810657796 852335930 458377853 267316097 560335855 201532713 314929586 842330018 16516635 906180953 429864762 902583027 504700806 695728793 840222978 750647255 18173677 471392985 780552974 620898464 120379929 913749904 714507263 292378971 147312297 411405851 178461501 98408976 50615032 992214515 768293535 861272827 844550444 79187739 128588923 257402650 280720451 296034860 99732668 149753437 54732165 382113781 904852815 559432970 77842573 745075792 162596577 948532601 68985129 943149550 421947416 41881409 709415805 136454678 334260380 709244453 400376881 512721880 660169781 450991912 357452746 280979667 312264738 54519541 360167405 293370012 311922191 640887855 589404872 264171210 643157644 644137036 646284990 548010458 56086357 576643915 145602602 218682933 377692867 67104082 14348834 799640283 108985490 723764638 788611312 295762221 285525443 188988192 808484101 945695223 639980103 18453198 79191241 804761192 72972739 439358645 98131204 384894929 80246499 540052427 501582490 575920494 36705814 383831 123930952 92792170 577027745 122049905 311475103 807236964 189153986 325823936 459393598 150655827 902104926 248004909 446418048 40146720 289509453 107418500 985841942 929489555 125871697 65033182 586767099 198844435 356908178 537414654 583739363 289671028 77467080 85321852 865591522 966689245 85705683 842038825 59481414 515249779 964088729 223472868 175003094 5759066 401813156 634396691 156414892 303918081 882401600 602832939 344064800 24427404 710251438 182423093 953916958 836123135 99972626 393200408 34967569 456880803 930615061 471223284 746551830 860598492 409061487 464659703 827287736 347283521 306698527 739285502 715049652 123303607 815274721 890052745 129062672 217087876 524449436 137993916 373522308 259367387 593343206 717587107 283794790 156110996 752526551 90228099 992234130 852499176 483428507 879718050 161896330 266559919 203457685 760964512 127158411 465035524 225624214 806962498 812319044 384839093 398764351 379885047 508142699 214039072 269937792 489721723 283643299 646903579 480231990 657165607 906270965 73575195 227269065 42582106 229686190 979795616 132810204 74436671 684811143 468755062 806671073 846707473 735314981 10128757 460188336 714989743 327680632 685812549 521952240 139999676 70651641 920716591 372401074 431310692 987272014 642338865 773548766 270915312 141758795 253780755 928080918 48029759 179872301 7866335 943128216 409558491 987661950 928454772 336511513 672473092 249726185 143182585 371696916 985041165 5827694 831885251 552547259 333508325 370214152 74499499 326024352 293382144 847732441 698425426 577209187 687520806 193280642 350757952 958436117 335039437 457055058 739033387 235585547 636927359 746899721 31230115 46485849 587078022 959684886 235513713 112067465 209411070 378696298 483764381 46968587 237040343 168165983 599515845 570548667 390896486 526531695 749089371 684278630 226780487 300031148 114004168 914301292 493311789 464762120 725253761 680867577 921817177 316803499 916453124 411260887 916219571 947683238 310263087 503297592 759884475 545776800 615365056 969295544 924473097 951645788 868780482 14029791 119811771 320812679 584578457 363224608 847344373 186184179 47503237 926641212 486215326 14023757 693458855 979527115 478785876 271228967 512911043 253119404 588032465 281880518 664380291 356768387 82080107 974643377 860065978 841964581 372936528 327947386 663776477 149925976 132109525 532556958 163955766 104437647 853369636 748534223 467662255 553230361 934718401 367681843 332387924 273450079 381705599 25846778 105493545 860491474 297075745 618404587 966127230 737624561 900285105 483023872 94392948 982365211 310183600 806975277 824329792 683120128 134922662 340622620 833046103 119548539 873179577 997001869 223986185 579065565 598052443 691648439 984812277 385287195 59330282 317200200 658737273 441035880 195563329 764230817 154043706 492639073 382635404 120170935 82779986 135436860 455711158 177172933 117802070 765894757 984148209 794648213 449014884 971587223 135270832 134577339 91135761 860966761 131579207 167638297 292548677 729631649 859286736 277360953 114918843 918617017 447077504 626172468 212169248 642640832 390403284 218729305 135279905 625555039 191416591 70576242 760991898 647127748 247749174 878793968 413022505 84413734 525958532 714553740 908517308 661229364 849131078 852169420 374712476 980710284 19807717 667261152 562858284 879094452 944622104 530293479 650227820 244215959 8982298 714913419 886856790 399385581 933642724 874653046 24940620 125059314 945229287 638448869 772187062 45494812 369759188 37725918 129908546 895717720 752279657 38425853 409463435 453927087 743111625 784175910 287153722 762919341 451437061 850012006 494530144 248575516 232821836 997274315 492791474 241804133 712187733 232164615 493706065 498346808 106817661 371163036 623406122 52046947 9611905 248109535 97541759 379371092 138351804 79966656 127605163 890631460 970908860 537068597 197074898 714020484 321244506 484228620 329456176 625197918 186756977 676502671 873773433 419578812 673776985 219081258 513899296 238481070 451245873 7605360 736827877 410579885 378768396 212750350 315143183 240896652 313376236 265201293 620267743 451728039 345167948 747872906 194875851 168593160 137457854 391950748 882613643 458702360 876179367 64586171 83900277 62936343 741088841 810190062 335031506 267382178 881787671 848930801 358379599 185549895 856536161 95207475 596129779 87820908 160474177 911272962 328717559 473850412 176474254 801501653 925578451 374158554 401890910 120454301 542751713 539348764 364921400 277881707 998051123 241100767 342467877 934467751 156553461 936073070 597174164 491584967 55971599 331478187 340515767 414351197 517028081 49568279 362075023 113157860 137389186 522549199 24430821 318623096 848915963 53421426 120124749 627010765 427579979 374532010 599981417 970331691 913880773 964902816 100729750 764448247 58519934 443197626 551432350 215073395 231787047 1122865 706658361 287758645 332601051 47174127 702109841 849629132 949258758 64184864 962786991 939164295 439250414 839734163 110303743 288166376 745671940 82944843 915177140 25768271 457476852 367674908 996099961 371357625 332577724 96829710 135805871 391097657 392543688 539754572 606171051 624330734 540877437 165345763 912089379 873478487 65036242 466715571 723107618 14294999 530900434 538410960 953459293 970150848 230661474 63763035 110833575 976333414 146707877 878527067 2101684 456701081 246201974 850717996 828058705 431296049 800064058 816380927 822393706 45124097 208651851 281081108 521971182 749529287 446426871 286576912 623007773 511463112 753292483 198631743 378274462 136709268 589559054 184250106 106860115 820220528 100529493 70210042 649070293 99753721 948737108 503688328 556454801 47455433 206922675 237029857 478751482 859503084 53410784 153661539 904627180 114578986 287258998 279114714 864108272 733685868 565691625 339632396 97665331 318984107 538264138 475939792 455693375 127823192 660189898 415069841 800560071 760719390 337796234 302146715 860473110 139049693 658351394 269444263 186505126 865274068 506474119 517772959 577293504 412401254 671434497 334437035 526980239 958693494 613551748 391088510 544895714 179243373 730720906 495077396 350743831 121501395 971017188 806437205 101840938 483723437 74023398 754917360 96959178 411819631 57064074 809948639 550869324 567931819 79392901 589890801 285722239 585867020 107663759 863015742 998268273 631614607 197452776 377764864 442824452 811004524 768853373 987720165 842764248 352090630 335313913 193508078 326108377 158847452 852461635 427949314 642570888 926485032 35383026 592046417 190821014 92447099 401995055 594206689 512895270 333904308 184097489 798617508 919771327 144277599 661633249 770555951 775892205 711602376 837166 218716657 375123251 769690539 58953173 217887498 974297520 394267085 263911928 300405896 553114536 116373562 580871562 48201775 895374945 616254587 640248191 86195958 561218037 894759598 532918999 74113306 228663905 717016487 872730813 951583 861294086 386880413 624023885 489702642 98482789 624861051 708419298 326122391 247067941 619888823 544009889 221365460 14155907 807921816 374287708 419786795 776811729 955159269 320504921 672186673 571413855 960753112 610898982 132631891 708029061 143817980 59261549 936692965 713350819 784508713 790160899 427161256 23905478 414184783 916863897 122388266 39045833 477799547 301027008 138630125 97688369 845036896 359995585 964360627 505475063 734283292 236663773 134803143 541958912 557168694 806989815 113372766 370438157 270405149 98521008 78467217 266739480 10298908 867676533 832606650 794807621 510353783 112284257 818713098 924538565 29148154 793617715 816100750 359464052 94644722 954730874 309668772 792197970 167242810 126545750 150189384 754042453 215725875 284992527 296001364 772894568 944498693 261890481 995849076 67420193 212927841 926832644 334159673 75743100 647025528 19282674 870550720 157379310 131566931 541780169 934434226 13231436 187914235 603051327 372695487 135075309 410298553 534880610 779789630 577541362 661426359 929979013 184100167 877152233 67487891 480101530 502563152 11986584 594508363 350928579 79406776 807436203 277761222 266082800 883179302 924786749 285365474 606246374 934682410 416932404 542894 869116636 430163839 40973481 324684314 655375677 176048789 734982866 190256286 955838418 165040580 704198996 738333782 349140746 433867581 658338025 829242275 936430732 522840960 276266989 139875663 454764087 83703191 417636884 720846887 819398845 194939985 858728712 278161570
