998
1000000000 799142027 -740581734 130159831 934571208 -624115991 -739666288 449692974 208708053 163588632 -241099364 -744073122 -862637253 -399222994 716305729 -115258397 269815605 -583780954 -684383986 -7888060 -831203481 -545406909 -248125614 229943439 335624476 -708074826 201290682 -41650804 518610780 -170258549 -715863965 442734201 -62769111 515546482 -109866557 691379967 727600860 778579653 -642057404 -773523844 287141449 -728425970 -516732716 -681067548 424445016 -262097161 -121563687 -966200020 -885876803 -206371804 867856079 -245588198 13066709 -832858037 528495875 853669571 -134509418 284110550 392728021 -295536325 -792045025 103076461 -315650165 -517613305 -752554380 836544568 628071614 -389327931 621325543 190079713 -840905128 379050812 88131121 -565472098 7652858 -805350729 -230427525 887909020 756422877 -791137356 -519524333 -83605103 656849376 -197443305 401471169 947265042 333513828 56347306 148891979 -336699782 304973666 251319184 -460628194 -490909660 289789030 -853475974 -652628789 -719766059 -158924219 -35143832 -410392249 -334925910 273955666 -60031220 -958890768 333306078 573428537 -810996229 478885868 94084727 -618222456 -995418592 -50876058 -962777692 -791713517 -164606894 -949294320 -994730584 -370609161 970076840 259916473 539242832 -226417057 -328911825 -985978405 639535947 97280647 269376330 437503466 -649635360 61484458 -829231404 -854551678 328770809 -394865720 -840142557 -768116902 -610189815 -832882170 -793806199 -117749317 -964336031 243092742 553908376 23541764 -510125431 459948954 -341931132 553439184 786632466 923387325 943609393 -546460295 -985090456 -362404386 -85077218 821477503 327319554 942564749 -519326590 87231139 691615162 717178588 -209043126 -751561308 266349051 159236129 -480603268 789720311 528127302 293521341 54037145 -616085285 165933862 -730336425 -613544692 -3837218 -709629433 355731044 857121609 -38680356 887430836 842164446 240523705 110161184 -916866305 -46301991 -290530622 -951923611 840839748 -598768665 832530836 812145622 224413999 472546434 -120589009 -572085913 521796813 968902917 -72634372 -769284335 -452158681 717002387 -615083646 602290132 599880924 167083194 327435627 485274312 -592272655 826538498 -818156732 -544997573 893176885 -164409613 -548555457 -948798918 691228905 865095874 11442367 448742398 -460114167 -522670439 421151661 -101619026 100885507 -814279361 962066340 -373230955 751388019 530674737 -529302834 565658831 93543972 854988389 803358989 743556655 384553021 -194434295 -653570354 457261239 -659115700 243038456 475494033 530967064 -808381950 -363916314 370317907 -829385695 516699854 437523569 -862253296 -7384591 395258301 -838243010 345035330 277201473 61528110 746765966 -848589459 787131211 -703822828 -78897697 -138826518 476888782 150196161 -681670302 -495647068 -762403972 859900239 -444190227 -232547077 -767934650 408754134 -958917540 650705434 418084950 -88040183 -627311094 950280291 568157053 -554636381 -434713794 929419399 534639908 -173563159 -55021654 -632666858 111751241 -466180190 40989513 -951650867 816408662 -480176575 -846526148 865148245 -260979233 -644283671 402088459 -36144717 802625136 511739585 733732471 992010811 -110125673 574553835 -779136930 -159527 -789237924 240883431 -968819006 -560900645 65507374 -637348551 -54442705 98450066 996560447 -57189047 -28925233 -640144220 294200888 -407371819 942762606 -156398598 -245523968 960061810 -641172521 -487544352 803319780 191266560 -730632760 -325184976 -478988654 124827138 -544596124 625646495 -433119682 369171556 -198226034 -569150755 -569992778 -606037137 -715048615 510591104 -130915631 492317442 176693102 634097242 -520913815 -747476373 620132767 -641542795 -333356287 454381661 881693105 -268988535 408399883 -779129205 423038530 -3530927 660672349 -8804624 -563702638 490643119 -694119150 -368278330 -951908766 979775489 716263618 -77209516 866161302 708315055 261742044 -777910397 909563537 -931153202 849071069 -638233148 991749975 887891090 381231588 -363059444 -851946324 681214216 -365134416 952214983 736021726 741404181 -849884076 -413348529 14140932 989550029 893186804 709338716 875139234 928227044 899740023 -540366231 689727677 719813557 -991140303 809047861 477460330 -997302659 -589544733 -700891594 -994473207 415014227 607785974 122011960 -984578677 766951707 -254497874 469554999 -918487724 559044006 -426161610 891620465 -277385100 -782106454 216743891 -469760581 -735625752 -216892130 -600709989 225898834 -148981052 -119648747 439359599 -968951403 546946311 -40959879 547487028 264883501 293925915 97656743 -544307906 -932193358 -699261858 788021651 466730297 -904814881 -361696569 72719050 -791253226 653809140 171987101 -388803195 855925034 -271814275 535404279 777104888 -135094685 -283383078 -652194311 443865710 244886013 -684308001 -371985288 94303637 -115562474 -253824598 -534167540 498244988 -274856469 -950472100 46644146 591336750 -5024199 -463949531 -47065387 -689067363 91780790 -923722939 -9639418 -428418734 467504019 -219612436 -422738023 -33585872 740521745 515608502 -141790661 -242798325 836039555 42369479 -651279721 947420746 534581466 -987096353 586601058 470126409 -867812425 235113666 -573125043 947551889 824174087 -232581697 994972899 -395251493 439713207 -123813545 943491293 509091881 -753417434 -827871040 149060219 -98417310 -664120089 255930662 664490710 -49083383 279508943 -48638826 646691631 976879631 -146596113 -561406059 709362982 815658877 240555078 31666776 -546516082 967949776 298426099 -717596594 547607076 866204064 -708212350 957404802 -814359643 671569150 47974999 -426816732 -311068176 -595650538 657025686 -427720484 759983562 671304684 122136078 795590134 517250205 -784381064 -246550329 457127315 58110531 -944040945 -796324584 734824706 661786211 -491505624 132280651 812731692 993780348 -29751535 496869879 175057635 779947740 -304861718 375976120 -877306328 418478807 -274513199 -286716571 -441031992 -593387442 -343531568 -461608874 -830600934 349021382 -530870359 -28168023 -831268064 -297999801 769222253 -979966883 -300597713 -604066389 673051136 -342253022 811558937 -752624567 394300155 -250798284 970610638 644801521 433018325 325690430 999006491 143815242 615176558 750985007 573770354 11120458 -546970537 -366897563 -367613894 -771715961 -986920505 -659885907 -84435789 731687607 -525968109 682569651 612001258 745110401 -194043124 962951797 340999625 171300034 962622933 26596200 -831541070 -775223733 966546312 -950765379 -226490546 256878973 -942820853 -189225783 62136519 933257094 -287883200 -295777163 918730624 718977349 -719860436 324597811 697888414 708661733 -732334318 235257210 384464559 375490798 -688343546 863401515 -415170517 -918782475 -751477116 393614066 37446566 468193860 42435123 -363328965 -551424889 -595708597 290810644 917271121 669712715 947976186 -741126322 513112864 -976994304 196883898 -367958132 934776351 -49648431 585104913 512690245 -916355757 518352202 -442419468 -139431667 -841955127 -26599013 332786894 -884497484 -719461709 -714966441 240683195 149465522 -395343269 645902922 754901862 -393617322 -931033772 -956404056 -563068961 469602681 24895626 -14272277 -703071793 930317549 -932638603 632569525 -405108513 995397010 -850990880 -612308883 -45617644 -318541198 -974606338 602279149 -676528479 384236523 570411762 -131590292 411598587 -320823905 395233177 274573236 -211752140 -70222046 845842977 973214230 129760410 174750967 473077312 -179669908 246789854 65622139 -879163145 -580899560 -620367863 741275895 429623031 -506100313 -543362905 974907138 277602379 -446332433 408566742 887099325 -120431739 985790987 458567325 178066 949147923 973163740 799021336 -355560512 -432062591 366936379 566166147 -322538576 -92668534 841708574 924777478 907423854 591322169 -274531255 101241132 -216616655 -343894070 -159069457 -160994111 593532838 53502205 -549868922 -126805664 277071042 393007166 -162290963 134693464 206742999 175790651 -963785513 -572905220 -217664627 540991657 487397830 371950194 -93441068 -217050512 20831231 150680217 738004051 -692817114 -970390751 451415605 -971885036 -830692719 623556655 154137196 750830919 522779904 484704728 -303192690 -113162548 274773257 762999748 -728324664 770490595 143516060 -88294992 861660593 -295197811 847867175 287028807 682775498 -706634387 -352366602 5956174 251636829 -511451626 -828886285 197996160 847745994 782176366 316090052 732960579 992211763 429215473 310770382 -413662910 287255385 842302115 364002259 14824865 690464316 755451392 666859445 172249291 951873434 412986940 856176647 500603115 255724768 881709143 -260505229 -967969707 -547633551 -485269269 585506473 887964293 934714413 274362303 -63333825 -483889370 -46624901 -218970951 464021785 -570677747 997458244 -60548715 836869634 532150646 -669027629 188014609 -520901477 -101507044 -712263908 504396026 -374270518 -309612119 -296755254 -443249339 -767024576 811526689 851681896 540540362 424201957 978986488 -761014844 812216380 -140490598 405014693 302445730 -8741587 813096512 -508614503 -502043310 -368837935 -178836545 336856839 -320539968 826044138 878776378 -753289585 -914513197 815852981 890542655 549215520 -29943789 -817896522 -79491138 861348233 843120118 -243118386 -830236957 661355822 -587164438 -633040888 -21391881 294430372 -260069570 -563927591 -895988577 -27956015 306166007 -278438934 494295284 -947374327 -476491376 387259542 173430752 630866847 834102169 -725898701 -471872682 -554711397 187373810 460130573 227732672 591341510 -793680524 665160605 891471838 820995574 -372728416 372646188 401162840 -717788637 359120192 524008953 -279968847 -822249664 821446139 450159057 -64027150 -580937737 -651674561 657363312 83047112 -623695852 914427910 34731578 -331165710 -404041855 -751685919 -346599482 718748162 271875333 -34324940 -785961400 935400161 -301732259 179341898 -488668129 -157075401 -202466181 -419335667 -357805367 342785416 -953461095 384026824 325818270 -555553136 -257992376 -654786136 292295302 296519636 512084264 -903735964 72357565 -40710229 -102838100 -636732656 -256372588 419006617 -77101732 -441940139 793337034 -517069315 -590094191 -249492723 -580233828 -990855816 -532606010 597238135 669033332 644359044 -109936406 292477849 912684377 -710395746 -503519368 -780064316 631205375 728730518 -779271662 556132493 -521723019 938120771 556734545 357845596 505004038 172785692 150888601 835709093 -100000934 -637176978 442057585 470068992 -264727146 325958272 -1000000000