1000 146897931
328236701 730009358 290051683 922182370 447236384 520004157 970199992 337802792 622113961 328600871 813178637 844201454 896643646 502663490 381805791 441626878 51727875 833405982 890610100 160945143 90924039 140143373 245383708 215973765 626297884 602645690 92409826 77396513 677136806 272337457 296487270 791461196 362199346 939147243 405199665 864940665 830873082 641663672 189212944 219337593 114735272 277366880 533113793 515083647 1028254 253596945 210687889 425681583 464902372 205198496 983498783 766655000 916859378 767998745 290241023 173001340 749886001 89817954 161529314 77919037 811576237 609681118 253459222 762789808 368723155 5606462 738339709 140275684 170336517 783461572 37712568 763199051 169535901 288311764 446624820 671681291 17238372 516017247 19617178 474905090 775698294 830399632 262670846 844739911 950280912 513265791 695511807 393215089 51945354 192395733 905940451 474351237 547376781 662117785 23854154 109834435 878089410 321180620 163338237 68395851 255115746 486557891 896977440 408625054 197036638 358841957 371094179 666308669 919621490 36505974 795518604 422241842 778128957 70127298 610654129 378410459 137690669 224921252 509566196 112184148 956769538 708120325 798938638 46619805 777770220 317605089 134930745 485852790 138150232 169911895 268547189 277482822 829742107 556007030 32617874 72294866 730971247 261922648 555711994 770342211 922937738 975999290 561387356 184391209 152484520 29196379 969717780 379215383 579504385 768439913 123184054 68353971 151476957 261993738 41629822 253671023 933246564 800076416 130579470 741433514 217476769 379932631 146200074 661472519 24274800 290658702 31712259 501686637 896929822 948742194 61547328 313855505 557707595 30009944 736006445 574158343 185992856 205109908 338233554 97081678 556619037 967510883 404661570 252082194 797984271 107263925 71830847 626137685 350734108 936919989 375969473 735114452 238332831 463603608 614283775 686495223 961455952 421156924 638270753 373447091 977945262 988346426 44355350 916808328 43835127 576458614 725134958 762574093 247033068 345936866 467904613 337670819 359228657 270720480 203054019 342863890 50962135 999622663 595084120 279022476 809844797 171238371 480958203 210600359 76331932 517060645 199082690 697846550 936574429 109425233 476026170 233022040 33315143 554292293 505063576 323591154 265785933 962423557 405667284 279446059 942750092 49335826 718624747 11824532 783718704 661247863 648596530 915751919 164138485 414364517 242332091 551383987 694829209 515055400 81666262 156422511 763596034 503807081 82863421 201364914 203958677 742690203 790456694 508426696 400342831 140098174 104231019 504300913 138168038 31631479 605411842 62942303 397628873 649734553 695696926 841882873 141980720 507277317 785933988 863491975 934570585 121592799 843396503 215562679 96518209 626180608 805518338 731790591 552303431 891917494 709424370 594095456 397247323 216443163 142612859 376012296 735666285 487900927 242684028 649370649 910136727 174203528 989402624 284634444 76740774 845074050 936526362 175991409 170400711 723057334 63231083 54340385 268606264 733144170 34675466 64250976 112354281 813149982 714294493 80537572 673309787 497089715 108115155 75887694 744637303 839249612 153199547 711175006 473580613 262376399 599835039 252718327 697134080 251789696 795638957 221573015 48116989 902176829 419434840 46478954 373523931 629920643 712277429 825468716 510484882 759164573 858517556 681596130 804296984 557026192 709633150 325183839 69781592 218297385 872471911 240369003 138566471 310479229 406204190 303787809 583719526 649056122 885901972 182796421 264820339 387364087 60797303 89516506 156938962 99665167 139214235 433123241 896429705 99828297 614290732 404768417 557273461 257576135 959250699 464662435 922397820 927688879 381796763 533339993 850768901 206715832 685800505 851964962 225328195 173659276 449223052 526769377 407074066 499030346 849337970 782199070 13842641 678982968 603733357 261407510 226881795 7241049 291024395 692389102 810264047 46153193 582235839 548010062 34791230 815444889 849875571 254629170 405851869 736163920 706610662 666606833 303484492 840701548 26621645 147487804 540109804 112084776 95629482 173831654 752155067 286081381 858301122 71311413 775949590 642994270 508755487 840828411 651636958 866747077 842785351 88882399 655784628 971058840 108545703 288347895 559713514 89111965 375340841 858200008 717986631 963181731 556174100 115403622 152410695 392300747 590401177 915868424 417748993 208320929 803286851 119048956 912695711 885060601 759754319 70641662 222614140 127069066 372110841 205801025 312175189 91325472 465094239 421543457 21454960 750535439 888169298 305850791 506632241 502014571 19093575 636451676 487839112 174764580 755812929 278882269 105095420 30007385 16311882 902070271 819267075 244234616 128187346 136120961 127241460 166985257 466524970 653432070 62216544 73794719 792659755 68192034 92814899 447628047 22646785 984162884 678153563 87380373 954884041 524907749 340888266 366459221 871509194 544756771 480461154 780113430 901456627 807802838 702503389 573980547 348061499 362499757 622679867 565208606 66393915 133134668 164428973 221648381 98181545 236067951 182557027 128605214 237641709 910655527 12533724 77305778 403395609 477645448 197610917 179746169 936225409 699915323 280161718 143296996 262807139 635201258 818060314 663795280 783826744 113520493 378639736 96226524 941317993 752751998 400725921 216379254 252656896 623466407 226235595 879441029 507214113 740144195 616578358 879584262 361075225 852257505 39276373 737168091 465448935 885798668 294479364 83487092 523576328 481001009 595180156 987035499 695931361 947511297 988469277 283613504 628207707 506862454 124329751 729015929 356219738 295399286 966137329 987190903 306517608 127425352 917336351 188889663 851867336 719889736 91048863 313020269 638415749 995834211 455177241 270773399 567920325 755885763 784947261 841306985 898023584 147762630 93738118 68617565 604886561 472370098 143587600 42749910 831626666 645183784 687400565 628280550 571483038 587393145 87658585 990650956 217345856 377393320 523152615 642777780 145625406 587847425 161533821 442993760 998768455 376816017 497902106 117039392 784296562 8396300 184345037 667136801 815954384 81318743 204532995 82175288 600318128 444087257 505368111 305942017 833739047 41663997 783965332 876593983 778345577 62875002 995840242 679876375 167432783 58258944 51102806 89788588 84996066 856279835 185417217 141904969 686380950 476198771 199799422 511764624 820877619 898169319 968958189 473565192 365391196 666549538 248205024 512626784 231038153 869025940 655088302 654115058 336133566 356478452 219498082 217747431 851223499 465724995 57846146 452580923 104192841 293432825 391127491 607867765 151079760 748107839 163957634 574881249 242669260 532800919 392192577 444491997 372346960 634186876 993336610 298085220 831068750 24566597 530277870 384420983 606354378 15521893 171753121 949707857 945028984 929452158 861409597 867309955 39556094 343719050 849941109 209244399 176170974 93643116 862582056 56784494 563188935 442624123 58833837 198706732 556132234 924154768 363942188 728777582 837684826 176449500 223923200 841229702 141370141 896440669 207990690 198148368 121532324 845824478 310818041 297804655 581257836 60826463 219914830 505550463 554430266 224491847 277470037 821843873 663515102 298415600 559405619 198092449 439171214 137734126 996108246 19892053 390747284 900424517 866775607 630176701 163527258 268210436 944262510 459682748 166606892 949737038 807221240 637368282 695606233 384634525 674565587 589961151 435762007 673158014 377012830 141506908 452781474 544847910 161064379 564507937 530562684 970010143 898232785 824291777 681605332 853453165 236384315 591424409 120990741 635824492 128994529 171729258 583148733 370309776 425422401 259193941 705694022 189780415 312231543 9429192 167508445 736714176 771630812 393241383 78664373 147493047 153940761 831905829 614668875 865277036 273261253 495926973 82944259 549919673 357751873 708939098 391318379 29787730 433262632 243213456 308695791 870636920 967854205 790146182 172899828 242665760 674289375 371746060 20935487 913913269 961957745 140688975 278176847 832660635 880725311 778902466 723791920 855087266 590944523 219492092 147089909 853252730 9998905 277926961 451353680 499401929 862119829 568617559 228016346 903353683 927871222 725734891 638921972 582598456 940121971 828763550 51678058 418743176 126273023 981914114 962375029 553571275 649175962 920068715 979262310 83376561 620487990 17245645 789120997 238703562 696792015 69308549 275547504 845400319 53275708 288715327 883880977 527667764 365977475 540670110 867100583 817450865 564103962 921635143 772375894 663929271 285949463 884413001 646312072 195233837 746548421 555935784 270678002 54283090 24567546 57229654 368853000 253605387 749724689 725376858 898556900 342045999 25180836 235425534 162381667 2224157 394814460 959734779 485014470 165599852 247454636 633489311 501570548 896615081 496153241 870383554 881332830 678062625 108184925 544012407 889320818 104536000 612291396 43325753 106711408 98196360 985771508 984276184 213975468 580889818 81137774 931253509 904917413 336431615 870428732 363320889 114150918 222107336 590410789 161420752 90707596 885219601 118133981 41307143 991638703 163570174 728521565 285774278 102889112 305064856 270847873 563378734 71121566 79090436 289892080 489515089 286887619 747014957 354513813 812020717 270018697 135909935 322241571 655404362 745214369 624742206 810951435 836104122 436665164 408556836 872007332 992354945 974279650 87473566 299068550 60893045 314912921 119259836 809780275 2542908 583574112 151468952 490084416 68569871 455230858 403249433 817702187 561162730 855401501 99840296 109344970 629019931 345068258 112102502 280544623 847560297 367479268 536571287 421722268 918631644 603922318 978892039 773061657 676145386 566893278 531404005