1000
275456729 835125694 888250892 -553028181 390651586 86700432 995480425 831201132 813821838 285535238 -540554620 -752794276 -261445642 -173861276 454299088 -131103600 -780751518 34535864 -373456174 168974372 663597176 -204966949 697756835 -631744235 719972862 137261855 265200238 -130360619 391541196 -558357748 984073930 -476770963 764001709 -672965057 -220092069 661970061 901814868 964723772 -683640319 -402270772 -391317476 -488375916 309034715 -626445285 155891761 -908660431 355788213 959892471 681914761 -970589948 -645124169 -35848579 776458359 -602328191 -323928709 147610156 144759601 759950041 472980329 809861352 -112806799 -137596770 -92940728 -764606455 -954076254 -134128374 -712247492 29461359 -769523346 486813417 778192155 -875239201 -579834605 975543608 344138183 -828913636 241951665 496940816 804859633 421295693 -766247647 492493711 -319196282 -916373741 495278025 -362269879 939009940 -435785934 649227097 124149980 939404109 -777251293 788686885 -916529527 -694391003 -336079804 769045431 -611645798 -844231314 -270279088 -419381101 -892629418 -285979212 -861450520 -165580561 -254267318 -287700390 922176576 -24779897 771257866 -561363879 -559789530 -444399392 -318567250 -775921306 145924498 932768477 270493699 807914665 -556723091 450049096 -999261422 518790672 239904313 330515724 97045257 806163314 696158751 -720616344 869526193 321647706 400894441 -417393385 62395985 -871964222 95669232 148139768 357466466 -349127465 407508826 448339523 266341001 843000415 -683205631 -767225737 669101557 -657411629 36997278 -816549691 160698733 -346933157 -480402948 384657529 207247329 -676516659 666889815 -826910299 956370094 746639816 -112953153 -462465216 -843602405 816905995 -298514124 800297269 749281153 34189468 677182638 896315030 -306981481 500350943 475920910 -313952738 207132173 -236528212 775209450 306546657 380715350 -801682301 96935352 -850592845 940353168 163303917 -182979795 334445539 -934895959 527945799 386061849 -128213862 -959962196 -342523345 -288819997 -301579713 750636400 314196393 670664943 919596286 -853986600 937680996 58095715 649884144 716725975 637489378 399703321 890672801 260114912 -715588221 -285205245 575539349 68390469 -969676703 467316754 -860181502 -172896483 142313051 -934745911 -302513310 56776676 -878672734 -232393605 -507935721 -751492310 258698689 782148755 -323593964 840861598 22952840 -772448551 626032130 467853433 934689546 -381853848 528846047 570382377 -791162753 569070826 420505061 795311081 210525962 834689060 231628312 15851615 192963245 241686691 -850449025 314865714 -639555726 864867833 722256328 -25882275 143274775 99093902 968135086 -302664088 355576440 403072765 -653636489 781095364 -917871434 -698462861 480395455 -510996684 259929011 310000409 -468796052 -116404321 276840420 -869682585 -502676170 -107467005 506276629 -690580864 218224654 -961398627 27915308 652102912 -243338207 -328012037 -485692863 -915451749 535180465 297296721 245035941 -936565277 2566226 -789735283 633604520 70888214 667900360 -652121886 877196942 -390353202 -248861869 -517387716 161260197 982943190 -914830363 -587975096 -95131598 -991056942 -119195529 896544088 306089461 -282174806 296469586 481785353 192620168 3487140 -709638793 -437001420 -687669032 723772233 637846450 -11102047 70964731 -552281870 223550360 910799626 321570380 -554543291 786644244 -861517932 401459535 88037941 452814912 -855653708 -148271323 866765734 226267571 -381452044 887318701 37477043 -105938635 -536172885 516322311 -536856120 -714534654 -748579411 -314526759 -536541648 564057454 518034743 543206101 -785861858 304963124 -772300146 -44249648 680446976 -178360093 -346187924 597924963 -354098090 430932585 -902805484 661765155 -922092839 -560726156 418359156 -727570874 876919341 607431820 -567784299 494950850 -745001911 -743797561 -95197281 -339722689 -763587768 -739048130 -660759563 123347219 578308681 217068572 -31818800 -806690461 570327834 -106250936 -233849625 525111104 -473831543 177722817 -62224767 912396635 -840760117 -621040437 962422964 538592462 -53256601 -882615869 62952626 525371795 -552651622 -972235939 332745475 -654141546 -714754704 15844542 -861403668 -8085591 652541236 -47824272 455545510 -705954912 185982262 -985551227 571655779 426260731 -150768440 257739621 -539518414 -220605365 -949232754 20523105 -843470850 923194488 877476752 -534793676 -571191669 907315312 -257910003 -822565384 375703748 434968126 -461884759 238076004 980113314 56193636 -269697235 -389209642 177460591 -341557913 398841025 979209582 946667977 125008622 893956515 -659383268 -217938517 -209592975 632302957 645060224 -190872516 237030700 -240645475 159844535 -319741336 512087233 551006800 67912233 906202875 366021140 659708060 895676847 898086673 -606687346 616775547 -432639538 -309303723 513800269 -480017164 296936096 -726052130 -758149693 -500306493 -318904763 726230408 -897554274 710708612 558459828 -159798879 795608190 970017213 -131669832 -183050360 850853604 -893990212 -332306127 -963881098 -389638709 -937566677 -936229575 -300726137 -756191913 152438428 -463450492 -174567065 -896568849 -987665419 775650064 -585682218 -233571717 316963565 -556836158 -591506720 -569386310 36759998 867886608 639855661 -490684411 -98287036 895713028 -836191570 -234937360 242025828 727405155 280309405 811655812 -821704070 658708573 857572283 -172412706 -847013509 -287100133 -361132786 -816056401 466972281 131540767 500552674 360016069 -693735411 -976724583 -879485805 -646339492 922930869 -464473050 25860926 -181457473 -407602257 -863287391 -666505561 282363141 530136943 511940395 -443340956 -930470612 793706080 366784624 462406920 -733320539 -789564723 -58454908 982088311 -685730560 -579191403 -915752814 525295973 -537676775 963055392 -820360409 792269562 708013706 311544827 -977993487 991922517 -647742687 141047819 945700340 -31858365 440056094 346741886 -70850857 -655483328 411613238 -810821588 34215652 -219339970 900890581 92505567 -891247477 34754423 251949812 843317785 600741232 -978975351 516321343 -703703398 -433920966 -462499719 244966964 463151479 -139268456 59694523 -236594635 12382238 820605371 -454025240 -358605217 -113962642 -70185634 323538721 378299738 211778338 263753124 348184623 11486020 284754987 -619043182 -751441914 991448931 -636562085 959482236 -976239337 -689901461 -264029709 437954146 -372575193 -922940253 801783326 84750657 -484429480 -651051180 224458323 -428619930 426174547 313956314 -808735735 -618435708 -958701145 -570380222 394790530 -863453920 -660291432 -856931741 -207334074 401823164 372072486 -335018252 889628587 387413753 -50812339 336403605 741184757 -365027886 -892447275 653261420 -610748632 -178385875 -439448099 446131739 -173039287 -677705052 607935349 -40432843 323129879 591949646 -56479136 586712489 -912118754 -158686823 106954408 552301561 -694350959 711554047 465233299 -705803697 -950502481 720564817 -861469987 254042760 -920212875 -515649270 -979676316 -968795509 -335730490 -268347945 403853198 240948738 621830947 872737107 -750838340 597900033 591059431 -512643851 502583831 950023043 7209539 -936060539 959837640 621122958 -604813648 175318656 436074584 -750097467 -635114616 -133194547 -294770016 -45314442 -575909628 -443573927 850868983 -886303001 27548709 -147072192 -957074945 695558664 -149690520 -573005182 -200361059 -856415762 -672825946 84063255 -830124591 189679022 -77690811 553737267 -14745457 -545772653 846508069 167758802 -898129497 360834770 -806954540 -683957663 -257932187 384698653 682441956 266655611 486241502 -795010121 344261985 325569335 -746120900 180007078 -819043552 965777293 557058589 -357381726 707863132 637785622 -175235203 -87446395 -837605581 -863288286 -591957923 364443627 -321816900 348670336 -396069079 -765510651 -312908646 88153737 584639631 -139558161 611628270 155226760 -945807257 89379392 861156790 -821292097 119948674 680094202 318409469 -772770884 -648234954 383501112 476524844 89825019 -327492838 -412016535 -956254169 517137401 -50054089 -335590278 871324915 -669607521 768544697 134841179 -566492337 39197154 -539137867 -8961623 317343544 348089393 -979174647 -998960691 -879427946 -656513822 -118026052 521228622 -205738940 -146865567 641341469 -526569333 -809851527 289889173 -273417397 -765017348 -507841785 -816863850 -498987199 886260969 666113347 -237519670 -817041215 418562289 -858872674 519823857 -945997639 -489774648 53032944 -259185155 -231212075 575848884 784686333 837813606 163861481 -984124783 -535962286 348335203 289604489 -939818931 -180304708 147194367 79502927 -127580339 966249310 477570108 746106659 -977052202 194824597 341346736 -897902882 610455598 658649930 154593895 -120616338 13566772 584868047 -425474425 73020639 196435628 -952745497 153968420 -240926577 661423256 -792855491 972445415 -48184911 -451632216 -515719290 -877959648 172144087 -704174387 -966348125 532441940 -47102178 515350359 -229717150 996099343 569229240 -797820495 -58115622 292899896 -356536335 671457641 255445932 -392998403 -489804196 -807868503 -274031176 -403553696 86149826 688179450 582273071 -320179553 -682766642 119835613 12078238 -494840815 812030851 -915193942 -710801277 -548317975 -407064411 684308198 926675159 103606092 -336315444 100579716 -948058511 436441023 -334642724 928755967 -149899143 -165765261 314614541 -873826888 -632236429 157300291 162459803 -467058391 -787098475 -638364713 110504314 513826900 -721335397 123315073 398515078 -667943901 388147322 217034645 -993282048 -101665665 626232224 -877129225 -515608544 -3512293 -123268585 41862198 552303391 -133912032 -473487822 663400444 -579113882 221442364 680538527 -637810686 -5442554 -846341815 735323387 -969449580 2677238 -643037180 689756927 149433508 648319151 -752113261 -546940375 521405150 712973825 -27535791 575073108 -525096274 -111779221 -62346928 -165227208 -862753220 500719069 -505905409 -219536485 -664445834 -853266671 -495115100 -153970291 -634145164 50421067 581060143 -602370291 915812711 407873607 -594935294 542495086 251360272 479730288 732815203 -324317828 359032839 -934501640 -640250961 22462998 221320539 39875484 824319782 -147614147 -887762405 -309269007 -935318827 211708867 -934342311 -403107369 882980996 15027256 -524438610 -738596252 -703344393 -35725376 624653766 737829898 -957733221 -965812930 12382497 -330085846 604469948 62329949 -979086874 674036810 -166236674 -609488424 889854628 -908576292 -669515331 288476722 -78514739 -564756451 690690265 874883782 -570221946 -241476108 560000130 -76674847