96 999999411 999999036 514277616 751006740 999999490 999999101 111866990 736059274 999999769 999999139 999999101 999999723 999999986 835192334 -443564798 999999017 984397589 999999303 999999791 999999151 999999666 999999177 999999648 999999007 -468797550 999999093 533455471 999999266 999999239 -406147813 999999074 999999998 999999934 999999082 -506356074 999999784 273654735 999999785 685024275 999999855 999999743 999999977 999999955 999999524 228776650 -642622116 -142935771 999999519 999999621 999999746 -334178893 999999390 999999920 999999319 999999898 999999766 999999396 898304120 999999832 999999959 999999665 978781529 -897594597 -676107104 999999893 999999430 999999782 999999486 999999498 999999661 999999699 999999633 999999429 973372235 999999737 999999539 999999042 82670789 325205016 999999848 999999047 999999065 -266748578 999999091 999999892 62952149 525887744 999999832 -23966900 999999734 999999557 999999903 999999794 999999392 734810065 255485965 999999587 999999949 999999575 -463176049 999999190 999999281 -461920902 999999936 -308046632 999999481 578089438 952790576 999999674 -675830527 213225360 -254669996 999999800 999999247 999999603 667472956 -602576893 -522965139 999999432 -275252882 761901039 626016906 999999500 999999051 489804603 999999528 999999561 -381082261 999999856 999999143 999999659 999999567 999999691 -540958031 -260767149 999999367 999999729 463819502 -403045429 999999917 999999201 217526876 -611372172 999999801 987420157 920052333 -975632638 999999492 124715997 516842571 999999551 999999116 999999410 -225681883 659494484 -763972796 999999517 999999691 999999575 46385936 999999998 999999995 999999035 -116014572 -820573579 999999856 999999067 999999397 -528838426 -603173810 668489742 -251280386 138005223 -655917418 184361631 947982229 253728773 999999020 999999336 999999450 999999552 999999528 999999851 -138161271 999999365 -892180402 999999641 999999492 999999012 664984488 999999341 -323063677 -106616694 999999260 999999029 999999929 999999207 999999084 81144346 999999810 -919530362 236233426 999999394 -638611143 809126539 999999948 965924212 999999083 999999107 966515829 999999016 -500940032 999999392 999999592 -320039418 999999776 -246431603 488070477 999999846 999999613 -195117250 491811017 -52282356 999999051 999999813 -32774771 999999360 999999608 -936708761 999999762 -830909883 -772020470 999999665 999999951 999999064 999999377 -287309503 999999130 999999878 999999856 833899496 999999885 999999441 989344833 758805569 322728649 973049845 485040520 999999150 401605792 999999750 999999786 999999648 999999478 -588215779 999999531 999999789 -759034308 -995991547 999999002 -804394398 999999387 999999047 999999768 638953237 999999971 999999108 999999983 999999603 999999821 999999819 999999417 999999115 999999381 140873252 999999699 881873333 -290630333 999999273 999999829 -959515150 999999456 -478515346 -261130376 999999475 106139773 999999774 451713703 999999129 999999233 -243687777 999999714 -542770419 340790414 918025136 999999655 999999764 999999756 999999377 999999548 276528372 438748718 999999363 999999118 999999203 999999659 -856960798 999999772 -64500948 999999964 999999973 -828879120 -750872394 999999199 -753420947 -208063839 999999207 999999054 999999665 999999237 999999655 133043200 999999788 999999406 999999522 999999409 999999498 723449842 999999045 -322291611 999999552 999999490 999999453 999999490 804138489 -711740150 999999457 999999455 999999080 999999658 583539663 770630842 215060481 -314709825 999999580 -617850956 -207975136 999999955 999999344 -598909476 -202503131 584632095 999999475 129821053 999999627 -834498845 -646921699 999999693 999999643 999999817 999999814 -451252425 -159877130 999999397 999999339 999999540 999999202 999999828 999999150 999999635 999999208 657625719 83266311 999999823 999999932 -387741659 -169452017 115513266 925388117 999999448 -819728361 999999050 159489476 999999641 999999728 999999352 999999239 -240242638 999999850 999999695 -954754928 999999477 999999737 999999047 999999227 999999903 999999381 999999742 999999308 -720405561 975240461 999999247 591810221 -343947538 229495020 502795764 999999595 999999611 -663972324 -680475842 49010332 999999799 999999365 -11914840 999999103 78939442 37008039 823321704 286142071 384553962 999999185 55754487 999999874 999999677 999999997 999999056 999999045 883254879 -218139221 -962042286 853380423 999999821 999999850 999999636 -924233274 -634057322 999999759 721290358 999999209 999999364 97252322 999999028 -792224111 755465621 999999135 999999816 999999835 933390433 468693219 999999558 999999434 999999915 -158307256 687725498 999999340 999999796 -424667451 311534570 999999347 999999921 999999949 -264793188 999999525 504213623 999999526 999999028 999999347 14933919 834122314 999999529 999999755 999999982 -820366352 999999298 -935138900 999999709 999999276 125147967 858413346 999999593 999999744 999999093 999999708 -662181689 -771227885 999999008 999999929 -808021459 999999697 999999923 999999173 -7513526 999999036 266641826 138507209 999999043 999999496 -299450949 999999121 999999666 999999280 999999505 875847483 266569866 497666510 467906218 -624903026 999999713 999999040 999999009 999999069 999999539 999999305 999999637 512987048 569643065 999999698 999999019 -801960986 999999198 999999358 999999450 999999931 999999228 999999225 999999448 429297940 -737345353 999999579 47416951 999999330 -611879075 999999444 999999570 999999097 809123824 999999759 999999615 999999015 317290301 -743398960 666894356 999999398 999999345 325452137 -936593831 -690342466 999999141 999999516 999999691 999999124 160746420 -446106178 999999792 999999857 999999205 999999657 56030178 660119865 999999722 502365291 999999156 -42064995 999999564 999999175 999999271 162516557 -617409337 -498028790 939534938 999999824 999999895 150632329 999999893 999999304 999999165 943761890 655373697 314628925 999999163 914747104 999999666 999999179 999999801 999999698 999999153 -30772613 999999236 999999929 999999757 -8852035 999999659 999999018 999999058 256428279 999999235 -648501854 667626613 999999998 -35882340 999999243 411651461 999999172 999999852 -443754222 999999202 -514079200 999999154 999999215 -533585148 999999029 999999257 999999127 -845708361 837290046 127385950 999999034 999999355 583761827 999999065 999999473 999999633 999999326 999999181 999999189 -667129042 167524639 999999483 999999490 999999850 999999373 999999213 999999720 930529840 999999346 204627847 999999713 -148189295 999999708 999999479 999999877 826569048 372210707 999999437 999999203 -72639644 999999681 -537491734 999999705 999999221 296746321 -211548269 999999218 999999414 760369 999999198 -511125744 999999708 -525801753 999999600 999999348 766359715 47361623 157015763 999999275 219709423 999999861 999999014 999999745 -228435877 572566364 406390678 999999580 999999379 999999813 -927798875 -638768584 680850297 999999744 -658833427 999999098 54217588 999999517 999999673 871983183 720975917 620144286 999999496 999999100 999999938 909296579 999999420 999999526 1000000000 999999025 319067518 301883980 -613763357 999999577 -801295739 543248208 -759166687 999999991 999999457 999999916 999999460 580064491 999999045 999999489 999999425 576216201 541488809 999999420 986503496 999999433 -174395313 999999421 999999934 -900478102 999999158 -265187018 999999678 -122295858 999999377 -765792083 999999770 999999570 731961686 999999753 999999285 999999031 843678266 607610386 915746014 999999652 304339963 999999394 999999632 349949858 999999601 122246841 999999202 162799496 999999602 999999226 -622185521 -889750129 999999943 999999278 999999229 999999215 -677973496 -606327564 -328975450 926514971 -943683353 999999321 -923522021 999999250 752953764 999999189 -952746163 -710313853 999999394 -530234387 -651819960 640660400 999999535 999999915 -852833668 -115584699 999999995 999999952 999999660 999999610 999999742 999999732 -168447987 999999258 999999565 -416085562 521089629 -862367217 999999703 579101930 514923040 270049834 -603654350 999999655 -752645267 999999983 17033419 -614748151 -866215026 999999735 999999253 999999972 290764168 93895726 999999910 411283156 -380996335 -550315861 415814895 720374975 936645325 261280525 945003780 792353422 999999193 -664173371 999999803 999999782 999999697 999999764 -743189892 999999904 -707895660 525320152 999999925 145266077 999999633 999999358 999999246 -232803738 -8419506 -197922453 -65063751 999999437 999999532 999999230 182501845 999999639 755542372 999999731 999999185 -468232820 999999165 -975003240 999999793 999999920 999999415 -729421302 999999480 954547367 999999955 -150415565 999999929 999999183 -712233075 990420290 999999120 -972995847 999999868 999999183 999999949 999999654 -223646324 999999470 999999489 999999414 999999464 468090146 147148328 375136876 999999659 -460732767 999999363 -384189113 999999011 999999034 999999185 999999310 -795261866 999999788 999999422 -135722549 999999455 999999435 999999240 591809028 999999576 -898471564 999999007 435392377 999999915 999999898 999999192 -343577680 999999506 999999356 999999244 -387085964 999999275 689499715 999999051 -864050809 999999370 -698494815 999999249 999999255 -60098692 999999940 -615359428 -308213087 999999116 999999848 999999277 -544474272 999999721 999999526 999999637 999999494 999999248 477576340 619542247 999999257 999999086 -773345950 995082141 999999314 999999205 999999876 999999713 -127797293 -859193500 999999116 -215460647 -677778015 -871131099 999999398 999999644 999999075 999999181 999999554 999999817 999999940 972453269 999999337 999999635 999999524 999999736 999999007 999999164 -28853398 -777794397 575538354 -811154538 999999688 999999999 -72739369 999999790 999999252 999999069 999999395 999999087 999999118 999999297 567507916 999999685 -216149415 -391695745 -188250792 -878743874 999999929 999999218 999999474 999999535 269907583 625110205 999999421 999999993 -191881836 999999812 999999616 999999921 999999349 999999085 999999347 999999211 999999677 999999002 531659632 799699026 -344128284 -51997030 999999380 999999740 999999400 -337266483 999999038 999999462 -697640492 999999482 999999732 -71585874 999999211 -283149040 -125203447 -838381967 999999887 999999074 999999980 -512048468 999999871 999999733 999999716 504252909 711803263 999999727 -516722532 20938330 999999173 999999305 999999916 999999007 268030358 -110865044 -205958065 999999496 999999209 -211171383 856319250 -433074943 239432225 999999889 999999564 815539009 844167670 999999099 679335805 999999656 999999086 999999388 999999365 999999057 999999557 999999637 -608782938 999999802 999999714 -109485307 -462574110 999999782 -526616162 999999242 521950329 999999445 911806626 999999931 999999247 999999659 999999602 626468549 999999449 776858537 999999884 999999860 999999487 -707601546 18452817 999999657 96357100 999999216 999999966 999999192 63340645 999999819 -848248266 -939379596 999999644 -857684369 999999764 999999283 -212912722 999999945 984371342 604292109 999999196 999999140 999999797 -25412029 999999960 999999718 930856415 769973877 999999679 999999852 999999377 773032871 642799434 -805569312 -163319837 999999060 999999902 999999853 999999158 999999802 999999694 999999157 -786226904 999999124 -605697680 999999462 999999044 999999235 999999741 -158598901 976731606 999999272 140490104 999999565 834143385 999999063 -409091931 999999613 -731987016 374719850 -564226351 999999137 999999183 -482437440 999999571 999999085 999999790 -264790605 999999698 151662548 872839327 812645860 -402641749 999999599 -867783808 999999296 999999390 280336031 999999006 999999593 999999085 999999679 999999104 -513984840 -804998232 999999660 999999905 999999575 -892317629 999999923 999999487 446492777 -127018505 867180900 999999637 999999797 999999499 458975429 999999580 999999761 999999210 -848990972 6350171 999999284 999999918 999999118 999999584 999999252 999999277 999999703 -405639923 999999953 999999421 470277996 604563890 -394256592 999999983 999999854 999999609 999999201 800460326 999999016 181667713 724448238 -244129844 999999220 686007809 169833496 999999700 999999466 -289182464 999999928 999999173 999999279 -303596504 -363231716 131540729 999999230 999999112 999999369 999999698 -539406819 287492809 153241515 -356728451 999999027 -507391590 999999355 999999211 999999361 -432479400 999999834 999999033 668328145 999999760 999999577 197799315 999999170 999999728 -369656152 999999923 992474061 999999219 351700399 26749016 999999241 999999873 -632393335 959893184 -273782818 -246673990 999999446 720913917 999999489 999999267 999999021 -298247540 910806471 999999140 709099772 999999988 999999449 999999776 999999430 -158967858 999999643 -58241591 -944830241 999999854 999999187 999999742 358565060 770254783 537800428 -895102995 999999764 184987579 999999940 999999902 999999373 -812078789 561957564 -930899250 662756138 -910884833 999999796 999999486 215959510 999999836 289224080 -100339265 999999655 -693780615 999999929 999999759 999999356 999999067 -916727228 999999856 999999873 999999539 999999485 -815552854 999999945 999999124 999999923 -375586719 999999991 927826020 999999832 999999542 999999538 999999829 999999313 999999535 634682158 -580371353 999999426 999999674 -423621004 -129754532 999999250 999999397 999999983 -525380095 999999648 564979049 999999804 999999897 999999888 508562881 999999186 999999828 999999634 -955370747 999999455 561069027 999999181 399137323 -509132418 987705981 999999933 999999210 -691139457 999999709 799037594 999999106 284642081 -346383273 999999952 -702581936 999999680 999999939 999999141 617188948 836214877 999999361 999999173 629872767 -931269428 999999361 -934380456 999999571 999999439 1000000000 -265570725 999999764 999999449 999999486 -670258853 999999127 185726352 999999125 999999156 999999153 999999073 999999991 999999179 -525148031 999999681 999999408 -772457293 999999070 999999281 999999664 124407636 999999927 999999297 999999157 -979998477 -285157726 999999074 999999304 999999907 162159621 -902947055 999999666 999999238 -498843929 999999290 -609548074 999999878 999999136 999999361 305343643 723018506 999999069 999999480 -61294151 240698231 -962255057 832982885 794099124 968543174 491765937 764135232 497441978 999999117 999999258 999999630 999999362 -305807079 999999874 999999454 999999522 609996458 999999102 999999513 999999922 999999783 999999079 999999562 287715706 999999082 -816002356 -979819049 999999015 -471192505 999999126 670106049 999999713 -832761131 999999446 999999997 999999611 756295189 -269975414 999999550 999999110 999999406 999999399 999999030 999999504 999999475 -916120221 999999465 999999181 999999415 999999342 28755233 999999566 -341409431 999999778 999999390 999999816 -858085472 999999487 999999026 999999473 999999061 999999997 999999063 999999854 999999837 -760518135 -960894916 999999691 999999937 999999532 999999513 922889599 999999812 428286878 999999158 999999692 -452564635 999999381 480125099 872864451 -668014566 290179222 999999488 999999265 999999129 -507120081 194472105 131913236 488661375 997557166 -486307828 999999973 999999389 -14725198 846111597 999999910 360458106 389306565 999999063 999999015 999999740 524280965 503498759 999999515 999999359 999999642 999999748 999999009 999999476 164838333 999999630 999999362 201164139 999999219 999999722 663250738 999999773 999999248 -686976813 372930119 807711258 999999457 999999325 999999556 999999834 999999002 999999990 174679572 -931739474 999999969 999999567 999999644 999999761 999999092 -750088188 999999098 915347704 -634459297 762174361 999999611 999999330 -570288999 999999596 999999242 999999095 -254172974 975942372 999999263 999999350 999999974 999999274 294891105 999999517 999999837 999999057 330376653 -569764870 999999551 999999324 999999867 137476501 -846974608 999999808 999999732 999999256 60498066 999999547 296919004 999999067 999999014 999999957 -396696663 999999807 999999831 999999778 637675328 999999252 11202242 999999619 -103788689 999999662 -491815707 413527575 999999745 999999098 -677439218 -764034418 999999613 193278924 999999203 -967428480 257588312 -417424892 414250621 999999899 999999809 -28916490 999999182 999999596 999999893 999999409 999999139 204448171 999999514 999999991 999999542 999999450 999999942 999999177 999999687 999999845 -254392473 999999179 437030958 14303744 999999072 999999723 999999783 999999302 999999007 999999206 383039604 999999220 999999117 999999742 999999809 -60300159 296636667 999999377 999999055 914127346 999999414 -616744854 999999173 999999140 999999941 -616015290 999999999 891437969 -217771559 -957736121 999999968 999999316 160303389 999999579 999999630 752716784 999999754 999999609 999999097 -194152786 999999744 999999636 999999102 335451023 -936226232 999999027 999999639 314520753 999999628 999999110 999999810 483624777 -535184588 999999998 -135709066 999999786 795609140 999999420 999999110 -12287293 -67675803 -775571416 999999579 999999577 562487383 532183488 999999988 999999255 622206958 999999461 373506478 -676601451 999999591 999999759 999999267 999999289 -838557181 999999416 440186186 999999062 672075916 999999288 999999989 -638757908 999999797 999999030 -917690416 999999838 999999559 999999555 999999076 999999961 442484911 999999725 999999284 999999280 -482154188 334213429 310887099 999999180 -980518913 999999438 999999428 390187466 999999506 557281009 -500660829 999999336 999999685 999999158 999999625 999999955 -238148270 999999973 999999362 999999660 999999148 419245020 999999784 999999793 396707496 999999279 999999412 999999216 999999276 98919472 999999299 999999605 -270931858 999999246 266136220 45493536 177789049 999999737 999999535 -203023815 999999306 999999638 999999889 -121596914 999999278 999999993 999999226 999999803 999999906 999999552 999999347 224570401 -396056085 999999911 681462833 999999433 -193612601 -746439433 999999301 -422836429 999999053 870791413 804731632 999999769 175680997 907697764 462253099 999999182 999999726 999999952 748283920 999999447 999999705 999999259 999999881 -26897328 -288597565 438261805 999999298 -466985879 999999142 552519536 -758200488 450335263 999999856 999999396 -845614098 999999525 999999859 336340760 -205321889 999999189 999999703 999999656 -953654658 745989865 -514842900 999999686 999999543 999999205 999999101 999999804 -488486353 999999141 999999611 -423167526 746804533 999999705 999999310 -602201609 999999478 999999196 -900461623 999999249 -242658501 999999917 -980841419 999999164 999999572 999999740 -429783352 97605072 999999691 999999771 999999502 999999155 999999002 -141408486 -846043569 999999906 999999370 999999244 32958407 672946447 999999832 999999035 999999623 999999465 999999117 -938494971 999999602 999999878 795766572 999999356 232944227 -376172404 59142364 999999924 999999828 999999388 -173409538 999999321 999999399 999999276 999999997 999999816 999999413 999999731 999999334 559419914 55575662 -211529329 999999678 999999877 442924950 271766830 655287682 379253175 -992973729 999999988 999999176 -724447527 -127042445 907015400 999999518 999999103 999999087 999999745 999999216 999999838 -156306083 999999406 484362282 999999010 999999908 999999917 999999634 999999662 999999147 814233427 999999457 999999511 -666083486 49976783 -503307105 999999214 999999191 904672235 999999694 999999356 999999859 105709220 -826975750 606815240 264897972 999999144 999999258 999999473 999999008 110092217 999999447 999999497 325549908 999999727 999999549 -577908337 999999289 999999849 -44404661 999999676 -569955914 999999411 532394612 -291921750 -872434710 -75786854 -37633290 999999154 159656716 -457251465 689515795 -611035038 999999216 -744533394 999999021 -356931991 999999993 648041884 868183067 648918387 -651243250 999999581 999999630 -586063349 999999496 999999239 913014580 999999611 999999541 999999812 578014663 -110277519 999999271 999999402 999999763 -768267898 999999240 999999274 999999588 999999153 999999486 381909495 999999266 114187247 -867597226 52524359 -824436912 999999434 999999243 -731546432 -527136228 999999061 999999964 598871259 999999494 183114374 999999124 999999135 999999771 348179315 -678275895 999999931 999999718 87219537 999999988 900835409 999999289 999999095 456447355 999999273 999999011 999999377 -444085375 999999439 999999366 -467094143 486005879 999999895 -514147698 999999631 999999331 999999683 559592254 999999660 -358079774 901509228 999999195 -542594532 999999704 -696270134 999999003 999999564 999999744 999999959 -130758080 -73327910 621957565 797925079 -296775496 999999801 902949656 999999322 999999718 999999468 -457422921 999999464 2678034 999999434 999999021 197372526 -275837219 -866355344 -170289679 -268202446 -731281339 999999532 999999111 -265802614 -360477728 -98532301 999999217 999999744 999999984 999999220 999999759 -154238007 999999199 999999094 96493169 999999802 -948856878 -460049408 -587669887 999999756 999999325 999999943 999999932 -229821354 999999201 592929303 999999439 999999167 999999912 999999387 541179155 854210353 397468347 999999021 162311286 999999757 999999365 999999055 999999378 130733654 999999969 -741771048 999999903 102565899 999999689 999999822 999999946 479865166 242727871 999999021 999999920 999999366 999999576 999999053 -421507318 999999781 -32394917 999999587 999999636 999999768 -405860730 999999707 71122759 -708464742 999999369 999999139 -685045561 999999883 -783446756 -80967525 999999554 316164716 -534107263 999999421 999999506 999999053 999999726 -799926365 537685920 999999325 972007937 999999492 999999414 620657817 999999567 -138703260 999999320 999999817 -909790584 999999005 -538116329 999999353 999999024 -186392817 -941976867 999999513 999999559 999999805 -48224979 778191285 118537523 999999326 -829870457 316711670 999999805 999999648 999999455 579371726 999999611 999999525 -308702738 -10006158 999999393 999999391 999999881 999999065 999999199 999999761 999999916 999999737 -40942593 -15543632 999999902 999999821 950235557 999999302 999999835 999999007 -523690278 999999133 820674303 999999280 -532562010 999999891 999999587 999999617 999999827 999999653 -113808033 -365469820 124015347 999999987 999999068 999999111 999999642 999999655 999999451 572080897 999999989 999999917 999999482 999999402 999999992 999999093 999999645 -866461805 -169591125 375870429 58249529 999999494 999999408 -97976591 999999711 250505590 999999693 999999470 -252951573 999999885 -309130181 -812140023 999999946 451484660 -754012398 999999170 -852087525 999999730 999999576 999999507 999999908 999999767 -863506448 999999376 999999255 999999429 999999843 611481311 999999696 -769546162 999999883 962717586 -835823910 -231561365 999999412 999999601 -850226335 594997133 999999743 999476718 999999838 -436876293 548752339 999999189 999999269 -647986589 999999124 -79885257 999999591 999999261 999999149 167247187 999999388 999999759 999999780 999999499 806779066 -16344825 -206442264 999999106 -934782089 613737495 543722986 -324400225 -359925718 999999334 999999052 999999345 999999150 -475436553 -579256440 -95932078 999999189 -709163208 -281163816 999999045 -983173754 999999900 999999507 999999025 999999586 999999848 999999893 999999061 39836030 999999725 -630308147 999999794 82215273 692342465 999999553 999999892 -879539101 999999409 465874102 654082216 999999286 999999740 -848414441 999999418 999999416 999999330 999999449 999999261 -842582482 951011379 -341092882 999999100 974402181 999999991 595655834 999999475 999999859 999999092 999999075 999999850 622264768 -154139152 957022052 999999412 999999142 999999914 999999769 600548954 578881220 999999604 999999641 999999558 -878516793 999999537 999999832 605346028 999999284 512373718 -40631978 -229695060 -266578967 -771954934 550573690 999999246 999999407 391721809 999999997 999999385 999999570 999999251 -317736229 999999248 999999838 -644379931 999999106 999999139 999999703 -893033599 999999925 999999537 44305034 999999912 -480033780 999999882 86861344 -309120067 -714156080 -936459972 999999494 999999284 999999253 999999529 -235951480 720331032 999999661 101814417 999999874 999999153 589562978 999999047 999999066 999999473 445260404 -509528621 -776654837 999999742 873659309 -671332411 -721530724 979098092 305407394 999999147 -245130500 999999321 999999069 999999083 999999095 715927683 -120253385 567014904 999999433 999999804 931130795 999999001 999999581 53787159 999999968 227866486 999999450 999999277 -297765870 999999355 999999124 199484314 999999274 869058269 -162247578 999999808 -777018129 886240339 999999529 -882696358 264585776 999999087 999999184 847610941 -265520029 -502289503 -421649306 -87419903 -225557002 639907791 -823245835 999999201 999999386 -656679109 999999200 999999694 999999614 999999970 881921218 999999395 -51333806 -895037663 573148828 999999760 999999829 -567612187 999999426 445493987 119857860 999999025 999999505 999999659 999999084 999999278 -330546705 999999047 -383930258 999999553 -577273842 903425466 518301195 999999554 999999308 999999849 -173515120 350637883 -424806005 999999080 999999388 999999667 658954325 304297695 999999303 -984162355 999999255 999999196 999999644 -360648361 -145834006 -297356901 -173806792 999999879 999999697 453138317 -966129599 999999548 999999485 999999572 413074592 12966096 999999781 999999614 999999486 999999199 999999229 -569489044 999999946 999999752 999999467 999999105 999999305 -962922401 753168132 999999381 999999139 119294192 -945148281 999999428 999999734 999999769 -949168500 -65899423 999999163 999999594 999999913 999999743 999999130 579813911 851195803 186327739 999999233 999999372 859451305 999999539 -3909561 999999913 361208474 -843491325 999999316 999999188 999999056 -476109717 999999058 999999868 999999591 355993987 999999635 999999802 999999756 999999122 597492002 999999509 999999467 999999012 -933964259 -987494398 863036945 999999737 620926037 999999148 -842151690 999999952 999999815 999999843 999999508 639724393 -133067710 999999201 -154088243 228082233 999999323 999999218 999999611 999999475 -970792510 999999923 326187189 999999524 -833248863 36373841 -38702730 -421838011 -365624492 999999206 999999865 -165658706 840043812 -411035756 -277596263 233016584 999999167 152135784 999999038 999999526 751727581 999999092 999999891 633033382 999999319 999999726 999999520 -112750526 999999575 999999265 999999782 328581726 -299501070 999999371 999999424 999999957 999999756 999999751 -669731637 999999085 999999842 999999888 999999097 999999601 999999032 999999307 999999192 999999770 999999755 999999278 999999713 999999440 999999974 999999588 249365998 999999134 999999737 999999973 999999640 -861302576 999999676 713729037 999999023 999999075 -30454505 120382069 999999301 500964817 980779887 999999740 560144040 730228967 -283352525 911567553 -354419316 999999244 -791786444 999999546 999999470 999999319 614833878 999999469 999999064 999999340 999999180 -613215954 91962188 999999938 983169980 999999167 -982933219 999999190 999999811 611455498 999999674 999999893 -274972367 999999029 -476421909 -170446444 -682632473 524190747 999999500 999999767 999999194 461628377 999999431 999999164 999999323 999999973 -465876871 999999723 999999207 667004319 -302339087 999999818 -451222060 999999740 285449204 999999851 424943811 -761892245 999999380 999999922 999999234 999999291 999999883 -458315168 999999805 28756799 999999059 999999261 999999694 999999021 999999295 999999110 999999309 999999139 999999898 999999253 999999956 999999409 999999908 999999998 999999635 999999654 999999846 999999091 524085368 999999763 -224382917 999999360 999999049 146195873 999999466 -461837340 -262366402 -689253237 999999488 999999311 999999748 233157776 -654048697 999999996 999999934 963911744 -274629602 198697125 385738873 999999867 -7567365 999999988 -107143418 328782482 360447016 999999438 999999642 999999606 -859448296 999999987 999999061 35376891 574966514 257169165 999999627 -554217428 999999312 -644373729 580162023 674811623 999999971 999999012 222965418 999999615 -739537292 881761206 999999168 999999235 999999989 77679226 999999904 999999314 999999443 812999001 781839463 7599029 307366944 -737915841 735536722 999999861 999999880 999999641 999999374 -569145579 999999670 -499863137 92209201 999999541 777656576 999999733 999999751 999999955 -172368719 999999253 999999740 999999998 -564451063 750613350 -887363777 -916558549 999999472 -695956746 -921544508 999999476 -865928002 999999511 146792215 -222249576 999999564 -592281257 757946460 999999847 999999092 999999509 -667196278 -690311330 999999889 92245764 559625651 999999946 -776552036 880017805 999999897 999999921 977534102 999999546 999999122 999999541 882241428 999999818 208582013 999999098 999999583 999999147 944271937 999999350 999999269 999999691 999999834 -870678710 29094734 999999994 999999812 -757981652 999999106 999999284 999999236 999999844 -430846038 999999075 999999223 999999024 999999876 666159886 999999022 999999591 999999145 197203152 80349571 179937652 999999136 999999036 285353822 999999387 999999442 999999152 999999547 999999129 999999784 999999468 999999714 999999906 131314008 -522515334 -560066569 999999312 999999865 -107258676 999999161 -743573999 652248718 999999402 999999797 999999531 -62727088 999999611 -966104865 327982793 999999968 999999718 999999040 999999366 -282503075 -87128277 999999993 999999401 999999537 -169223723 999999756 138422355 937913615 999999657 999999586 999999160 999999320 999999272 -601701649 999999965 -99153331 -40545991 -500175472 999999553 -7024137 999999645 999999140 -179193425 999999669 999999134 999999058 999999898 999999932 55055699 999999691 816818599 -858004381 332239032 -18172490 -445645428 999999580 999999555 504408160 999999432 999999740 999999113 483883154 120211099 -556529914 -955068102 -44703393 999999997 999999533 -550905840 999999897 870339945 999999872 999999674 999999385 -772631139 999999188 999999024 569875116 -193961238 999999033 -559635291 999999552 999999045 999999692 999999963 999999850 116928981 999999939 999999977 -975861678 -146840363 999999639 999999853 999999521 999999381 999999214 999999293 999999383 999999027 -708995723 999999251 999999186 216861288 999999142 -255947073 406774088 999999636 999999841 999999192 968676295 999999928 999999216 999999559 999999884 999999115 999999302 463230798 999999271 999999819 954506903 999999531 999999571 882821833 -720241395 999999697 -384043602 -431449834 798550393 999999067 999999027 999999637 -488473665 999999279 326836005 974632289 -770507809 999999418 999999807 -816575729 937362674 999999269 999999128 -713418703 366170053 -324636410 -409758562 999999384 999999787 -443749804 999999112 999999852 712325194 -120079853 634642967 999999231 -563286350 999999712 999999600 999999675 706286793 999999487 5390857 999999766 -283479763 -850949365 999999099 999999760 999999446 999999810 999999129 999999330 999999641 -490824999 999999665 -867835960 999999450 999999282 999999284 999999941 744458115 999999080 999999466 864068506 999999202 -644368781 999999011 999999883 999999108 -478726400 131184471 999999517 999999286 999999456 -628280888 999999393 133469105 999999721 999999172 283737068 999999432 999999582 999999392 999999437 999999104 999999736 999999873 999999532 999999558 999999041 999999629 999999552 999999983 999999752 999999594 -329476009 999999681 999999346 999999679 999999935 999999706 999999918 999999425 999999232 999999044 999999848 -189865913 448392177 999999980 999999188 991017346 499562413 999999636 -61205373 999999030 999999976 601814536 999999205 161113692 999999558 999999830 -439199001 999999485 781515187 999999240 999999521 999999481 999999270 310141815 -305657627 37960025 -636814938 999999269 999999466 -821282151 999999428 999999163 105212459 -548056359 999999201 788337456 999999908 999999155 678568156 999999508 999999306 999999341 -461196025 -866956708 -347906409 978650045 88282463 -108770655 999999873 -153196454 999999716 -261991681 999999186 999999253 999999489 999999684 999999115 856946654 414072939 999999648 999999720 999999118 999999809 999999531 267407962 999999162 -32774225 999999939 999999428 999999193 999999364 -782150209 999999740 999999694 896599855 111777492 13527462 999999728 999999541 333878607 999999546 -516825552 999999258 999999151 999999840 999999465 -827555450 999999872 999999554 -324692280 -590710538 999999309 999999692 999999570 999999165 238509305 488624051 224895269 -298995753 999999638 -484835731 999999500 999999444 999999289 999999732 999999065 999999604 999999136 999999743 999999428 999999572 -793893844 -189768890 999999334 999999584 999999929 -389301936 999999845 999999305 999999807 999999979 999999254 -166384244 999999091 -616092409 363823171 999999377 72315575 999999814 999999561 -473702077 237005163 999999410 999999950 982345597 -730405040 999999484 999999064 -2134125 220306883 999999709 -269353907 999999246 -83207206 999999467 768411830 -538539070 813787882 888969933 999999921 999999708 999999219 999999521 999999274 999999337 999999901 999999975 447029280 999999088 -835811540 999999582 999999561 999999205 159721843 -319321219 999999350 662031388 955842563 525023469 999999814 999999926 999999638 999999611 999999540 -59567675 -866590786 999999950 999999034 999999560 999999986 999999956 999999232 999999447 -484209669 999999636 999999288 999999160 -326112648 999999552 440272487 921348634 -855202856 656205720 999999946 999999799 999999046 -309371293 999999064 999999388 999999194 -473651859 999999135 -60657423 -500632764 999999920 999999752 999999564 999999007 999999835 999999957 999999019 654645384 655377055 -285030758 999999611 999999507 999999306 -5254628 -563733077 82011028 244596948 -198258185 -117342020 143557220 999999753 999999912 -988317003 999999038 -650161114 -585359105 999999619 981640508 999999527 999999791 790993095 999999656 999999752 205230572 409152465 330628998 999999831 -813609082 -947109869 999999308 999999184 -141864118 999999685 578204866 999999178 999999664 999999686 999999206 999999576 330014781 -519708395 -906288110 999999027 649452571 999999373 -9542441 999999851 400354682 423145711 999999415 999999295 528311705 999999635 -249966700 999999370 -993199437 999999781 14726555 999999315 491053261 999999311 999999388 999999754 999999052 -889912976 999999888 999999872 -953527496 -158644487 999999999 999999406 999999160 -197155753 999999012 -870102457 -961435690 999999375 -680037672 480460006 999999168 999999928 -845209642 401123329 999999516 999999127 999999747 999999192 906690366 999999063 999999586 999999592 999999805 999999228 999999966 999999065 999999906 999999235 999999093 379974675 999999398 999999727 999999426 999999003 999999955 999999272 999999711 999999461 -163499578 -320783003 999999040 999999069 999999927 999999118 999999793 999999878 999999536 -310310953 753734179 999999952 999999225 999999987 531289602 999999457 -253222093 -424328786 999999098 999999041 999999570 999999377 900546838 999999609 445052897 999999558 999999716 -905446777 999999927 999999352 999999238 999999061 746589562 999999312 999999600 783040089 999999642 -124478884 -792354126 196909890 999999624 999999639 999999094 -42383832 999999585 999999951 740667617 834043645 999999497 999999254 -142918957 436594252 999999719 999999518 -16149210 999999438 -788621693 999999075 999999907 1000000000 -317437533 999999382 999999008 999999980 999999796 -626296953 999999659 -494096038 729611405 999999708 225338143 658858126 -876582785 161097972 880492225 999999004 -337769333 999999237 92276299 999999930 -894461843 999999359 294685621 999999557 746748828 -853638070 96904848 -274815189 999999630 999999052 -459826893 999999342 999999981 283363128 999999146 999999545 999999251 999999782 554714782 999999914 8698935 999999142 832848303 999999502 762553319 -874785721 400650157 -97863692 999999115 999999659 999999038 -262109049 999999797 -527036447 -367297583 -536131340 999999557 999999046 999999772 999999555 999999368 999999201 999999296 999999571 999999463 999999220 713932891 910403533 -87232792 999999653 -331727991 999999022 999999654 999999024 999999905 999999285 987445961 999999929 410072107 945371820 999999916 999999793 877382965 999999630 999999421 -560611631 999999235 -364991067 999999498 999999140 999999303 753716931 999999183 999999266 999999851 -38883855 557903413 154449817 999999852 999999009 999999454 999999095 -230989673 999999001 999999388 999999088 999999133 999999096 999999510 999999288 769528082 999999338 -343592694 999999712 178644311 -967705468 999999553 999999144 999999206 -824875559 999999905 999999950 999999648 494254544 -397412428 999999658 -213891203 999999619 365128406 999999081 -877191867 999999252 -870881109 -29582067 -849809508 -344731001 999999089 999999766 -810666921 999999649 -772631884 999999872 -271912663 999999193 12946705 999999022 999999764 6159754 999999765 -58807109 999999145 -796533122 982264014 999999513 999999070 690989547 999999866 999999585 612538869 999999395 999999447 999999513 999999933 -978508045 906061921 -701989637 999999545 -125738964 999999008 999999022 999999586 797856843 6964605 67688595 999999266 -716141881 999999332 999999872 999999197 999999538 999999341 974785553 366804825 999999688 999999674 999999271 -604999460 999999374 -893237906 999999947 999999977 -414428765 -64535071 999999581 -186245142 999999036 999999116 999999125 999999738 999999885 999999989 -769730878 -808244180 -924959 74763344 553339091 999999245 999999382 133042714 999999046 999999070 999999280 999999590 999999115 517798376 724379564 999999948 -792042034 999999997 999999213 -209666865 -327513744 338241790 999999751 841472082 -47277523 165859363 999999865 999999392 615178975 999999780 999999414 120616205 999999896 999999820 276357468 395981560 999999207 999999659 722654059 999999600 159300714 -977318287 999999970 999999872 145389949 999999962 -470150729 999999408 999999670 999999885 999999265 999999083 370837453 999999204 999999966 999999195 999999005 561282160 -509122733 -968205522 -558619809 999999112 999999379 999999754 966203413 306312284 -373622251 999999597 716899940 999999028 999999697 999999215 999999682 -834814684 -266897222 999999932 999999344 999999681 999999372 999999324 159925228 999999914 999999252 999999288 691624859 332040676 999999737 65391055 999999161 999999872 334224188 999999648 576903659 53070021 999999730 -113097473 992580859 999999665 62423114 999999692 999999485 999999137 -314628838 999999332 779542493 -515236006 999999063 999999208 -427318496 309940758 999999697 241515424 463380424 999999205 411709956 -229075063 999999014 999999117 999999261 999999615 -305538564 947532185 999999871 999999103 999999178 426291871 999999774 999999976 999999757 999999944 181202290 999999528 999999124 -836983970 999999168 172247851 999999955 999999169 999999164 999999812 999999868 -739576110 999999981 999999859 -954404485 341987521 687281200 999999204 763904833 499160125 999999075 999999703 999999836 999999573 -229538025 999999892 999999255 -840734469 999999043 358725198 999999564 999999246 92633303 999999805 598976578 999999948 999999456 999999283 999999849 -771077790 873504682 999999776 146166168 999999752 999999315 999999967 999999776 999999840 565873986 918763753 999999340 605445309 814437399 999999178 188434001 999999440 999999870 999999795 999999878 999999352 999999598 999999880 999999310 999999353 -381669841 875591608 912121235 680679369 508269060 -386759039 97622638 101340366 999999813 999999511 302057435 999999503 372831721 -560412492 999999423 817028969 999999053 999999409 487004216 999999212 999999996 612250447 999999147 999999523 19840488 999999452 999999103 999999255 999999002 999999863 999999560 999999341 999999785 999999093 349611918 999999433 999999253 999999607 999999112 641043512 999999166 617386297 999999509 -914073887 999999767 721749061 999999765 999999301 746141519 999999073 -483180922 999999119 999999847 999999568 999999915 999999308 999999009 999999447 -52764182 999999874 915122044 999999401 999999127 999999443 554844558 999999598 236430960 686989087 999999849 999999312 869985557 999999948 999999670 999999482 999999114 999999654 -164825917 999999169 999999959 999999641 999999080 999999422 999999933 999999936 999999830 -635307335 999999877 999999443 999999592 -136507848 569723673 999999876 999999924 999999123 999999297 999999717 999999154 750359079 999999507 -261916585 999999287 999999678 -656606028 -622810620 726681465 390707354 999999566 247022489 886344946 999999930 614869064 579805782 999999183 999999037 999999503 999999614 268487309 -160741230 999999789 999999445 999999064 -825629156 -731961239 999999946 527990662 999999775 648174974 -973281336 999999497 999999005 999999205 999999446 999999344 999999804 999999702 999999478 999999248 999999929 999999063 999999180 668940560 931252693 999999189 999999593 45001105 -605394335 794341082 999999509 999999322 178321391 999999505 999999880 -127567511 999999145 -221385530 999999411 999999457 574425666 999999926 -644670957 999999345 999999296 999999068 -537976951 -221823096 999999119 -852903338 -515178750 999999251 999999100 999999544 999999736 999999560 999999871 348272739 999999476 926037185 999999237 999999115 999999474 -737783786 -136931004 999999304 999999563 999999119 999999770 999999675 999999086 999999438 -52181695 999999794 892295181 999999972 999999534 999999352 999999694 999999092 1000000000 490661786 999999675 -505093622 -194552205 999999075 999999937 999999393 -500219548 999999192 999999831 999999227 -109643620 999999584 651636887 999999243 -216994330 395772405 -691720347 999999992 999999038 999999872 999999062 529330420 999999824 999999469 999999101 999999182 999999824 999999621 999999524 966041008 108082158 -767179171 -378904191 -542656222 -603267759 -414510146 -729881265 198045664 66134254 999999725 999999503 999999650 897719734 999999292 999999631 999999646 146265839 -663292936 999999167 999999536 999999803 -380027772 242126075 999999943 999999170 999999783 999999895 538046819 793691770 -26882483 999999930 999999997 999999131 999999565 999999882 327472801 -551051805 999999949 999999007 999999575 999999696 999999631 999999230 999999056 999999566 999999854 999999577 202370490 999999183 257945067 999999327 999999775 642648677 548399552 999999365 999999833 999999549 999999284 -995884259 999999748 999999869 -5984722 928138970 999999483 999999651 -531227850 999999088 999999281 999999417 999999958 999999951 999999828 999999318 627339859 999999017 281034710 999999893 -24056124 -625708175 999999041 728409430 999999988 999999205 999999412 999999071 912706558 885159779 999999092 999999296 999999646 169864877 -10548712 999999451 999999255 800613695 999999317 511859170 -767461878 999999734 709115992 999999919 -128745737 -200354148 -497541007 999999958 999999534 999999057 -670059039 -824820152 -573776447 -231327519 -473039335 999999134 143838866 999999853 999999187 1000000000 999999293 725466244 999999577 358006281 999999144 999999121 999999949 999999770 999999948 944972978 999999283 -586332691 999999751 999999740 999999741 128474657 999999895 -858891566 999999442 999999549 -111533952 -586124063 -909294367 999999953 669052658 999999964 -892311556 -980634078 833116448 999999841 -877045339 999999412 999999071 336027939 320086260 999999167 -620099182 999999280 394906911 -438753533 -882891667 999999877 999999250 21739238 -504413989 999999239 999999598 999999521 999999580 -411074432 999999546 999999527 999999071 -281625466 999999292 999999302 999999739 887589156 -676697208 -361558967 673777693 999999223 999999247 -54942159 999999345 999999708 999999495 999999117 832267406 999999474 747732493 999999673 999999636 999999768 999999417 999999578 999999060 -462317355 -308406789 999999247 999999038 999999523 549230076 999999138 -839963711 999999467 999999042 963830149 999999763 233938557 -274879879 999999306 999999244 682923530 999999231 -329814760 999999757 999999177 74749648 -239830915 999999008 999999420 543379822 140608651 -753256084 999999668 -431281121 -871989676 879963474 999999779 47529387 999999959 999999965 -492819474 999999426 999999280 -804382559 999999479 999999553 999999988 -81848097 999999217 999999019 -577313725 -858153461 999999961 999999780 979832540 -569100817 999999413 7897780 -883036534 999999519 999999936 999999779 999999232 999999397 999999614 999999302 54858183 999999848 -77864310 999999694 999999459 162180819 999999584 999999128 -77204036 999999428 -714800072 999999629 999999746 999999910 -708983603 999999364 883460428 -480491398 999999634 -230726209 999999007 999999986 999999668 502922184 -531545462 -439080985 999999349 531146067 115455263 333100798 999999673 999999541 -676076757 -883284155 556763865 999999122 516932400 999999159 -878230463 999999853 999999937 999999784 999999638 818989503 -452144448 999999148 999999433 999999542 999999829 -115084469 430776347 999999053 999999153 999999855 999999423 7550428 701399073 999999196 999999883 999999334 999999909 999999854 -571875381 999999361 613744657 539634964 999999073 999999745 999999503 999999363 -502692920 999999279 999999942 -747895643 887037452 171129754 999999254 999999162 522815383 -631208591 873923433 -474419175 -336100133 -842737327 999999107 999999747 -246986364 999999007 -899455925 -782114117 999999882 699640641 999999576 999999498 353681576 999999869 999999720 981481218 999999851 999999591 999999830 999999060 999999938 -270201888 999999104 999999505 133566319 -771344760 435581568 999999617 999999365 999999668 -18109165 88795154 999999692 999999153 999999688 999999235 999999947 -666486470 999999945 999999654 999999421 94771707 999999493 999999982 999999561 999999503 999999806 -31195173 250418288 71389939 999999894 999999441 999999148 366893827 999999218 999999779 999999432 999999680 999999121 477636220 -678831353 938029245 81602157 999999686 999999585 -780510517 999999514 999999927 999999556 919198350 999999544 202547921 999999914 430190285 999999736 999999871 571553210 999999554 -845561591 36835691 999999260 999999075 999999842 999999631 999999365 999999455 999999906 999999823 -65411615 999999005 999999531 999999294 999999483 999999149 369476919 999999586 999999452 998560522 999999299 -633577683 844066208 999999561 341367253 999999943 999999932 999999739 526248443 999999428 44930814 999999345 -190216542 212675808 -951249391 999999850 999999424 999999590 999999836 432496920 259963459 -634647156 -280105781 999999446 -490059718 999999345 999999404 999999692 -688279042 999999029 999999296 999999271 341923670 -285113843 639458819 -179573688 -721750415 412981224 -59669187 86572604 999999184 999999652 999999629 504607612 999999181 7052067 360167606 303183799 573054663 -198486126 -607812397 864299722 999999879 -240749589 256703310 543256775 999999297 999999170 981612518 999999275 999999920 999999833 999999282 -677253193 -911534761 999999019 -316883009 -613439801 -586766297 892308928 999999162 -915637609 -595292880 999999395 999999529 -801747702 951032061 -311774831 -586656328 999999408 999999984 999999018 999999427 999999692 999999619 118578148 -831232710 999999461 999999321 999999571 999999215 758903569 -471413474 -269481359 999999716 999999347 999999262 999999020 999999847 999999146 999999315 -786707705 999999931 -893069210 999999219 181724241 999999276 -811424666 999999665 999999064 999999779 999999608 552065498 999999482 999999893 196114787 -26187162 999999145 999999299 999999442 999999608 -628818689 999999367 427602344 999999184 999999666 182546759 -968715876 11676897 999999843 999999841 999999049 999999377 999999162 -507018913 132937029 -138008294 999999124 999999694 -160483219 925025912 999999527 999999223 -149050107 999999082 998164484 999999157 -640666409 999999825 999999992 -748322919 999999488 289915817 999999550 -425607675 999999272 999999219 999999420 999999998 -417527398 999999458 303203128 999999007 999999997 158395348 231355271 -458993809 999999639 999999721 -971930081 -895760059 999999972 199120751 321415045 999999859 999999103 91550964 999999510 999999303 -890943911 999999061 999999170 999999897 -389529701 999999374 999999016 999999657 999999032 999999935 999999832 999999608 999999882 999999876 999999308 999999473 999999697 -472622518 999999359 730468724 -792277303 999999350 999999733 999999585 262332359 999999945 919993147 999999347 999999652 999999337 999999011 999999923 876097059 999999632 999999289 -597472493 999999278 73529755 999999693 999999208 -592336575 -510709344 999999915 -517749049 999999956 999999246 999999042 999999403 999999120 999999888 499995077 -337553143 442326334 -190243568 999999445 999999267 -696206371 999999605 999999882 -864262616 333080170 102216597 999999432 999999400 288797404 999999862 -499514769 999999101 -935679937 999999752 999999411 309742844 999999704 999999706 -999156589 999999892 999999283 999999451 999999026 999999415 999999989 999999217 999999220 999999568 999999607 -90436097 999999908 -115900402 999999899 97496062 -543596343 -300052606 -737703608 999999745 999999530 999999617 -129025288 999999382 437895824 -95448757 798134346 999999624 -184651367 180872339 970286851 -599659210 -773348944 999999396 999999985 999999909 172788439 999999777 999999025 999999685 999999643 -164398140 -51413893 999999126 999999672 999999361 999999431 431159922 -459568689 -636744122 849198007 999999880 588773293 544140153 999999634 999999032 450755401 854808156 -212658355 999999706 740868689 999999940 -399851134 999999194 -701020495 999999015 999999344 713745978 999999993 999999111 999999851 658879528 -641462333 -672550459 -941942043 999999181 999999027 999999304 999999537 432246909 173250573 217116230 934375004 999999160 999999834 -805974313 999999346 999999501 999999798 999999750 -257822072 999999458 999999511 -95385914 293057580 374213395 -926060231 55760817 999999137 532187572 999999130 -627016528 999999759 999999140 999999009 795290345 999999837 158995560 999999730 999999820 -991434232 999999221 661535963 -491538182 269876533 999999813 355520833 999999094 999999708 999999876 -689737446 999999738 962611184 -354675855 -289711510 999999901 999999402 999999843 148747664 999999293 406910160 999999279 999999801 999999679 999999728 999999134 999999752 999999637 999999153 710799901 999999839 -983702919 999999245 999999445 999999809 999999703 999999518 999999759 999999381 -907164070 624571729 999999574 999999493 999999829 999999513 999999143 999999259 999999268 999999923 999999865 999999868 999999838 999999089 999999546 942749152 999999738 999999988 -907059243 -570139512 999999526 999999059 999999211 222613159 999999727 -286868853 999999778 14432826 999999359 -476329532 999999239 999999393 163172607 354558073 357028237 -869595397 999999648 999999880 -129263058 999999261 999999352 999999836 -247333704 -814687542 733233772 999999023 999999805 999999954 604470936 999999587 -415832729 -474136310 999999637 16461661 737652868 999999353 -99447031 604265272 629252917 -984059261 999999090 999999864 -201879485 973829913 424267547 999999422 999999846 999999762 999999936 999999782 -966240962 -332175322 999999662 999999872 -380177210 -8549007 999999381 999999592 999999345 999999962 -673824351 999999619 513950901 999999587 999999983 940668330 999999174 999999457 -793415487 999999658 999999254 999999295 999999949 796180415 999999753 448276536 -146502758 999999738 999999485 999999574 999999012 999999854 106789139 945209390 999999767 -778448037 999999295 999999506 -14629497 999999184 999999383 832775431 999999055 999999138 999999349 999999072 999999542 999999399 999999481 999999843 999999568 97105437 999999516 713970359 124685605 999999289 999999108 -683627469 419194332 999999406 999999117 -942223087 955894057 999999962 999999684 359336826 838616959 999999873 999999850 74503827 -713056260 -375178692 999999969 539929941 195840775 29881195 999999623 999999551 500239956 999999730 -809498960 999999423 411019742 999999206 722646331 999999354 -32677458 999999714 999999701 999999346 999999272 389995662 568463721 569460736 999999088 999999753 999999222 999999947 -522730991 809899418 999999996 999999697 999999373 999999568 999999716 -497602322 999999758 -210065603 999999862 -392666041 999999592 999999246 388574094 999999135 921028142 229324652 999999563 999999645 772815785 999999271 999999894 999999387 999999403 19235867 999999871 999999738 999999073 268876112 999999890 343877442 964170072 883724545 -856615538 999999355 27023781 -294024808 999999022 341985794 999999649 999999533 -223029055 999999890 -109084052 221688802 999999344 -727537345 361309932 999999700 -116502677 747913401 999999619 833342001 -945103572 999999634 999999972 -465309967 999999648 999999006 277760710 -148258851 999999842 -597663769 999999560 -355546262 999999955 448111466 -2838128 999999059 803437020 999999396 -134836428 999999777 131538310 999999450 999999715 999999730 -759861863 999999621 999999521 999999769 999999383 999999554 999999679 999999060 -511584667 999999705 999999999 999999072 -363618925 999999202 999999774 999999923 999999288 999999939 -101152355 -214770975 -983916545 999999037 994249594 999999298 -833785679 999999958 999999062 -194446595 999999821 -584142020 999999711 -859089213 567378734 999999384 999999628 999999935 999999316 999999770 94868446 999999033 451211873 999999674 999999069 999999643 999999504 999999178 999999408 999999400 999999159 999999388 -28803393 999999596 999999651 964869160 245875555 999999807 48145209 -584427899 -129914204 128580881 -38682647 999999287 748036491 999999248 -542821830 999999095 999999517 999999186 999999212 999999586 999999495 999999220 -914573083 -219428932 999999951 999999157 999999198 752452713 999999705 999999357 999999237 999999489 999999643 999999629 999999024 586574480 827550088 999999173 -440672174 999999013 -490736755 999999327 445082113 999999043 -335623956 999999018 999999825 45675347 -929953989 999999020 999999728 999999546 999999541 533436084 -254664657 -916976692 -795631778 695955813 404739739 -495498251 92054241 581550996 320327764 -926366846 999999391 -351710849 999999054 664902135 999999718 999999916 -147958399 999999271 999999495 999999235 -990036814 -905699034 610337018 999999073 -309846311 999999639 999999271 999999222 313160146 999999583 999999931 -757921069 -128350705 999999247 999999441 999999432 999999951 -910907332 273883978 999999180 610984330 768912671 -621082846 999999666 -245131099 999999765 999999890 999999625 999999396 999999440 664424235 298358762 999999589 999999702 999999192 999999909 999999431 999999087 -246254662 398863543 492599082 999999676 999999864 272265236 137474920 999999732 -545211862 999999711 999999818 999999824 996455336 999999524 999999773 999999915 -78389001 999999777 74935340 999999424 999999554 999999168 999999271 999999547 999999679 -681183034 999999119 999999626 999999597 999999532 999999058 403740895 999999727 -805718652 -741004197 999999752 999999304 999999141 929313495 710198157 999999786 999999906 999999648 999999550 -86995588 999999379 999999619 -512720363 999999124 999999509 999999864 422457647 999999249 -300065122 -491302659 999999180 999999684 999999548 999999688 999999245 -754200711 999999643 -146019025 999999601 999999246 999999592 999999571 999999318 999999741 999999923 681241132 999999220 999999362 687221309 -548747716 264674192 999999134 587046852 54343310 -920904427 -85252461 571471996 -938826419 819795962 999999856 999999201 999999226 999999695 753401984 -627809193 928946453 -732051287 -570851559 999999048 999999675 999999369 -264192027 999999597 999999637 -372998044 999999080 200271380 -495985737 269760915 999999490 999999210 -134345653 999999547 -961577718 -823327156 1000000000 -376279227 -590050324 -213815012 999999170 557551452 -344647901 -496943315 999999627 999999627 999999961 -955899009 999999319 999999771 999999373 999999115 999999578 999999666 999999089 999999190 999999799 999999472 999999101 999999795 -688130593 -410715407 999999957 999999672 999999964 999999788 766303502 999999049 999999804 999999637 854000982 999999885 999999657 999999041 999999294 425290009 999999770 999999400 640741643 999999846 999999132 -646772133 342910876 999999330 999999087 -394286897 999999672 999999453 999999433 214081032 92344039 999999221 999999374 999999041 999999319 -780037427 -908440314 999999772 -134598154 999999099 -277908626 400894596 999999469 999999029 188690517 999999968 -748595747 -578214453 999999802 193399487 671566685 999999851 999999542 306736879 999999261 455126248 997746069 38350512 442729055 414592909 999999424 999999833 999999750 999999794 -894966470 -906299256 999999328 -515607266 999999902 999999863 999999197 -458437102 999999173 227049716 -460662429 407279168 955675685 999999858 999999584 -384798801 999999311 552998336 999999019 999999384 670677967 999999721 999999967 195692677 456814524 999999819 999999129 -61338255 999999598 -998944198 999999481 999999177 -249068325 -221070892 999999653 999999538 699965796 680765395 -588992210 -81271461 163523932 -164352364 -697737420 999999431 836982339 999999519 999999350 999999125 999999923 -78678904 999999759 709527437 999999127 -173193557 999999361 833676227 999999246 999999080 860394205 999999272 999999546 999999101 -813141755 999999168 617085175 167510952 999999315 999999304 999999973 999999287 999999164 841911218 999999185 266319369 999999719 999999355 498673130 761127924 658613059 194953784 999999351 803031641 999999141 999999444 -103017104 -677161861 -655601765 999999767 999999831 48395050 -491134970 999999780 999999873 999999622 540100219 999999479 999999987 -180245653 585686548 257082693 -629052900 999999949 999999640 999999738 999999939 -180256502 999999118 999999767 -587114565 999999222 382332187 -270737390 999999242 -800400121 999999081 999999079 999999499 650418075 752089091 999999117 999999101 338701521 999999270 999999249 514667549 31737733 999999207 999999612 999999989 999999729 -538484561 999999835 999999285 999999065 -921240142 999999128 999999337 999999728 -716014139 999999581 -417468718 999999133 999999955 999999966 893515533 999999900 999999113 999999876 999999194 999999246 999999014 999999525 999999899 999999206 999999263 999999361 -654501706 999999319 999999231 999999961 454587453 999999261 -922101725 999999624 -19119921 999999241 999999193 999999574 999999767 999999094 999999931 999999251 999999407 999999431 -460325851 -735447252 999999310 999999126 -263536942 -700106332 999999657 -536645226 999999120 999999649 -165673847 981845885 999999686 999999639 999999839 999999729 999999419 990341487 999999571 -560587789 999999788 999999008 999999057 999999030 460206805 394601679 999999345 399618897 999999115 465747067 999999791 649848816 -376377467 555143804 999999342 -176389332 999999552 138610946 -105362281 575768219 999999206 999999716 999999719 -313433866 999999185 999999422 -188410245 999999446 -370774406 999999866 999999936 960924876 999999571 999999258 999999287 -865482617 999999078 999999375 999999977 999999848 964800949 -449058663 999999922 928820827 999999982 999999608 497326107 189599820 999999053 57420749 999999447 257363386 586156738 999999783 -730646455 463178926 999999712 999999432 -374060984 999999145 999999819 999999083 -484790826 999999223 999999017 999999813 395026810 999999037 -794360443 999999592 999999074 176287201 785291452 999999918 999999391 999999158 -136917666 -20150352 999999475 999999447 -294150397 388336193 999999142 -869702024 999999170 999999091 999999114 999999934 999999205 999999520 999999758 999999693 310212327 -795152453 999999439 731050833 93457454 -828529989 999999845 999999571 999999735 -536786695 999999890 999999750 999999092 999999462 999999644 999999902 -988651021 999999517 999999924 -470835624 561410396 566390663 999999989 999999570 -252967775 999999822 653974337 -447232651 -177789126 -911646337 -487299310 999999830 581739782 999999665 717150466 999999470 999999959 999999158 999999670 999999934 -859968705 -746552580 999999950 999999830 999999384 990011110 999999343 999999335 -86006503 999999768 1114869 999999360 -964470784 999999217 999999142 689750129 999999969 999999290 999999250 999999743 999999071 -611452016 452103266 999999582 999999034 281469047 999999783 215883271 -913310279 999999617 -628032232 999999548 999999089 999999322 859818849 999999739 -712661464 227916690 999999684 880617694 999999025 999999190 999999681 81143385 999999491 999999200 999999021 999999883 999999820 999999802 347338217 999999008 999999750 -585789896 -526036199 999999266 279398536 999999838 -617339880 532870890 999999892 -127148911 999999427 -730473078 -500531480 999999894 -201684337 -406118618 999999947 999999757 999999667 -426093487 -714902149 999999491 999999213 658847103 999999386 -551672958 999999575 -391509304 999999658 999999779 999999833 999999083 999999805 999999358 999999587 999999674 999999334 999999262 -371206969 999999679 -13610016 -594574438 161635370 999999030 503153321 999999498 999999881 -793732262 546479743 999999350 -210634309 999999985 999999087 763065821 999999491 999999911 333993544 18849579 999999019 999999639 280980383 999999975 999999913 999999591 107713431 999999648 -868173543 787857854 999999592 999999436 999999339 729018719 999999583 452900344 999999600 999999077 303849807 94568262 -736548156 889754834 999999582 999999773 999999671 999999206 999999044 -197821376 999999375 999999325 999999890 -739075706 19837348 999999522 999999283 999999507 999999586 999999844 -152076323 999999071 -178587370 999999291 999999262 771202971 -743248467 999999175 271691427 94234890 999999818 999999052 567883869 32821843 -141154690 705569637 942064034 -969391327 999999846 -224685661 497322896 999999961 999999926 999999318 231081156 999999399 999999766 999999519 16134804 999999869 -14655900 999999428 -34292686 -901252883 -888013728 932984432 -364343293 999999342 999999720 -78016381 834031024 -676936013 999999840 -760984521 999999100 999999192 -435453263 999999983 999999281 999999446 999999760 897946872 430384275 999999958 -413004870 999999833 999999678 999999883 356788088 539668915 999999775 -806626109 -316190891 999999814 326117319 -570402432 999999859 999999286 661515715 -205157960 999999332 999999676 999999503 999999753 -263090213 535730181 999999468 -351642164 -782393269 999999117 999999202 -794433556 -76973615 999999591 999999891 988935885 999999580 999999643 999999268 999999500 999999086 992004974 999999397 999999101 999999469 999999239 999999901 -972583472 999999452 999999050 999999638 -220512552 -587723664 999999178 -258957875 999999364 999999670 999999479 48279169 999999099 999999839 999999012 999999122 757976802 962466258 999999952 999999157 999999897 999999439 999999281 999999500 -748876354 658274261 999999219 -808621894 999999116 999999505 999999330 120995888 742466388 999999268 999999883 999999226 999999248 999999031 259065570 -298675434 620991316 -879690313 -17005691 421913751 965602110 999999046 999999412 999999831 999999705 999999044 -205085267 -259817377 999999968 -797101119 999999754 999999119 999999759 638823689 467150182 999999336 999999312 442921859 523577517 999999015 999999971 454527871 999999277 -179331643 -169683602 999999623 760943650 999999147 -417374902 999999659 999999480 999999071 999999843 999999112 679974707 999999074 999999846 999999765 999999785 457048994 999999853 999999739 -785769363 951702947 641152140 721673351 -838896789 999999373 -119764705 999999265 -710759685 755807851 999999973 999999869 906239257 999999383 999999307 999999942 999999828 903708650 -953642185 -532571918 999999184 999999819 999999798 999999407 999999531 761712654 999999210 940704856 999999074 999999797 299785097 999999794 999999713 999999974 999999953 573614384 999999517 18233629 999999928 999999675 999999004 -872642620 999999557 713694503 999999573 999999771 141474445 932219207 4286795 999999651 999999377 939662606 380632755 999999712 999999588 845085847 999999360 999999957 -724701732 999999764 999999465 -236850059 999999160 229486099 999999245 -723402657 999999834 526357805 -662122276 -523147830 999999576 946436477 999999727 999999142 999999672 999999696 999999518 999999674 999999234 999999301 850915140 999999053 324382184 569091259 999999686 999999971 999999137 999999309 -735489882 999999740 999999176 -651920955 532478937 999999718 999999916 999999982 999999955 -562133224 999999875 999999934 999999050 999999744 999999461 318218709 -196484299 -682218625 999999689 592313179 14561634 999999830 999999336 999999196 999999914 999999216 999999860 999999941 -20432716 -371730104 999999007 999999863 -140200012 365546251 999999005 999999930 24970132 -157629351 -844628468 878913841 999999009 999999826 999999698 -13426640 816260702 999999727 999999789 -73708560 640463871 369864561 -164289196 952420794 131576182 999999245 -799613651 274473754 167790574 -935244344 461354791 608973656 999999690 -833806096 -825893534 -546343305 999999645 999999363 475077423 -502025787 999999811 999999947 -59581321 999999302 -792156467 999999923 464830941 196218342 999999522 376232517 -441476163 999999593 999999829 999999832 914355882 -788353298 -822195518 540506373 999999295 999999201 295337483 -840381606 999999570 999999831 999999481 549635380 -173012020 999999308 513611888 999999827 999999770 999999532 999999024 205982864 706156054 999999594 999999913 -495510190 999999456 999999390 999999259 -538272388 999999599 999999562 999999055 999999044 500505400 999999911 800183340 999999732 314678931 -108754833 -410429051 999999865 -373090257 999999687 -970137372 -313419308 999999920 999999334 541734190 999999216 999999089 999999212 926102233 999999488 -682525238 999999558 999999834 999999061 -938597609 -837441311 957101447 999999567 999999242 999999551 999999735 999999331 999999488 222743455 -169753081 930013321 999999458 999999780 999999021 218331958 999999097 -203353536 685108203 999999871 14603218 -914563292 -270758822 999999237 999999064 999999691 999999063 999999859 999999366 999999593 -226138290 -538042336 999999224 276204024 -599197649 86603461 999999563 999999951 -796536182 999999783 999999606 999999250 999999807 999999256 -504366436 999999644 -202032330 999999028 999999161 999999091 -367593007 999999668 999999460 999999473 999999758 999999714 999999076 -176601421 -540331080 61109230 999999626 -618506034 -726180676 999999301 -550735120 999999149 999999774 115261428 999999747 278882602 331555261 999999159 999999792 999999820 999999083 999999992 877070715 990283424 999999713 -256235510 999999201 999999296 -388315279 -157267865 999999820 999999309 999999571 -428237979 591219293 -242463500 999999527 999999563 -110909320 999999809 14851513 999999684 879003921 999999157 999999907 -245899766 999999617 999999882 771831650 999999443 999999778 809175907 556490106 -538023663 999999297 999999273 999999906 -975844099 52644867 999999873 999999059 999999174 999999521 999999947 -571074578 999999089 999999390 999999178 -662900946 999999862 -960280240 999999913 999999999 999999009 999999214 999999337 999999069 999999581 999999123 -89505797 251244869 85917696 999999630 291916388 999999012 -751336795 999999751 999999751 999999807 999999742 -437802269 999999672 -181249879 -381982553 999999438 999999734 999999596 -649369559 -822746837 999999988 -784149296 999999640 999999196 999999195 -618700181 716764385 -257979153 -70426969 999999846 999999822 999999178 -749046812 -618884452 999999357 999999973 -833210503 999999476 999999515 999999446 999999393 -216933530 55051103 999999367 999999051 999999169 72139812 932301918 999999894 198396373 999999557 716211700 999999049 999999632 -966350782 999999579 999999429 -599589669 212723450 -919858047 999999456 999999028 -501692943 810380447 999999211 -232900307 -805811425 -276956490 999999456 915184578 -786859017 900023874 999999065 -516443774 -502291457 -847437974 999999824 999999714 999999770 999999452 999999461 -910123273 999999380 251358550 999999908 999999716 999999763 999999152 999999815 -377492816 999999166 -446996194 999999756 999999414 999999457 -70759845 609979442 999999056 -979254137 999999593 829276073 -706723224 999999025 999999015 999999201 999999448 -926895007 -466877624 497124119 -36439459 999999044 999999667 999999849 999999134 772549449 999999005 -31996459 905010403 999999268 999999685 999999941 999999761 999999365 999999584 999999335 450532679 999999290 999999795 -550961019 -840660917 718531811 -75713264 999999645 719616222 999999236 999999853 999999821 26539855 -574976286 -514169183 -417679006 467917181 999999212 999999019 389041049 999999805 -726801991 999999131 18474050 999999283 999999564 82939291 999999729 835682551 999999212 999999467 -25771640 -271165744 999999503 999999109 386689547 -577404406 999999939 748932463 999999515 999999323 999999362 918974927 999999432 999999906 980296891 999999767 999999898 999999458 -592214011 -736871849 999999111 999999573 -518814824 999999559 999999061 999999770 999999306 999999620 999999156 999999146 999999366 -946073233 999999276 -464063417 999999589 999999398 999999619 999999412 999999720 -163340950 999999489 999999122 -354213159 999999310 999999039 999999132 999999934 982890266 999999172 999999264 999999893 999999885 999999543 999999976 999999240 999999379 999999798 999999276 999999165 999999710 999999915 -506783889 358132571 999999950 -624419712 999999900 -666512425 999999363 -174587188 999999599 -532370426 -822576130 999999915 999999155 -539126765 755429458 999999988 999999167 999999201 999999065 -874925910 999999534 -595531993 -649522283 999999780 -573027404 999999506 -968725708 999999729 -589865023 999999754 -194162816 -665390856 999999490 999999577 999999347 999999897 999999983 999999643 999999284 184774963 -943875829 633489166 999999688 -899132185 999999293 724777241 902045688 999999422 -318220938 -970817984 999999209 999999110 -152639930 999999635 -572659257 999999356 351797860 999999301 999999557 999999580 -306391315 -764783828 999999512 999999114 214263285 -632730119 438151910 -574448656 999999848 999999508 -722527191 823610580 999999166 999999318 999999727 999999657 999999821 999999165 999999204 -217278909 999999354 999999923 -99186165 654470860 999999719 999999568 999999889 999999977 999999689 999999248 999999293 999999671 999999750 999999769 999999871 999999770 850462883 999999851 370275403 999999706 999999685 999999369 999999422 999999052 758915343 999999363 999999436 999999417 999999654 999999125 999999535 -478024196 999999717 -931135465 -665628715 986285930 999999102 999999420 999999262 999999854 -732585090 -515217380 999999597 999999908 -568482185 999999733 -352275299 999999566 999999710 -251828755 999999905 999999882 999999889 375751869 818565162 799753479 999999111 999999065 999999550 -55367678 999999663 -523561075 999999707 999999058 -984417705 999999669 999999553 999999951 427414693 999999380 999999245 999999338 999999818 999999554 -753813801 999999469 999999561 999999020 -847196230 -975068937 999999328 938524611 999999732 999999861 575608110 795033331 83692828 999999256 999999687 999999312 999999716 999999660 999999413 999999728 999999333 308612993 -606097574 999999887 999999154 659518815 -960974974 999999303 999999776 96562155 999999420 4927595 999999823 999999995 -252789371 198289506 -670802410 -667256333 999999871 190208564 999999449 -308544266 891756589 -282304558 999999682 999999690 999999399 999999456 999999813 -969598553 -939249085 -97454171 999999365 -300755591 921550765 999999645 341454031 762175520 827301542 999999493 999999539 999999368 217394098 -283247037 999999184 53545068 446246951 999999291 999999006 999999904 999999132 999999012 999999469 582311795 357507742 999999329 999999729 259780748 999999478 33403074 999999037 -747787205 999999283 -60387884 999999996 -843590680 999999077 105841507 999999097 999999803 -820958153 999999931 999999721 999999624 999999986 999999700 999999311 999999843 999999041 999999735 999999984 999999953 999999332 -635672303 -200821980 722132788 999999580 417445298 999999741 739021747 -979242191 856742401 999999996 999999462 999999621 807800619 828857987 999999022 999999244 309092721 -866672356 999999445 999999994 999999800 936232329 999999721 999999927 197212757 441988056 -985823571 999999535 999999675 999999504 -467455748 -391496594 -517614663 999999313 999999343 999999102 -519047494 999999588 633952216 999999443 999999303 216742193 365318789 999999534 999999425 -12919833 464696386 -26042793 999999200 999999985 999999693 824879572 999999836 -460520207 639986441 999999403 999999714 999999018 999999081 999999748 999999229 999999029 999999821 -349335684 999999044 999999310 999999579 -648920533 999999933 384200493 -314913965 999999094 999999599 999999272 999999664 807103796 999999008 188672014 -642762907 323654226 183331770 999999724 -72316570 999999231 -363924254 999999336 71169591 999999604 999999429 -835310766 999999072 701682802 999999466 744170723 999999667 999999396 999999479 270853919 999999323 999999648 151046060 999999011 892041377 999999316 999999006 999999689 999999900 -310744663 999999128 999999430 823545128 999999365 999999893 999999268 999999508 999999179 348966059 542569676 999999458 999999820 240692887 -56725810 999999409 405997054 999999499 999999668 -745893991 352059641 477763037 999999730 -443767727 999999504 585900694 999999348 828409794 999999522 999999682 732606872 999999241 999999208 -245569615 999999020 999999919 999999778 999999859 999999566 999999696 -56467891 -526530872 999999775 -465465189 318244653 999999641 999999457 193985135 -407959960 374989729 417610383 999999319 505472631 999999582 999999190 -15822629 999999737 999999822 999999908 -188388901 308522226 999999398 999999514 999999868 999999391 593743186 900426026 999999422 378676657 999999284 -792829369 73888704 -141372262 408935664 999999117 999999103 999999153 999999377 999999122 999999858 999999127 999999051 999999650 308862001 999999134 999999056 -591935828 999999426 999999256 999999554 999999742 999999047 999999775 999999435 999999187 334604010 -89908044 999999967 999999826 999999002 -256260192 999999472 999086501 -417659028 999999807 367217272 999999474 791526998 989801466 584292127 -279971189 999999026 999999981 999999997 999999457 -394695153 999999191 999999232 999999347 -391029911 999999759 999999666 -130883929 999999950 999999779 999999790 -741090797 999999465 999999807 999999338 -228330964 -500886442 -863414769 688686589 999999756 999999945 -262683231 999999529 999999503 999999767 999999539 999999868 676917599 999999848 999999908 234999706 999999542 773521861 613907829 999999776 -853042092 999999359 999999843 -55499779 999999854 999999896 999999496 999999028 999999681 243073310 999999525 -961859866 999999209 -582622035 999999852 871641784 999999584 999999864 -223502749 999999636 999999717 999999813 999999729 -275924683 999999429 326404749 999999799 999178969 924685864 999999926 455084409 999999229 680907552 999999864 999999737 -885157346 555843897 537002860 999999154 999999305 999999535 999999445 999999631 999999887 999999273 999999245 999999524 321991885 999999271 -142891451 999999904 999999720 633086479 598474763 999999264 999999217 356861657 -531496978 999999074 999999967 278380722 999999678 238902928 999999445 -751554036 999999081 999999681 999999892 154273723 999999956 999999340 720500197 529857635 -237961806 602280852 999999646 999999440 947599230 -637961664 -637590732 -827289659 999999707 999999818 -294809270 999999266 999999742 -736126513 578758038 -275241149 724785474 999999318 999999054 50798366 -339871445 -266689201 999999606 318071456 937564895 999999674 503200122 999999904 -831764848 999999394 999999214 -668413914 175024396 -518600672 228082252 999999243 999999002 999999476 999999282 999999109 825642578 999999456 999999772 999999265 999999478 999999415 404997275 810813415 -888093686 999999450 999999299 999999902 999999352 999999471 999999125 999999196 999999676 -375439856 999999683 999999572 999999732 999999409 999999930 999999717 999999252 999999173 999999921 999999160 -550110732 999999674 -585411612 999999735 358071182 999999051 -47009439 -511690907 999999687 999999977 999999384 363809125 999999219 -269544300 999999448 162413037 -249008473 999999013 65067454 999999170 999999749 -563611089 999999405 999999181 711683877 999999288 999999375 999999691 -228160676 -546820721 -471180426 999999083 -722320234 703065663 999999557 999999985 -642276233 999999245 999999963 999999229 -167377104 999999414 999999882 -783266775 999999421 999999193 999999664 999999484 -861037541 999999409 899027147 999999586 391948578 999999090 999999480 169643379 999999338 -950406287 282422396 584714676 397203373 999999676 -640478184 999999459 999999181 20612435 -162539154 -923045327 -115444928 999999480 999999168 999999610 -896847537 999999157 999999801 999999493 999999920 999999273 999999198 999999371 982372744 999999588 -989268968 999999400 -658939520 328577794 786441510 -114619848 999999329 999999167 999999731 796247807 999999563 999999207 999999428 -788282020 999999509 452933720 783401760 575316226 310580742 502558762 999999600 688734891 999999520 -268424384 999999521 613183595 999999618 684542913 999999575 999999139 -798891475 999999999 -114397863 999999642 999999398 85365550 999999880 999999340 -209071377 999999292 999999907 999999351 999999971 999999380 -698235264 999999237 349322941 999999411 999999963 999999295 999999255 999999977 999999754 999999689 234161592 999999766 999999792 -724032647 102140413 999999807 999999136 999999044 999999133 999999348 999999457 999999273 999999195 999999407 -758192016 752032117 -588198804 217978102 999999916 999999851 999999261 999999098 999999313 999999471 -928612964 999999058 999999813 55184686 999999688 66849379 999999902 999999518 999999679 769700847 92692550 -544902285 201165159 999999751 -875656801 -595745763 999999192 999999039 -885529404 999999341 999999533 315513680 999999490 -852634943 41360415 999999500 458703804 1000000000 999999513 999999753 674833532 700551077 568594924 999999122 999999420 -754982310 -437011539 999999184 648508159 -71583257 999999987 898382624 999999348 999999730 999999567 999999958 139812801 999999067 748504781 763897420 667996302 999999187 890808549 999999419 999999912 999999138 -67163878 999999236 999999895 999999049 999999749 999999373 999999059 -767646413 999999084 997013390 999999887 999999040 999999346 -331612619 999999640 999999639 999999226 999999491 999999448 999999622 -267634542 -257441678 999999296 999999482 999999339 -220953748 -727368694 999999636 999999814 -189710321 -716885788 999999602 999999553 999999447 999999349 999999695 999999048 999999093 999999982 170695161 999999783 700717058 -662376107 -739525228 999999866 1000000000 999999476 -553884096 898318411 999999205 999999093 912467432 999999002 869301575 999999582 999999327 999999172 693997861 999999503 999999757 -265283074 999999802 999999389 -452796553 -360302874 -704721331 999999938 999999017 999999247 654684193 -770462119 999999412 999999289 999999667 999999991 324409878 999999105 323380114 999999957 862379272 999999306 -753761968 999999878 -574697812 999999409 999999988 498910955 999999635 999999046 773420220 -102512249 -692520931 999999558 999999867 999999875 142233369 999999887 999999718 -134774734 999999708 999999509 -272535905 999999665 -974872350 21009676 -826367191 -896796403 204052809 940716804 999999400 999999374 999999063 999999086 999999239 398844742 999999316 999999432 999999900 115155868 999999257 -577402365 999999661 999999243 999999636 -28250618 999999741 -179903939 421995019 -981803554 369536736 999999653 999999732 -656441825 -732613747 999999043 999999158 902000128 999999004 -470401325 999999301 999999832 999999609 999999896 999999174 887475472 -654349576 999999982 999999783 999999453 -216001557 999999465 999999543 999999196 518237594 -524898543 999999726 -28812079 999999129 -739743049 -730170429 406056788 999999211 501894 999999652 774285173 96930209 999999854 999999906 -777215725 999999815 999999817 999999682 999999088 765852246 999999848 959468192 999999749 -974112232 859276689 -561279292 999999896 -237817001 999999351 999999687 999999680 999999494 999999335 322049675 59097503 999999532 999999792 999999388 999999734 999999851 999999354 999999480 999999534 999999335 999999061 999999826 -600762250 999999071 999999180 -583220909 -159905640 999999780 -199238984 999999217 750381741 999999286 186037498 -606986820 -441171052 999999416 999999512 999999262 999999356 958092141 999999433 612468373 653308067 999999620 -554808417 999999207 967268265 999999505 999999916 999999762 543556230 427039547 999999249 999999609 64811820 999999859 999999812 999999007 999999436 -247919698 999999257 999999715 999999382 999999400 -170023058 811724100 999999126 999999010 999999517 -150495776 999999213 94687088 -25705518 999999220 999999201 -795542783 999999605 453656155 -61015135 999999828 999999481 999999796 171524823 999999853 999999703 999999855 999999605 999999092 349937463 999999142 999999089 573916353 999999418 -76685160 999999680 999999591 293620071 647696991 -280306760 152808710 999999296 861978203 999999545 999999209 999999039 663366154 999999355 999999075 20993364 999999358 610421138 999999893 313511405 -98606641 -499618323 -749256283 999999902 742477605 999999435 999999651 999999841 999999872 999999177 49229911 999999735 -144484799 -173195799 999999734 999999676 113609814 999999614 999999378 999999456 999999725 999999252 999999980 999999240 999999150 999999587 -894107992 -295148695 999999643 999999556 943875575 -271521782 -124279907 899312044 -573386434 -973711496 999999444 999999543 999999023 -433912801 999999767 999999993 999999158 -590457646 -361031631 -655571065 999999231 -802139505 873466151 -933780841 999999059 999999070 999999957 999999377 -331964352 999999066 999999752 -420719153 999999935 999999992 999999480 382350447 999999054 -565687434 999999831 424814355 -658990959 -486110860 999999598 999999360 270927712 -824357300 999999072 999999689 -350624189 -267800529 -790396349 -887798012 999999014 999999895 378603759 755530098 999999294 -161457167 999999055 999999613 -75704163 -861728091 864254001 999999205 999999086 999999783 999999837 999999203 933600015 743236118 999999994 999999263 999999454 999999832 999999210 999999287 999999995 999999392 274302244 999999225 -886354115 999999329 -991361013 499782716 999999083 999999095 999999561 -730371028 460946833 -894331241 -227427464 36181529 801976620 999999560 999999793 999999602 999999669 999999089 687782394 -453758640 999999578 -809259682 999999719 999062591 999999698 999999482 999999645 999999658 -715871592 999999470 -531857571 999999477 999999476 999999588 -810853625 999999348 -497252406 -775640201 999999575 701254996 999999249 999999610 -521584627 999999600 999999515 999999720 -745146794 999999157 999999968 999999518 863753656 999999691 999999028 -331733788 770010624 172834049 -655494939 999999460 -224232192 999999837 -986676277 -689179411 999999357 -199412452 999999913 -154993908 116083052 295616906 999999837 652185462 938057915 999999912 257883457 999999152 999999417 999999605 796320529 -525823711 999999447 999999151 999999992 -465660987 -670435506 530183469 999999056 999999005 -148056872 543789330 999999555 608185510 999999519 150186565 999999430 502115589 999999419 999999798 999999459 999999672 999999352 955716478 999999165 -298127059 419466886 999999956 999999838 999999655 999999766 -266214384 999999521 -892874217 999999434 999999738 -507241821 -627231238 999999028 999999149 999999572 999999879 999999938 40104841 999999353 420853734 617317982 270894843 374890886 999999331 672777693 237497061 689026089 999999533 950163223 999999143 -546358019 266738612 999999935 999999019 968594961 177585014 110018938 999999156 999999196 999999556 -894777683 999999204 999999570 999999916 158502922 999999502 999999808 999999899 999999949 631330479 999999505 999999839 999999307 302915711 387556972 999999460 999999489 999999276 -558870773 999999835 206651863 999999389 999999409 364582504 -373990152 617754779 808649131 447824332 999999867 999999794 999999181 -690009678 -360034576 -281800609 999999435 999999838 999999498 999999020 -59204444 999999144 999999543 205598979 999999486 999999225 999999764 999999239 999999480 569500999 999999459 999999299 999999984 999999798 68984631 999999246 999999527 -480878265 921550659 999999219 999999790 999999098 924273563 999999390 999999646 999999338 -384646978 -880022339 999999047 -220500886 588605737 326162650 -697787512 -437386251 291718454 145788301 932878470 999999030 999999388 339749578 999999782 999999565 -668072956 999999762 999999888 999999823 999999405 576687280 999999494 999999635 -788363216 620573503 999999047 999999010 999999672 277322161 999999276 -595936179 -217981256 999999714 245831792 999999697 -633966428 -355487140 999999353 -281594847 348081901 999999113 999999750 999999834 999999118 -97362006 -451072805 999999397 999999180 999999077 999999315 999999658 999999389 999999485 999999597 943904432 414831404 -413911733 999999486 -456830993 -39643649 999999149 999999194 907878405 -673595327 68932268 999999624 977686421 18974559 999999279 999999748 -106633828 999999012 999999591 -824507097 320438520 591899475 -295055521 -417124765 999999634 -673630787 999999610 999999411 999999559 999999966 204141998 999999846 -507206025 999999922 -289188944 -828943855 -682033957 -1279820 999999793 704052170 999999915 614858649 999999192 999999677 999999926 999999352 999999837 999999335 -918947502 -876349095 999999560 999999164 999999578 999999644 148634817 213988549 999999330 999999706 999999026 999999267 999999513 999999041 339525582 -261043455 999999396 999999719 999999395 774049220 -357345225 999999143 999999636 818779913 -162936984 476146893 999999525 999999426 999999942 999999359 999999808 929570529 999999995 -481483456 -293780363 999999391 999999358 999999339 999999733 925235039 999999336 999999950 999999918 999999842 999999920 -494599744 999999625 218897210 174427158 356442531 999999390 155262853 999999555 999999671 423624693 999999093 999999702 999999713 870689284 999999684 999999590 999999668 999999190 56138443 999999359 256339953 999999417 999999873 703923679 -696190748 999999857 330429353 999999954 999999223 -814261139 999999222 999999946 999999614 999999444 999999019 -91528647 999999122 -506506785 826461237 999999037 999999510 320330390 999999193 999999963 570155192 173825018 999999907 999999135 -601215790 -805920016 999999921 999999741 999999459 999999450 999999644 999999177 946893621 358710393 -490167723 288141326 999999106 999999705 999999019 999999704 786370481 999999673 999999763 -32994890 999999415 999999907 999999846 999999965 -405214446 999999910 999999426 444495861 999999961 970906950 999999987 999999945 999999495 999999386 999999830 999999271 891634493 -958140213 322740347 888758245 229468733 284226332 176318934 404793260 999999805 999999652 -282148950 999999592 698892460 -224094579 999999680 92472306 999999158 999999550 999999690 999999823 999999504 980070733 999999281 -840927475 155227027 680028943 631582159 158684005 999999221 999999842 999999949 -845144185 338648436 999999223 999999604 -570685973 999999072 989736289 398173738 102482048 701931014 999999387 999999186 999999395 -669022860 999999569 999999862 615077488 -284607587 999999418 474376994 532359938 999999530 -268143702 999999744 999999219 999999973 999999703 860423209 999999156 999999360 999999326 999999272 999999244 -149904847 641483036 999999494 999999410 60029431 603179528 999999669 999999462 999999802 999999640 999999660 -910328457 999999397 -590901820 608562796 20184892 999999551 999999267 607153127 999999935 133072640 999999119 999999304 825348195 703246398 15101906 -937590351 999999509 999999621 -702453156 999999141 755165699 999999765 155191557 999999724 999999943 999999469 -591120665 -221084413 999999077 204042346 709957576 999999249 -975396459 999999853 -152892041 999999916 -424328754 999999057 999999575 948498987 999999819 999999023 999999473 999999992 -930187408 978710172 999999134 999999141 999999024 447546168 -415778645 999999019 -524131352 999999021 999999782 253013705 674916285 999999902 842742630 999999844 999999622 756981087 999999867 134248408 999999702 999999125 999999741 999999871 999999902 999999150 999999827 999999934 -935693564 -178544443 999999180 -826719302 999999395 -673771675 999999421 999999384 999999388 999999764 999999007 999999959 -356249863 999999330 999999748 -596022157 -883494857 868445397 -794175282 481665227 -985904132 999999698 999999599 963517227 999999423 -50464232 -561420713 293162628 999999915 999999018 999999170 999999987 999999351 999999085 665091116 999999710 999999760 999999440 -510749144 -937033554 708035348 -784730812 999999485 999999531 311499987 999999916 999999036 999999370 999999514 999999340 999999278 999999782 771400367 372559704 999999804 999999669 999999389 999999105 999999081 -795699608 790156057 187311228 -868073662 999999088 999999017 999999194 999999357 999999659 -233536008 999999822 999999006 -191879531 999999078 999999753 999999822 999999996 375447696 999999998 999999712 -285765833 999999953 999999035 -196344786 999999530 999999968 999999496 999999672 -908755263 999999374 -224861187 -136522880 -790557137 999999470 999999943 999999694 999999952 999999216 999999468 -336688080 -415836367 999999678 999999178 -517416285 999999236 999999448 999999226 999999101 407957551 -84976176 999999642 -394588581 999999216 999999581 751736343 967709026 766365009 999999759 817094005 999999289 880310157 999999746 242893014 211080411 691884613 999999938 999999474 201436446 759893708 -703430864 999999523 999999045 999999835 999999190 999999335 344308959 909378026 999999021 155999473 -858121833 999999810 -468061633 999999743 999999248 999999196 999999422 -210890501 999999445 999999956 -933589157 999999320 999999154 999999184 999999677 98603444 999999977 843707971 999999969 999999842 999999232 999999127 999999423 999999995 999999562 999999944 -531580952 436441096 -681899398 999999597 999999188 999999546 999999719 999999560 999999298 602328917 -518347447 -41465471 999999591 999999669 847842993 999999687 999999656 999999138 999999478 999999156 -479804250 999999687 999999749 999999380 999999778 999999936 999999268 38003364 79732188 999999567 -751573866 582027083 235236256 999999939 762010680 999999824 215542214 999999488 999999921 999999864 999999613 999999370 999999210 999999083 999999307 829791618 999999949 -396044593 651565828 999999100 999999753 999999790 -727805993 507157605 999999502 -746613369 588613252 -456032129 999999835 999999863 999999853 999999637 999999297 53246818 999999946 999999380 999999402 999999911 999999447 999999110 953376787 313125498 740858388 59242788 999999127 -142011361 -528870299 -926406702 -688078226 999999690 999999290 536931128 999999505 6885471 999999551 505952752 999999983 999999386 999999380 999999397 206069361 -383203818 999999693 427276487 626169893 999999100 999999655 999999401 -231800061 999999303 525486499 999999882 999999787 256873903 -222223525 -552160029 364653608 999999133 310125901 999999300 999999090 313793295 999999472 999999208 947517179 637454482 767609968 999999358 999999357 999999881 999999667 -931718273 394763022 -340032027 999999031 874006749 999999273 650540872 999999021 999999081 -655145562 -97773751 492872860 999999444 999999461 999999723 999999420 -267636413 999999425 999999899 999999668 628860418 10078855 999999167 840567134 999999835 87777082 -597942386 -243816143 999999382 999999538 999999686 999999894 999999726 886041277 999999505 -991729297 999999684 999999926 702909054 999999965 999999062 353000464 506528535 874930448 999999608 999999590 999999601 -882001536 999999826 999999518 918669980 999999239 999999839 825932319 988032435 999999380 -35358987 281108087 999999249 -178813587 999999982 112274521 999999963 -158060887 999999780 -78458638 999999574 999999212 999999322 999999877 435491703 999999243 999999650 999999585 773988405 999999056 999999215 999999121 999999749 999999079 999999165 999999708 -695612625 -350598441 485152976 999999566 999999384 963606720 999999606 -140384876 154483753 999999562 999999830 -149204395 999999074 -254261516 999999452 999999944 999999369 999999990 -988235061 999999961 999999935 730596780 999999084 999999440 -629045419 999999532 -630150001 -872387132 872314867 999999662 486646997 999999962 999999839 999999072 -27014282 645343504 -652398894 999999110 999999079 216512523 11510833 800951372 879361652 999999858 999999437 999999230 999999999 -168656084 999999271 542854977 999999924 999999702 -644742100 466155867 999999314 -641875324 -598077317 999999170 -532748288 551278415 999999880 90426171 -222095402 316655495 -762894951 999999178 216194922 999999876 -166682952 999999910 999999291 999999323 999999014 999999410 437607801 999999686 -24075879 682794034 300520451 677348073 999999190 999999689 999999548 -931590522 999999441 999999002 22137247 999999584 999999115 999999132 490062837 999999246 999999005 -480684596 999999604 -89607994 999999374 514776904 369487761 999999293 339229349 271261439 999999639 96745508 999999902 81708618 732250718 -831426267 885073063 369639956 999999750 999999273 999999874 -8922072 999999344 -682110583 999999929 999999444 999999849 -757703510 999999663 999999050 999999296 376113621 -927147773 438576334 999999895 595040169 999999004 999999113 265485466 510967693 999999465 -954272279 999999263 999999446 999999283 999999398 -308891740 999999059 189657746 -788510607 413318173 -685089164 999999973 999999437 999999779 999999878 -747256503 762052153 999999264 -149113777 -171345173 999999334 999999023 607875358 999999180 194664971 999999601 999999413 999999787 999999445 -935787199 999999148 999999655 611412807 -394521723 583873880 305148753 999999317 999999904 999999845 -478665448 -899770837 -650900629 -264223270 999999284 1000000000 232057082 999999738 999999917 999999676 25664197 999999291 472328410 -294840177 999999978 999999298 999999977 -607595611 999999118 -169641199 -869628777 999999806 -852513513 999999706 999999248 999999463 999999203 999999539 867022439 999999395 -843287913 999999614 999999361 999999693 -669540582 999999540 999999919 -856152590 999999866 -423741137 101317352 999999854 999999524 -86564802 999999339 -711556906 515623579 192451731 -308612762 999999487 999999398 -602344647 999999950 999999200 -449778861 999999672 999999267 -202988498 999999495 1000000000 999999572 999999194 999999618 -974277613 999999130 421993516 999999570