973
-1000000000 845910854 -439045356 165610268 812408984 -362795192 -416376289 642428756 -803997877 266569061 -496745241 -273953353 173267760 -484843815 177951142 503761066 677880357 -662779905 -436499157 -861824908 -929079718 159064648 -60629489 -457865209 55898503 -715559807 700386805 679965138 207230677 913718751 -566991283 312658005 -948158232 463578890 -723692039 -434149687 -399613818 509162707 -726808198 826276130 -555481689 288089415 -89469205 642814684 575039188 853289132 -48833296 -342903327 -189838449 -877336312 -863961752 -12948346 -196585324 -836403299 -629858053 946487477 -386944945 -495047245 -795992269 738579266 631578372 -790000885 -808940450 -485672562 -634094174 -447887776 -289036463 -819947856 980758455 833007866 -763199686 -157600500 -525255807 -770927751 222903986 681524017 -366315871 -886420761 -968175029 690054078 -560510260 909255529 -672837469 265908487 444312804 -969423574 -262224169 77666478 -493116568 -701749442 -674769879 -783317594 528483828 -284547585 561305039 -81259723 -284633058 -200371004 -331246824 -893272964 -711187514 -726429153 -891973161 886336149 51817801 281413771 909618136 177923197 -163347587 -757631011 43120929 -412403210 920065047 444269248 -547189368 -251817330 649380467 362783565 830697856 30090003 -567219196 -748916278 -923812528 252415686 -73926987 -929804049 -142952620 482513781 -531639632 -672267609 -623925543 -636090558 469726597 -607589130 194848633 543441306 506367184 -597594665 -149527272 103970887 991229861 -748032695 -415119656 398868114 681302333 721857861 -651468668 779373559 33852075 176481170 -585805685 -687490644 100547938 501666744 157485234 -176290629 -486241282 344178762 -895440286 -908112764 -869939961 385130034 -234232900 -360141758 -806271296 -299201915 603417784 928604844 305107808 -24001714 41735156 -307838652 62927970 -692354961 823423599 -681285168 -308539560 75113095 866884159 -846157156 857834196 -693277117 -363709831 -702561728 125746364 -389132623 -230178326 916059036 -524647166 -377538827 -347882181 416813287 -372211705 648028199 -121278661 817058874 -267019211 532295137 -290342085 873350776 717384810 234105602 -129267609 -616094245 -6085598 37844889 -373384182 -699903712 273555706 -27086777 -170351606 195687822 -891552116 503332865 -719930726 54412981 938708919 -454377438 -42945906 -763332589 927607457 -122526962 244466135 832711051 400810740 77293470 -663777118 -827517594 -240612395 906119583 -318118351 572000308 -199922972 342790221 -151050491 -613161706 -907930454 -570434957 96836054 -201648824 227577201 902800729 -70635781 -478577120 809166172 -970835530 -811118962 403408880 666846965 491589785 689965268 999759301 -350627747 -174823543 -819998519 561660270 633475078 -188798559 155220541 -738138882 610061985 436195168 -665546851 467186035 44974342 81363156 313258835 -251612995 -738019655 -963947644 599779555 -336759916 -454525744 78796532 -588240670 284749480 47511519 -369919772 902062905 786187232 563008479 -322720928 -939693173 -949787395 774558765 -876688264 846610038 775584973 -613090839 -376053159 35106482 501065123 -865943590 181286331 -137264970 -408477792 329485115 -96310629 88057464 472919631 -42795523 -237058589 -245001724 534762955 -513932039 541884816 327557533 585156619 -339804086 497923260 321094036 710222853 -548564290 -448350054 202791985 -848247 38724646 103239078 -966341027 -518399313 -114688998 -15413315 -356712737 -709377767 -482800403 -870867711 980156882 -785156112 -545701553 -803350700 -477569365 -509556476 -254915179 18148082 -524169826 962896536 -417013805 -245820602 5949561 907340303 -313083535 -690288979 632695322 100962652 203710540 -153983483 694192505 -925343457 570954572 -629319085 -521454932 -450052213 -741811508 -504362943 648776426 241975396 757039532 -172398709 -349068226 256755590 291891736 466525843 366560688 -600821163 448655214 -889297860 -107380573 15864647 -990104456 42170279 -616892788 -564649536 248461287 440692654 660257547 -123669755 367120135 82202088 43720009 -320529648 -878958531 935288652 702098280 465430526 -936911270 -605297653 -651903125 457219170 -809811094 -903905122 833075657 592305099 -261281462 923678436 545151137 162691198 605202644 -17254694 -700925654 823683590 -610061174 -697912525 716157182 -603645056 -484220006 515453530 624081109 805787303 694890525 347338320 -802424234 -73891794 -788927885 -691063495 -554561851 -536617078 -258128805 692258206 299281958 105003799 421023933 837235488 -280892464 449837545 56420060 56254843 448700988 729725852 -161680179 -125143157 304669829 893795100 675383701 842707058 261735611 -46218166 -765335997 629487776 -505801854 -974866357 -31304699 -605910495 911574952 488459851 465369126 -680784855 -284362151 23968228 553527989 919066058 634697184 709747676 -194782644 -99935 -95340919 547074033 -727371205 -703466436 -54802092 -782904220 -609529810 -562164694 -943963664 -737358858 -549792404 850877865 989991990 -468610585 612117734 564032658 418463615 909843683 -688681735 479123760 -404575445 592009457 45961924 -837427648 254968556 -309783664 -72908985 -301498397 -404247038 -470602921 222870545 409548019 47170191 161966009 719641247 -47750341 304665418 -59681039 -960256788 598453431 -273246452 361914651 -925216695 -291354564 106380933 262278533 -433309241 647524103 -747521023 -7477007 -803964360 -151671815 -253097525 -579766487 -892772152 203274309 -961851484 570497481 523580717 379280858 440694200 263162616 130047460 736969973 -716751158 722407145 -359519659 308410149 809818973 -965715403 -194749490 -267903067 -590617010 -413729192 297491544 -957038410 88691991 858432754 589672332 -560111742 -332763527 -989390045 -781288738 227831532 -342696810 -187615460 46076146 -678327752 -657732931 333556710 -453491090 20066770 703640612 -623607886 -823308043 -954676109 -198738384 423911876 43344911 105423627 979121063 -496350343 -713000354 -480116242 -895495830 984914646 371622533 840903218 -353019684 -304336822 -488209601 801535299 -612281901 -485567326 -858555518 -640784530 -68139027 562165841 672112137 212717628 -997751935 -855807050 50155701 -766200302 244032158 972729283 -665673701 161346384 202635792 70957411 -974593135 482649178 -78886278 -766818055 -90425719 -22738523 -972906754 -525365007 -563259071 -986034706 -921438606 -957782450 -207898411 -545998273 -838794603 -477195764 391764835 622895697 -923669234 -58419835 -657955840 575357508 51819007 526475825 -160081129 708022147 -44847444 -870721490 -788741198 -463811384 -420324744 -624199859 -64588197 200082254 -55832512 941654775 -542154087 -325013028 -909437959 -98741866 -6237612 -927339360 462704971 229087452 440943285 747350970 -117260604 -54089024 -725514739 -359285077 -912091619 -702794514 31993880 -345300380 -592903381 -990516454 510901756 -573954458 -644662194 833000209 -130648169 777430839 -920083053 -347718810 607905318 479166732 -755922846 918021028 -905909563 668788692 936066566 -827062888 394514538 -875060951 360469561 283880615 -849762666 -12146486 674717391 636194407 969115463 698529305 81377882 252414172 -630584298 -241521326 -318048442 -904539549 -967658694 746793459 802703663 50075846 -950266720 -30788269 335031114 568557282 -891156003 913396057 -213743478 486932569 983302629 -377053605 -250926587 -25404645 -549069280 -393810337 -674522351 -324153704 -286568824 231132197 353497726 -226119048 -545795242 -820629780 -554763666 -749152184 -821815273 -849040307 804518295 84178852 731621452 558188447 -156018557 660878223 -574488426 95948098 -940068257 936169302 -933669723 278909241 -865796854 -783505032 -385417431 780771589 -371324800 -67494539 -545609718 -220183498 904880200 540976825 582625607 223364005 -385489382 594472835 -427933709 -975789104 -383281860 -932786223 544081818 855162096 -23101354 -270632666 -491875852 741427814 -298409637 -848001982 -956676336 723825003 -79970637 613371971 -80556465 -57927708 436002579 378870700 333190744 -189235744 -734211845 -618047542 -906428613 -811448031 436094799 -978895351 -770031022 628639577 683180087 398836938 319669386 5553647 148718343 -126674596 678196355 -589785764 -934836965 -608150757 663129277 453806850 919077828 -141928614 -196735683 984921861 123196104 -405589516 287347936 482156657 390321075 264331220 -320278684 -59221662 -479126443 886381950 714567668 453789835 543517639 -516676228 701839602 -256628393 415046469 -412551875 950825100 -506159131 536528774 320288713 802891613 -296662142 246945611 -640328527 -405699276 -759189881 694250047 219794710 -318819780 -416017146 612156169 -642330724 -443061204 -79021157 840045756 -612736032 -273842988 443367805 -427694833 -361544998 -91896808 790352624 303323256 62971767 -645294525 504779470 -618811608 -256132206 354965723 -555334308 568067961 -372431046 -759918317 -939600721 16725008 -86935481 366441189 -998313237 -656960808 -179580043 723899011 -635202151 831881882 -25394742 -327974447 717526954 -727281760 -589254437 -956437301 217853561 793199936 -770167100 226335478 399281573 698774097 425186620 684372448 -968768991 456924722 101431047 -811226595 144060588 -407035240 -121435234 -792992455 108560326 -174465538 -925035736 -24664827 -214147249 81727772 899805628 556275240 419407536 159784178 531634836 -482575675 283268324 480047021 -320703944 -197069778 584328029 768242212 -447268842 100535147 -98467630 90239222 970602513 986518726 -603971511 -517587378 -865140161 -155856656 -413285757 916616071 -154773425 -136649430 177211134 -981602052 879672709 -386289988 824325606 -911410278 530081953 976099899 -859833478 -122732173 -289823878 166165724 822431197 -881302477 -896326606 193440977 -589083670 668437687 609282955 509839904 401071504 804880725 -295219236 -413993310 181768209 95047971 -722455188 -687662588 -417177695 316909319 -293694256 282680713 372244065 617715019 350692924 329489519 -231150858 495133727 -694766015 601025182 -420661896 371627555 -887883274 775672386 -42305231 -719619011 -111332670 500069270 -467166134 -79857804 -463894115 -92149826 956892839 -396488560 20935571 161858179 -745528431 -488953405 80798546 -943100235 580063707 55779046 574264793 292800467 487431886 986636775 -94166810 -534995975 -233712736 170201953 -326609865 112549435 76133662 -430212359 967525300 735195356 -964932386 70469536 907330508 1000000000