1000
-1000000000 828856218 198975844 -290112157 224759033 729068439 65585985 40209648 -125133721 784376302 879540639 96838416 -250455219 -656252714 736091817 -640724799 -907889330 -906483570 523945459 -505827352 633368931 -15631609 -798898868 325887469 859102287 -204447237 -241842595 -237898700 -827606637 571207917 718889032 -307380813 -635663649 657254723 751546960 -996233349 -975493594 354230926 -436572935 346784264 -433926811 -17526209 -650938880 -946463516 -893266643 776462604 688637097 376073624 -807295081 959309634 -639958049 924448493 750508248 -469281173 319523610 -381967954 260795686 386723097 -812438205 -874520742 -103686248 -642489532 753644326 797057509 866725031 97601837 -233178291 -341928629 -542096860 -289745982 60074478 -448545269 288024022 981314613 -812189187 -157947449 -997068336 93839081 -866082224 17780465 -360132865 988075087 194516365 247394306 427288343 -63390200 407479449 -769715079 -845860813 247820704 426911641 -8445212 170904033 -524031739 -785398466 828227065 -894961706 562984498 -501338511 782180816 -369566940 -568506984 668726977 -64899418 -731022938 714121582 -840975855 654459990 -323589187 -941456972 636140396 -367819425 753977890 -569550096 -354983324 -585340339 -418062429 -174122529 207451947 569514604 68851531 72117934 -853504699 -8720970 60554373 -224773920 -40249003 -17843848 665254637 829142942 -68211417 811326890 320998683 -671323111 388739185 -253048032 -893164936 -631919944 890089704 -550261785 -181809382 -772795514 419871305 903902304 -604495005 -718665493 392853608 558338584 -681017312 -970662203 412685972 614810744 -309430520 790273951 -981834780 268860887 787712787 557245326 923069365 -256870149 113602978 -485375363 -439116429 819322217 -4643409 -232146682 452877817 -298579935 6804171 277785147 723395732 -871532374 673088137 -539792865 -845071808 -34120899 -8476569 -717565959 355265953 -406554952 -647338197 123352295 112816595 265821814 105951056 -165771370 -872014421 667638202 254419728 -125375094 892122618 -653758475 -472053619 278148725 178150470 914098767 778745159 328687596 -782577666 -302238913 646836 -68916073 835964758 5517712 908766320 653536237 238329019 -854111820 497205819 -727796828 465758260 -699165100 -42562961 -437101018 -759617235 478849344 808363961 547383638 -37676452 129009366 -286862841 -824122948 727718559 -307695237 -642740020 -454363522 201487361 422977567 -45010344 -542740834 -134135583 -545863255 281359546 -348645462 -540018353 -68055824 -162873766 81400853 -657783738 -824479072 354429656 863977712 296895590 494957255 631857019 265570857 -597480111 462650841 159578403 -194764893 -478092468 -427942314 -958550909 -584769034 -862723972 688563219 181599761 -741625278 -683828055 -52934362 -887840356 463775870 968410357 -790994819 127017153 237143332 704900221 1109883 103870628 -410097008 -194904931 -693550803 -28296700 -666695600 519138631 355026265 -428065485 292796758 -513251486 317933045 -203771510 829364194 144065491 328743899 -169411389 781406874 326500347 -105391835 289297984 216139322 448214205 111875801 -733189482 877973759 -330908898 536635022 849981321 5029843 -165727965 394769658 975668061 -630507326 -767097226 -771507411 -744327798 811826261 994252667 -36500654 -151913658 442753628 -702389714 -341361310 135522683 -221308338 -423649572 348670224 -927199458 787545177 -774013836 578366957 12260807 -251680400 -186296825 756732735 983936583 365358100 -675105961 186138080 26116524 -146659447 855586278 -350676997 -587833632 615422487 -334055994 -807528016 156151858 396609572 242482349 326064595 224635962 595937068 760832122 500518346 399578436 749041782 -571106996 251622920 -909626205 -642139196 499307239 94882625 -111288632 -331972459 -414843975 512527441 -153918633 317750490 -80611936 11530818 -733464524 646213527 -440887205 -985516173 174884909 -286459 217422588 -476995187 -547433777 -932904914 -632324835 195869635 -736169244 -717219959 -176240615 948204632 -462393835 -443380359 798847880 848252118 -158576577 -593674339 431249262 -799720355 108320882 -727115174 798739930 643259671 457572080 -649761815 86997244 -135704573 -913667036 869537867 375596432 -111697541 -299285792 800163543 -741008202 16987541 -916569034 -660781936 7130770 -760390471 971210672 869829865 -190959568 -322557744 932330404 -604870773 -823456984 -108197973 592596998 861028742 -652547504 -608788951 182794156 400419865 -403419088 824285740 -54278721 387173091 635481526 -142580607 57156210 717750032 -661943937 -641521293 649549367 576515696 187320133 116097986 -787349620 -248400379 127672191 462597249 -622151496 841690587 131621980 350927240 -623093214 759861809 -814690011 -533332393 137251308 512288111 -464840962 218972042 246174651 517928686 770032699 290085322 424116760 166969206 442114024 -960445340 249970943 -664222442 -311048655 -315168078 70434442 320655635 -921120918 686543828 -380259514 469023858 -843024088 746345464 -827974461 -142101594 -623800819 -385165644 427939371 -884773368 -727601446 -469752306 -173033193 -299435561 -308850032 124722431 -288217899 249896859 136039580 -432910310 -274506546 724226581 -291019656 850718523 -106371126 564399508 660191152 -830244760 757628116 607340456 -868966673 -972319200 424770532 -922533017 390161951 -169717063 769967723 -945680967 243845296 -457674287 -216755322 -539406266 130253264 -969262943 -231745213 -122534877 397772875 -631860470 296531905 -287581860 299092098 494055090 453835893 -493029715 -821269850 -258292602 -566042833 -99879450 -706944896 -765370393 525511 996687987 240351509 247294416 617147970 -532843336 632518865 -547667688 -568210351 177770550 -209732760 -13356764 -870750375 430240925 840747204 -231203322 471611693 353690399 -90916499 475974195 272986301 -847760183 -685823885 -413867019 442568157 -492269266 -820383443 -623356451 -940557948 -661200723 929084402 332057778 693596936 -227411929 502290251 -739431347 577297464 836193607 493906585 -461761992 611366973 884951183 -940665681 -777180867 1475999 -159029340 -696844639 -603993401 251658238 637519563 318356410 -738414725 -830530931 508419234 193763356 417396335 -2410889 81670516 -999987878 -434187083 -376578270 -247021038 407017782 -297538830 120091985 680955043 -560679553 994197649 242297509 -634215248 845738573 -267844057 -70374385 -253669410 -53948484 -953947574 871620048 430223604 212607144 -673447415 -43611307 563039728 311288110 -869590885 -348539247 721999649 131310735 -779876823 -827288403 725676708 876289790 -460151439 464827987 412883838 -394191824 447006555 -343300571 471896968 -417024112 -143202824 -230921327 137119237 689246564 494477744 110534799 -757676631 840748271 -192607320 -418405417 58848127 -355155050 -353541038 542402944 514980980 -922081457 -380798184 475282566 207715695 -289007222 -576269697 -815187987 -523586824 -636308040 -666388232 171150078 82175739 -976065871 -836841802 781460093 -508813160 91620109 -157860900 536157091 85326051 -302458500 -626760103 897728436 -394540977 -60370661 -86058554 252377653 -7531626 -228351166 871864609 -281648675 -726029916 -713606786 702913210 983864635 -194410967 854083296 -855671253 -403417794 674633356 -571407473 372661061 711877019 -697597103 -118199822 -358119435 998025615 498924753 -401677630 -150901186 28571665 130892656 552519312 -326661930 -286154552 346103863 18114933 250257013 -921723318 -13962208 597332002 856322164 -504436171 739246973 396574666 -416993525 -993639396 -398983822 -498313350 -295148144 224344007 357037535 -554906238 -875271898 -392070938 -270813398 80682485 81644584 558393697 -326167647 411150017 -34326141 -963546309 -175274145 -954485400 -526560905 765406807 267429593 -559936172 -845239859 475918985 -8954048 648138394 902465762 932886083 989594504 -856843416 629289225 620794933 511556319 967132474 -448747903 166324190 972650740 684056531 -623053260 961330507 129136429 -597320025 -145600733 877348803 -219244586 -890916722 450393602 -971350371 -414696520 -713777763 -857157601 -163440927 243296864 49542502 -727935047 -410981228 305169421 -393517107 -556291371 200412162 325980030 229049035 -25906966 326325930 -882082146 768625009 -848391368 406676454 -301566563 500540389 24721518 108076809 608078042 802878857 434524973 -733032035 -352799752 355540764 -431685570 772364083 221997231 169378849 841660992 -748851119 -358634264 -86471869 61561998 -796787172 637685622 -264809824 -412878155 -736523414 -75978288 -517753159 668908094 233640587 -342395112 -778164813 -155044535 721050952 437199198 118107385 888554823 -540135823 -655994685 772330697 -653915150 889815107 -574910111 -644359759 -986630199 -545717188 -652774339 -358368146 -868829762 567284972 292583176 -429433217 -186316970 175440526 -392622489 579865086 -355409733 -82241993 96971696 -246718746 -673272934 542879711 867037602 245226149 -174942048 -989077939 592093257 931524837 -932807561 166193991 8696132 93996004 -6418499 650905988 -283622590 208989616 48289339 -463289150 645981250 725485002 -311455956 -205322889 -562141244 322291964 -598085069 42262124 -758743614 300720230 991680035 -359312269 -870696517 -822616929 780684424 134879529 365639578 -690327598 208160474 621968077 -745674711 303543729 -895405333 848710594 -41778055 -918990289 577403493 -979896985 140791583 564466195 762616057 943605968 159492506 277795370 328996921 302305750 -210813814 -783041632 38191616 544696364 -954084953 327663556 -112806624 -274118981 -421781980 485798186 -615181508 946086208 -820147924 206027604 260086563 -423221107 371588509 560384779 -626616378 -492899859 481389362 -250528544 -913181780 985387889 -387056154 22601696 417559793 973465719 59787675 253778681 534160795 209160431 -173881690 -513165995 800935282 -431253293 -840847707 28522236 -400072751 739850988 813474985 655094290 -329299572 336536048 425298682 463636719 451339004 243678837 -633588372 767517681 744802062 408155941 -645268214 938050489 164584476 39062878 -715164225 -401637059 -833419022 -860318106 539501425 683081133 -916983077 99697013 785708871 102470425 794988517 811041366 113950821 -989811709 912482645 290696793 -115318012 30918192 -757437750 -551291446 911957042 -223902236 256245524 395590742 -637466068 -791680290 467973973 -235392362 -951251762 477928443 345924760 663550685 -187045124 -935413343 -443228167 -735036566 159111355 -525264233 -762037317 -408924208 -694080875 -252442587 -242794431 944728305 436176568 401619412 252711172 47234216 -93409803 603540598 416134143 436254361 -987734003 853594642 45079192 -524171987 443245468 446288255 1000000000