1000
747654864 -355320586 706327887 -635035417 -849157280 -927542562 69508571 509496744 -340679620 555978560 321020376 329955429 -781772843 -200728853 878301573 906015163 754245997 564296969 -810987021 270531067 -536718250 -312826999 121721129 60537382 -795739939 946491779 641958682 -182270991 960845140 -630347819 -433720106 -488280482 -861086308 -387740177 425043941 559149379 267315267 103596259 -219097965 666022156 -778116945 11582047 827679967 -93741187 722529517 -906319874 -324178234 -541996157 757415747 841533895 -455482917 -446570610 -215070040 566206270 581820526 -198950858 186877046 879573046 314795059 -935597962 298254361 -867097464 695696909 -723850852 -460246812 -267619764 40371426 111358506 -674384615 354995173 -939850739 599671259 183987321 577616052 -536614302 -601178240 340214863 763587983 555849622 491433189 -913669383 -620310707 582296057 -369980373 262001944 529021760 -673947861 258835650 832633508 958900940 323281995 831337693 -377637438 -336308524 626334094 -728458562 645762855 -388647755 633613640 -154281763 -536511490 638636417 -844023719 633505336 -17744031 -968657358 825006645 234634253 -422949913 -521258153 -557397048 301372136 -423963641 102917323 -957427664 105929199 498284043 -64748762 -834179210 -688951412 352635293 -369179632 -476485869 1000000000 546520678 894646578 -101748587 -6888407 -996191272 -599159323 -940463961 373188308 436893139 517546647 -244566936 -373922838 -198952040 179257068 87190048 -412000956 -413254871 -689970409 -360075767 895175473 516954434 -458339136 -390109272 908426913 591732517 389769072 -215078381 346131897 -71747356 658607352 218787572 -96221684 -49369687 298000821 64622738 -144957699 820462738 509320596 901043673 -231753817 -435314162 -952178476 -9590627 -222101204 361709453 -802098371 -391568476 960138697 -734810347 -869295734 910057077 314764906 662245708 -718011063 504305244 199749506 150027521 -832384835 -621481538 558403622 -535277181 -423654099 792948816 954372093 298249346 -812862805 166782033 -174978780 976526031 574604842 -976105065 637422145 950631075 788617515 926084556 -147359476 755706553 386227266 -20912074 -134518371 -99125286 -681633467 -804593423 965440704 -604577656 -933280050 -91133918 -945291615 -87023440 214136482 -528373768 -468585086 854769618 354254344 976011738 -896179952 -158323625 -876548109 -46586861 162362346 -173253154 578633304 -103967053 506315862 -243173345 977044269 891995421 175217707 153139236 -60594987 -36972384 605648700 96552185 -935554101 -247943007 -271762460 -451937953 -676930495 647598995 -939307768 -608548920 8998577 -284166022 -749889056 662330287 -926089921 303269959 -565466194 524412061 539748480 -541959202 -112658227 -428833498 -134783852 818147720 935559557 341671221 855809838 424221993 23682481 -470790645 -677306466 865681033 64672760 -771424896 -829090474 803025809 -749421384 -569919601 -790451798 655649024 612322730 -847287819 540921438 -547967191 486973210 53970032 154071906 587038999 644376106 512240951 -752322642 683543969 448038226 356774807 845414690 558407096 -639494334 612249582 -127956973 -494507921 541507187 -99482520 48072314 253945691 -966267891 -813404983 -615161252 772324333 88828283 700826129 -832441656 -389490390 -354300707 -189099218 486636667 851978064 -587706278 -97429352 884551633 -116283796 802196981 259848248 -371676544 776611818 310502410 -268812945 -34296623 -307215847 -699277380 -127855382 -203115080 378840329 -205528566 -737403541 -403853652 -702890344 536165099 -860112274 -384448 361697916 750312887 -942888488 252913125 -250349637 560931880 577213943 -496507154 724463214 -213252997 634122193 -145367168 897095487 -595720405 -233351222 -628386363 -644286213 417440846 -189866222 -529831339 -843201518 -596089532 -468982810 -615381322 -642126875 -733770976 651933151 103082469 430609509 390510534 123778602 -519273457 -816984952 -155337246 44359136 -829797952 -589213245 -18278579 -112795326 -446687760 850800880 237725331 -622345797 133727759 -328794909 -478356924 918266722 -36367422 -168913975 -437421796 -788214881 401724321 72174250 -859301005 -95143357 -754264605 553025428 356567373 248548289 828497707 -629942545 659120612 445328150 -186434014 972360292 -236111513 685953612 -660366447 524487521 511099567 662209264 -33646220 -481386032 951095893 110772092 -173233662 990244591 4871570 361343297 -122404528 -289145379 -631462469 -665056348 -997314749 -726672835 -565465698 419645165 -821638976 -46055695 -621166047 -858579497 -174856220 -688395666 -232078901 -347733545 -362739393 741596730 524265245 4813339 620891105 392363605 729475541 106249611 61716818 705038985 773672346 -980404348 -758450061 613737713 -520956551 -227790851 -786111828 557272910 12432136 -609850812 636823038 -801170203 -605438395 540250910 -954871498 -274940611 872033545 -1000000000 -256331088 -124525831 237982283 903530975 -435884995 -773176637 -198368980 309991923 233901565 -626595024 897715234 -118775974 -449164059 -154131644 -753423211 636958721 -834772576 324832733 462311528 -708145800 615631763 65247108 234966638 756015403 983719173 533272672 -472610448 722320482 -481885082 539251385 439573789 100417889 -274892284 -191883529 72799480 830260877 -842378263 -172836469 -575450063 716717887 570579373 -403718656 -748892365 512384203 524674379 -569972891 -917038363 124028892 947414314 257879333 -201604903 406179030 -377685249 626240859 44915740 406637257 319268532 -477008471 486408418 -805832086 -784770838 436072630 739604159 -264447060 -640431323 745596917 -439805927 -529874621 -149629932 -405784816 52647662 711894740 890017916 176779055 -349085825 -904372756 1901333 -296110842 -875182284 574154987 -381788785 -323059734 822991150 89733445 721655567 -298721950 295183980 670541284 -488325343 605671487 139862447 542525981 -665236646 709205829 408859904 -338894358 -39105858 -267898341 -506300252 118449815 169576915 570070498 -227532230 182543854 -851812660 -92229978 -189753568 -970898208 765566010 -991864845 -790285721 413953001 -112841647 791382668 -142549601 110676613 713699694 -637629924 -53269688 -943100682 440208529 854644323 918488068 911830581 876991247 925518091 687172442 -324928031 -44090428 400798801 875136397 -572731512 -379616306 -961091905 429556170 -764257374 -484923092 -148313632 772940985 559782962 934283029 290901405 810811488 480593107 -530832017 670761376 992179292 -198861174 811616260 -274015759 -756599248 836705441 -43799439 -480589171 -713907875 -628559810 418204175 -981629420 75235303 -83831462 -764393563 -878133797 102672469 445996657 -715424941 -744285975 -274342884 481855749 -557430834 218966968 -269651799 -652075675 -117031508 225183115 944171132 -525895660 992425246 -629539054 -663761588 479554802 -621270222 673155072 -518736985 294544171 755036118 -724510638 -330957166 -393714263 215748301 488101831 -929235345 -298534334 -114517815 -621445723 -654507328 239159766 307685048 -585947819 -422681436 491185968 408339092 365347869 -254533565 -451801590 846915430 -87707013 -619429537 -328472755 -740746310 -686972154 456753666 -965565076 993742136 -88120620 764403610 124066957 -152011758 432243901 173635433 780938351 349671460 -450824502 -282967139 850010328 766846926 973366164 494191012 -105535462 290729201 -354759736 327946944 -288161085 998511460 311272826 80542285 -545969670 -147126066 -70460043 -116440557 -253446913 736107273 -409038451 -782790610 -482835405 352278862 544704509 -18696450 -978651926 -379373890 743955929 884391622 157656008 612030094 -158949022 -185959796 -471988001 -280653777 -691213334 286190601 528247622 -294739468 -616488524 -281935921 -398918473 539854145 -646885055 582704715 -719509000 384042803 68378527 562162486 410045887 116874956 263397674 -542169934 -220566735 754747904 382599559 454054771 291113349 785094270 -9213911 -902228753 954481737 252532226 -723360755 374334327 948360710 -560841755 790983770 -465799694 569717345 723491216 -685984444 -950115047 883454358 613949946 -406454114 -930195879 -5956338 380358159 -976425561 517680152 -44824195 -371025781 41340486 111796162 985697383 213052023 -4605177 777423388 305585374 635956372 -644562720 966413491 438586752 -538474805 -251090305 -946323446 -552417810 -396487915 476390993 374138462 -560302711 814612399 -869512003 -124746194 -926639762 -954183823 -701033003 -148732315 -955887508 1 -345777082 -582609090 267056340 -951376874 -408546329 -899521392 -439783383 -23425159 -846641599 -391476836 740110734 -334452221 782216577 765097499 -952632009 -84605171 -958926317 -223880537 592142455 924278823 -645558375 -593597036 454926055 847262179 448441627 -926054203 -702285760 912575194 -195640289 399612827 -369898661 -298124557 -236985093 563571312 400399464 969304816 872350600 -700776958 -862088806 -269793660 635272976 938563825 -960952595 710277356 503082370 35545786 321656924 -959466354 681339654 360479608 990859900 -884196042 50963274 56559931 -69727780 603199788 56428739 -385067045 507001796 -632171289 -958320003 505555878 378205462 143505136 327449097 957782659 -982946441 643883536 128559243 656089657 -78418541 -737589403 -235206418 -665307877 -240541507 -910020591 -234141310 751070277 972744630 -625217953 -320837891 781054767 525858447 -10735180 596616048 -244965160 500123054 -366311218 203971522 407683191 168697009 385636505 -101577323 813349110 -264675149 -346190840 -966830543 337258425 119286612 -309186555 -814829797 24903030 -289383162 216599987 701811272 -398215893 510327546 -777055808 260849939 -622248985 -342564574 420644982 515105889 -856790012 -853348506 -926208989 490722556 -544080177 -971056440 -298750833 432253589 -570644722 639822476 376981282 -968898408 584663216 118986646 -457230735 543518444 208800911 -451741139 548429738 -547890769 -891828676 -754699106 -289430540 150492875 -68867383 -837949706 395062728 -167215271 69832766 570036243 527855072 753964706 -868159688 747389641 297086343 245730799 -568063760 -240329287 -641825322 275888188 273990851 429451851 923211660 81191524 721647712 -17193338 796499148 179053004 -624223201 -230574737 142310052 451444072 968166670 807977267 -701835770 329266275 -220692215 404550330 859170407 821928026 448582663 499675354 -811951328 -472901964 872705697 -576457707 -657687141 637474635 823720891 -327300936 -829340171 32192051 -605135377 931222362 -945386805 -546030711 78062348 107381022 -734985994 -498061218 217969767 14155248 -890915279 824501028 671436098 -847864224 -695436300 -11674198 -537708174 550444028 470476829 -91698975 966255478 -959043662 721436423 -486152185 -906153529