1000
195581978 -991425709 -170068859 585234349 -680175885 -415844540 -30494721 -310313090 298894046 -945723318 -655571552 -672153556 -550546670 -57509456 160138611 145688396 49162891 675166442 911438264 -603130426 -638255509 -124879797 108064659 263493985 887888977 100595511 994863680 473785592 779728092 143665933 -255456634 667628919 825770443 929611501 -58404495 -472191688 -275066547 848468270 432292945 -654722554 -949305169 -807437014 273100628 -597471857 -975305165 694440646 -83759683 -336259656 345243919 -709937644 -311057550 387914701 130471789 368875384 -207622454 972602729 -349109354 467895973 -319051960 933748042 -270474518 462685216 662704 151825831 188022749 206646043 -507908020 52529673 -52791434 76344819 985190955 -581131694 239496897 -230370550 -816523140 -998736045 660617110 -906285257 -394849145 -332784438 142362844 592368522 -119355420 -978852582 -310392670 -393627941 -248415912 -677182454 -778702513 115807410 -61199470 961034637 767738347 949448560 -869190876 -678338771 -313846839 -275426561 -903805238 -729035965 -742089662 -881789941 771989710 -427983168 -305847194 -611109621 -595330548 -304625847 -777559312 -989477195 -918499886 -218832310 -430767635 -725698525 744678331 -662505958 695234758 -166071565 556145293 508689488 -348602645 -673148694 -409399321 -936199777 542559624 634587956 204732275 510030681 216220434 -773307183 493517802 -20975397 264026823 964029957 21727330 -6743969 282445750 -68271626 540070755 438518153 460781561 -792981628 83589441 713890474 556242371 602364216 822004419 -618600220 -432415171 573775940 435498927 -82329878 -945200607 -781813075 108077547 230411218 -716676371 -202884200 -240716811 -687467097 -61312274 -277547592 812601838 906286918 99505667 16934521 235938953 70286858 74867219 168366780 597742620 711722817 -86655680 299790939 -755600615 -731371034 846792059 -682369141 216022045 341935161 -195885890 620633973 66031233 -445046962 638626920 863337539 -882726833 309318918 -453839914 -116900476 -354937938 253600508 -421295900 -772586955 917358885 119554723 128780082 -249706944 -388831791 -600778056 -285885693 -359668472 643584638 -184356325 -124001780 -174794160 72585320 651035289 444500428 848578949 782835218 809122425 306044627 214932213 -338605648 -14664815 -494592287 449987573 -391913174 -882190190 -968769091 748642856 -538447540 329360052 -567053450 637436867 -642378019 397146296 -602729498 -935223791 -71513447 17797302 -200403827 -549040671 506580283 775125720 536677879 337008575 501952461 -395097433 93442289 -480439755 933125176 746695452 757055379 -108829528 858469921 -439909315 374424670 186069620 243511420 676298063 919109393 111048228 713371337 -291261947 -134281844 546333051 -524929820 -285251938 -454522484 -522140478 751492427 309548554 109297916 563884738 774372209 930173830 863113241 694025182 570788819 -254917705 998247146 -425084641 -56904104 560386346 -257025887 -640443224 -294028865 -135779177 294275268 995144729 18186729 531923763 439924851 914600537 -458503594 -432437681 146907821 975739160 507535993 446612657 841772099 -323113612 -980675735 127456876 -310462602 -649170308 -518586397 -948960718 973329059 139135400 -7578810 659788160 -610940193 -562958788 582901521 -675749287 344323062 379200221 -190517537 -607638652 -880452699 677926576 -338252469 69132968 726052797 298849470 428966348 274782808 90439384 -958681886 46464729 -342798722 -821791575 -947394565 530526469 394738917 -518909106 -41575695 -29977203 -389564778 268622394 -372555388 451317265 -798678360 -595395239 456911957 440325863 -776131645 405101726 991464277 26669497 -131713309 43043497 237863292 112258023 -381307328 -496329680 -714134218 783258908 -923231374 134242538 586930446 -17708114 624713158 9511858 7200254 607611730 799694869 502041296 -16165298 -571071192 139833223 652810696 197966897 -150614900 379659933 -615353883 -342284983 252975087 916913225 -63824086 983961699 -761236023 594873652 -888538497 639568123 -570959533 55711187 746529949 890296463 -949714298 960435869 -365390221 545580303 28880366 325269103 9880215 -229345581 550371810 -967349443 -67257780 623439445 683561195 -538185070 -176286093 801409259 357080893 -721081975 607890806 587564400 -533249648 -442078217 -617809456 -593631817 844679499 194220001 -399730098 87643823 -501184929 -966154602 -844374330 -50580028 -425251712 -404191474 -293442054 475931203 686578409 -502375242 -979238938 156277941 412352840 68220021 -523840891 -56098319 -649361571 697935053 -951532153 -356055377 657069720 -555185900 -195675270 -814900537 947632356 703261720 827857419 243669365 777430521 253114280 185419042 927625107 667611412 -876864448 -372902875 -460606096 655455073 647971776 763277576 -220717626 408775870 901208599 557584576 -238601247 365631445 560630457 -311473246 31365236 183060071 -226421184 -545995796 479372475 -654036179 973484931 765705547 -114167314 -784759740 894507211 -487801977 282665107 -469400079 -418896484 823858867 540235873 -391742532 -554990182 276131843 -58337378 -857261610 50127675 -246717434 199170952 -683527889 -20855554 143246936 -426133212 -946334060 -346788141 677729605 -640257935 349537777 -414120490 248079387 -686639844 218929115 -697330454 -489259490 12671122 -925350812 -263610133 -763441845 90270650 454313778 -160879934 543992864 -77040555 -698255032 -142270459 355271858 -620899263 496602645 -520132151 -551501276 332779944 357530273 -866236916 -131256611 -739031325 -890404871 -412342236 -383212372 599035925 353709130 -642308415 -251032797 -445827333 -193592641 416667734 -706242603 -158901036 832405190 352439365 -381480051 430551748 791382356 -888149961 996341594 -159163224 -880715553 -930712130 903905115 634058835 97175451 269826513 -535271160 543790545 -246031939 -971979704 -581457913 -518024693 264764207 -661032561 -846623038 372480144 742186400 -57197326 -870355029 -201058523 -110196376 -509324461 114350192 714179402 -719494966 -630932087 -551851328 626218362 -980473980 -172418033 -224524887 617080717 -185537623 -82099739 339392349 -797808957 -933925795 -989409846 470767301 -914789651 -570020614 782203743 -887337644 975253632 618354 -42780858 676736739 -320139132 557258037 -577609493 -196595511 374630929 473338828 836108279 -19534232 -270683859 481566282 971584727 584835886 873952355 103331072 -759968026 -964461917 854871655 -404643969 -195811924 980189516 -922289717 -546447775 -602756908 238374072 -68536367 -433059346 314122534 869305719 -415256704 2184591 -801114885 400781152 145981050 379078625 458682992 132248680 -742437138 -250457284 940724205 539145450 845275573 176631557 312763414 -772301696 -256546156 -929131065 -614664402 952517300 653683004 293255332 -463137461 -925766719 -446330550 110782653 -826639325 924969230 679742192 956146145 -646997276 -722354287 512759799 -817713763 793470402 -539763784 -602297401 439222977 -937348093 507680981 302387334 902786941 -292361830 815608315 -913787561 790611059 273193071 -664714206 874127256 514546298 -3600634 -323972320 717063788 809588584 943863220 -64391666 767169773 363427307 194032051 -222293481 -501434448 687380630 -946496245 82607030 -325843861 206955190 -32162955 -287512088 817338062 -424683439 542459750 -561188177 198763686 862901520 -137494193 -250494309 663980500 -212236751 -624668339 562826462 -514774869 864044236 -854089922 -695239727 -623333559 595797069 950037986 508184762 -412507940 26297428 -819183480 -267117831 78207935 -364550725 -978819305 174274516 391773626 677560167 -87377189 941449043 902306602 -4784217 365832265 -256045353 -975688547 -342989373 26754067 -451641135 -501623331 927192000 222445479 874483201 -312489891 858873369 771568176 -472443144 295155252 -284806176 900872539 649976754 723935522 789255207 -253117991 -457707680 -844988225 -619514673 -45381332 -86376088 699688200 272451150 -375592091 -187771781 193330871 60764780 -865382561 243096334 -733043316 -77562254 885006838 -383777715 716183919 -602139131 -385950272 948629927 553800124 -952872307 -553378315 -804705338 -978948375 513357512 -659343141 -420009793 -754506840 687521692 -373080252 445471644 910901953 927207099 484148654 -431211012 539737054 657628168 -931659118 -766701218 -768776280 822940205 654312018 -623019566 308339145 -407650009 -409571888 -197041116 825106600 -422178845 -341696350 177710665 560185240 903415606 955659410 829305594 479963769 -325108447 499664486 -877113738 -328275492 780774730 100328438 -920849894 -997010869 -431920798 8674828 704779131 -697223295 -320117605 592914980 -491404492 450651996 -525023963 908207404 -760466539 325621616 741659123 543649385 830808998 -444765257 -245465650 588067962 -746226816 -746613049 825940640 -31377488 673356080 725246875 718994059 -294982155 16858616 157786066 -667774857 -554955053 254857320 -38570951 -245612968 987654352 432296779 689823870 -422797680 987916531 -248404070 79420694 517955862 -697123465 588948205 855022045 72189592 -340659944 623198823 -330053135 804139279 475909231 8936397 -124914113 -339445287 -111386421 -477420222 -761012896 -295231048 -647339015 -1291700 475033445 70599774 973972670 971730778 -122787033 -189360367 -11503074 112470119 883301855 -564238012 -729390926 -965680914 103454875 -818839482 832767597 -925468050 598176447 510814283 -940697408 -500051539 -209217206 -897186591 -409712048 -198803184 -754757202 -235150572 -618393199 -647289926 576354935 -109766091 141392777 124107248 988673490 928980888 221102955 -158135485 88976845 -605096066 -567974865 -5213121 438015781 -89282144 533464045 -459299397 -729499867 124349969 -985250240 200010491 380391790 -876722707 765772853 838282581 947064464 -843464069 215798776 958064801 -353069845 -9265736 -836977191 364732027 686455695 899702797 -821372062 451820459 -830574807 435481811 -339691560 -591948569 964946464 406257814 962438676 -624604536 349210196 -673525475 165563451 368528956 187529578 -236383157 704309127 366253214 -456628692 524069347 -702663015 153145854 399602490 -799657064 -945667032 736124328 160837841 -808264102 737768644 792050009 -479936694 -23943502 722008985 393120673 345347157 -538938256 111969763 855058709 193023632 -565986621 -588917326 -449119117 -866740383 -125609703 986420143 -270723087 -281612482 -95862563 -968641797 57448398 21719236 -16362774 564918969 -414636756 -677800018 713448438 -548314515 579739495 -886287377 454171014 872283066 -773771253 -253994180 235116339 -996304422 58045 -299670653 -414189316 -413153211 -115873169 -19259947 503949198 -935669357 -431872174 561622775 117017104 456419385