4 4 1 0 1 2 1000000000000000000 1024 2 0 1 2 3 10 50 100 83220 22832 35419 16538 66026 43014 11109 84563 1126 58314 35467 45227 58725 87809 70749 17285 88114 45128 19009 46557 34047 29046 48260 57292 92 58317 57399 8743 52166 98232 31081 45536 62138 83187 68367 47985 61683 17022 22358 17184 27982 79847 79126 2124 23515 70306 70573 69909 29015 32886 315 99413 97746 80893 82802 54553 62109 15922 68331 80039 89299 62018 9989 21748 73903 83248 83126 80958 47595 52713 60902 92163 53543 63666 8995 12870 55943 68355 94095 33196 47708 58623 37162 20563 34898 16891 5537 21752 38842 96302 85368 36601 31344 64654 50737 5249 66021 42043 58606 34021 33899 15306 85022 66756 27346 15724 36507 91709 40087 83786 37968 59024 6004 49540 69488 40070 38945 79065 91010 68104 83587 92080 71645 84746 18204 24198 63847 9756 6422 50540 58296 54509 55430 48539 96854 14996 3226 88589 52109 97897 68053 28020 21531 16432 75456 22935 96127 17439 16309 34252 47954 72037 91756 74417 28334 73668 39053 99316 47601 94473 16973 90375 64013 44555 946 75258 10349 70356 90358 37769 94544 75245 17511 73729 77968 75278 28687 67275 19339 23864 20032 81829 76428 78059 28662 65943 54220 48650 8044 26774 75695 55291 79987 50135 31803 5500 95317 44151 32646 90123 90808 57164 44112 96682 24623 15975 36108 95868 41521 80915 31147 55033 91673 58133 38425 79188 41178 97287 63827 53844 58289 74530 78807 1110 8114 70424 45312 80853 29771 3373 65117 28600 77433 31071 66381 44313 21476 56616 56721 8566 92644 16651 40483 58706 45486 57702 29474 35937 80263 8780 12491 12291 26952 54010 91799 98645 62193 12684 73543 74035 51956 25272 88147 79484 29553 91128 74069 28348 401 5961 74340 94605 74671 62402 50290 22938 77982 54846 40397 34346 29711 7545 34141 40249 39294 45239 25333 51318 86145 71875 19737 60913 90436 55309 91027 98249 68216 54733 37042 89219 93415 91372 64691 3087 79882 67459 86008 19237 20527 86719 61165 50868 25207 75247 12254 85739 33140 2389 67443 21592 9830 47947 16069 74584 35365 81505 66868 93648 37809 32232 75293 96968 69325 31104 26864 68584 90955 92326 28452 51229 72680 39004 28501 63102 19745 80138 10004 58007 72183 40932 53405 40087 54538 89467 49128 1327 72587 84203 40146 84989 64869 58 5283 59953 86135 72778 9445 48155 21185 50484 94374 94649 93284 4559 33893 70517 59204 53902 23444 58584 29574 73723 28196 72443 62417 64880 70971 22951 73219 23465 1066 56486 51855 18442 18741 62841 75374 61009 69390 46154 52242 79560 31706 5128 58886 79745 90411 66378 38093 58357 22697 65427 86624 57376 92121 34494 57718 9705 57127 3834 93439 56860 30338 6566 12798 88120 19715 98742 62162 24143 31963 30567 78385 31896 48453 28646 75867 87565 98627 2802 25401 41337 94831 40651 2467 44424 1668 884 90254 81829 75820 63556 76992 73334 7370 25753 22773 19811 26391 70632 29275 36549 4372 2868 26194 55175 12716 78164 66909 13543 69916 73211 88133 39377 61283 14909 41321 11922 49148 52959 93009 28081 39558 46718 25863 20294 85385 96178 57478 58753 93043 16339 73812 85434 90439 79257 68424 61361 14260 94584 60326 25291 54803 12531 17603 91355 82327 36239 83703 29823 68259 84019 37176 45304 25673 95589 32327 61349 10814 18461 82483 46732 80711 96557 31622 96314 44789 70511 13289 93276 49588 83406 8181 30155 59256 38850 9260 87331 58480 42008 58323 27608 97148 24828 75058 66655 34097 49579 85205 32765 67184 83098 44886 53176 72463 54517 85972 35510 30120 60153 40231 65123 68567 64037 70692 95098 69455 97052 79791 29841 88853 94437 69509 57342 32882 88984 73668 60393 60191 1015 1446 41262 75089 36908 36855 50760 14293 9256 93839 32561 22578 70246 62393 41194 4863 73944 8428 68268 9553 12353 15557 56648 47018 86600 8069 77642 97306 93521 46168 45243 34530 75238 90134 17516 7080 75227 22641 68390 37108 95589 98254 66458 97624 23530 73609 10530 82387 23108 37407 92131 68562 29066 53653 23269 50095 72182 11983 64792 81267 60744 85968 25900 37815 75921 15584 87113 27511 44543 72089 96432 30405 85629 74037 76709 86380 66001 75092 53435 73065 12645 26294 2225 67974 26930 9530 55228 44720 43766 90741 58574 34272 63017 7643 429 1052 66508 15819 12307 85733 4161 60307 70376 65375 84920 69252 48833 37312 12898 43942 69917 44007 68167 55133 14326 54657 74065 48162 55216 20603 56416 50558 87253 89223 69295 52217 14582 73990 57206 6973 56330 90456 10250 44447 4247 92353 214 6182 76366 20098 92961 31121 47379 64996 71691 40793 98038 52316 22901 32911 62850 59263 44862 39026 90358 17964 66473 31283 59935 59904 15777 80581 72402 58667 63140 28960 26993 23403 19125 46637 45567 90927 25016 64585 68791 13720 89325 25916 12837 35524 48741 98873 61222 41288 56058 72083 94413 49585 90912 51214 71117 31159 17174 82989 17260 78885 91308 46202 33886 66281 65226 72071 83561 63045 91164 75046 15816 45465 3776 77261 27931 20723 85747 22647 16678 32766 31394 84855 61443 49071 95341 74907 68335 57315 24156 19588 25283 21117 53948 72929 3663 91634 59727 7159 32065 27111 36200 50534 12175 43409 25918 78066 33452 30821 87379 32364 8622 99682 52525 17607 6531 11418 85639 22539 50747 56867 71802 61095 49338 67740 11851 68567 75428 21855 27520 86034 38172 55825 47349 3180 87711 81632 87339 28862 17613 91210 49585 86200 14212 2929 57482 39879 32521 3700 49408 74718 48640 41386 19928 15375 88253 66998 46404 71346 75456 6436 77732 39813 1444 6134 44541 59330 46271 20596 75193 88088 76460 10906 53703 44088 67877 72700 22027 81147 45360 47421 40306 54877 55 61211 89861 37065 95371 75743 69799 41738 59559 70088 88383 6854 8357 32839 82131 61400 26494 46529 88146 17802 19635 31809 24474 6070 77555 68799 69304 68014 89943 8601 62052 91600 15389 70515 81089 42638 33831 78052 85612 49812 4682 6952 83569 40123 26069 23244 30778 52459 7871 95632 7918 70536 64021 44457 1028 1173 57951 95220 96712 58288 54172 86102 89570 76381 77258 99596 65908 13273 92003 79023 88190 17239 69724 60262 14985 80375 91763 80403 40675 9555 76455 82768 19357 18916 41684 66543 13939 75263 85347 29105 97759 44118 21553 4867 13220 98712 41629 41110 15660 54999 48718 76658 78551 63318 24280 37120 43293 88160 14003 87869 78361 79865 55269 72168 90067 93027 65981 73804 41849 3777 2048 1000003 0 1 2 3 5 8 13 21 34 55 89 144 233 1000 1000000 1000000000000000000 999999999999999999 999999999999999998 999999999999999937 433417157969841514 836633742619224617 114899860085291504 320539242188145339 234117631381549243 926912203752479382 271394357000399034 615316422015305652 785952965139461425 876652905240802875 842545924681708637 821608124939926149 714620219897153508 568578597710465733 530936253932001248 824800501396896813 798344378218611312 964504256557001342 102164890918245715 558121751735864356 716618973694227340 749950621829503792 460892300814165681 878945958453040370 301686859381036471 58022596708988868 744042923822144231 960543124252410278 359010006504001656 939216647813622121 498817554718379970 948645848352631171 166302706827130642 933538806761618065 761655317004586373 488795100305767857 787197643862913221 521798548580157587 512750513203174758 457937400903441828 406635771945006810 469786207406539641 342025205347049735 164118931591559263 262452477597170825 833769644549923335 657703347541055839 292843402089469522 193499538980791577 204046915109979280 731908247548746175 196093033485627156 392775013337979532 306665754195656545 457619026930229311 409791801421754568 336574065095922505 866272852038264373 182677910851055819 598340526109597439 140137516658441940 251319104002507836 295874656910625728 850378478490722544 613145086610811418 477376010558918486 194919226683284307 46568048343192622 434852312644801225 826161009548846808 787068422810881149 44150553815829797 221660741234050104 622323013536391429 203196902840145119 160603867415938534 879599501061861045 63513953483857706 154981850847343579 582488871406911555 536236181904178334 982642430736741778 715588461998501549 101388850132333837 952584532119492747 529707562080884884 263046170114122160 331047617867923531 699838973551419246 204466472058260688 92763737558958422 610996815904701441 274059012582198632 975387462875726519 97147136140260216 742098552458300849 66517167353685447 741123211857763145 189865717850214808 157186289301406241 369600903365760731 299617548109597970 974810097188668974 916340713420496397 87685118295160196 375288688881614141 256140356385511415 467247890417149405 61753302270289565 168940769869559438 428903361891956050 215318343774353597 848854271345128992 199288849270630947 134916779417816851 372820183637094599 913224421013085554 431189842495487658 875281594277225141 258106653584978486 433188930020164912 915580121718201440 907995735787295878 276781394811542328 945149044151875881 4462509095224959 949360802858582245 832600015323703381 981114502866229153 634236664705525370 148557239426374437 674543704980733146 185781802012215160 705842487028231153 282128658532810326 665827513100694512 787103328524794073 388757072755249529 945318425562840183 429880521921360038 76535316398785242 439102086520703429 752094293368074138 204671262292295328 969703761383553230 981722120729772053 825596447127749158 566659406733154590 504774146022505985 133602893757074094 22938470000258316 631378923141367902 257991067630386790 803492164374558153 301281473726791833 329051223976938741 430020971620915855 844075340540138357 256259629828739775 473346817470041702 770653007646660859 717178639587259502 562126023129482601 215444233474774106 220905418391284017 173357341487035300 690565532253062273 21632747986896822 245385029202781624 95877828365626707 841913628891708434 362991838210976737 886582932500311463 298226055573872528 46030382142861465 760156577923725571 887137700502578206 651987734813657479 518375154735832439 778338277222361422 412364987130713036 632450811335801665 952177130368478088 762810702246020 439142967146997924 580460975859028440 333764627639851286 58514404398894800 688603800329582215 97297488690672520 973868826100081874 370080904692440123 137145460333178781 334593414940453031 349008195878283697 231441369509782881 435751415942117103 905280088475957123 309846019027188823 269253788673951572 420490020757137258 10305351222507021 199654303785629498 619150783741314004 149250110347484674 979594488344914515 281860874756918940 26818715314081837 452522374526861154 273220545456388701 246106861845210708 664893790652737258 353491731085940254 286423231622920053 89599277795795655 71036020745754807 519628529486723125 425055197365795845 976621657979039923 214311391002750030 241017296416191792 712201146631671804 145143994729960498 447705213160721690 50260047759334300 140879308692188913 711942917046704441 464159539624638443 815273328123570652 690938699186266412 852999127107284702 847599107715330347 393862909931745477 277480226823022913 752553698026890301 932852735253367559 786758127821866011 210690625643714673 415605807610914078 954349466035887594 426665986713091436 600322120335857937 622765989543940009 460613014778591771 60128927261328342 858888582133489114 101300542117941439 481794035506392531 96322982640883725 203768567770415397 675507243740586317 152487307121231204 815730928420947263 719863970042824458 802227733616910212 183431286734481898 96090526053128536 810343061845433100 300363348027805039 561376235017975749 484634471333772875 398458348896545855 121250348388475890 492568081937677397 151165268848832570 297863190942809826 401056137826333448 488991838678941565 126644785711531357 402726841169943158 86790190093306105 834428403633572964 714107958433513284 506005198964494842 579494447995411017 508037237870416783 422487325845860435 149961734584993249 579374513169201630 459481985051985750 17139050778678222 483468293847391296 695738238011194887 891642759424845898 298918012432429489 869924340760759140 816832625158026654 975916932229881341 870270028297669744 426362375081416372 729928637399475283 721258345805244087 387959991831863546 811437188962767768 927661106401033658 649491703890116351 493382807014634205 561911747219157067 27718652072354262 855915020372576344 441296784611971034 46909008347643627 601163687101303952 806369956966634477 233269958937897366 814275714015455830 148072129142554191 247050155700658793 41319342935218827 969794618765945435 336038417341805438 50222905285262258 130843478334420785 874877487062649647 571234638377250232 467487838218854671 582529316526145294 168057925064841431 869827762128041064 660514822008172404 584206618886873534 310108364901920638 770962782049859661 540003968321043610 15510068374127554 867155692818218017 176542353733166320 870699901444250633 314908826172370554 357463180056536532 759746459173894681 506389771601432975 796770995181954051 172154984209259115 514044546178093525 714193995360784730 836844317451352373 736690408298463841 500228253841658444 490712487563639626 440342445784887363 435585782538415701 685622552419384623 216654261056118862 431000243165862716 935227721804775262 487978578124940442 259356287178056103 405170849734703767 259675427020618311 233800979898991257 901282583094649113 200445491654978238 17469236294163399 560847256835555373 198013713819716592 941989432041816128 493227446491321272 247142652699673206 102621620537472702 296510593239525415 210364309983741270 247995590100108438 962662330067845291 962563182480218227 8770090231410793 865359603818654113 101701121884190181 429870797584212949 838588220406695734 956399278992781708 881804584014752659 886323674862886255 488293598833802763 235062752176776798 678283081024005657 927493854433796152 420796022977628459 506301975684361518 248669409280820370 515759856753706585 812028421811295437 333679698041846056 589474229697655066 643252897260489228 103496492724637743 517915154903432674 317446843364159613 456372010821280871 266344071500786426 966703472243634536 133569250793082950 131711204740589004 750242665626834188 721108544004182616 490256389954966584 525805921816335072 56059985688775495 269931825859515893 8509271735264678 210650264934259904 739560084845524241 696689183738464146 645203559949325144 505618146641618443 901926006904078030 476186326110128447 33291484061426752 469992328884597911 329455565485315132 503169253979072977 692060316764216654 79154306444626249 89656993709830051 509672053303955200 37663742037061061 991980052675671313 355393488533693269 929965737047682885 643432047261971994 745719138722030182 736525066448458665 301710442567862498 594282605283422522 845842521933992601 655326126331274526 555787674701145438 179422506295643750 411081607323660081 603968103813155748 843418534433566261 108145660680938485 475654657738315535 423247031229095594 849434240281317427 575647600953001115 531489699120694369 156439556176755165 342611354241830730 894021262079879428 588531020466965506 223585095557221108 960518574131692067 454056703646606759 638824074883712352 724909174502067233 630199233004754339 300103030697938177 799089157305397288 169894475349646698 194730095638536460 411420406777099287 603474860081372879 732382864526344423 116944985693503705 552797941285870800 563959555476006760 204541801445523100 832632447412761203 926760032755048891 904446885339566726 759173155549508929 108310265272358610 769239271723796020 72537641916249665 754150226448285136 58316786590357302 281598489592288506 878408805561125390 568004638435699519 547830549970585540 985494668229571721 935566100575090417 353141857589963361 622435911325495804 762301037175695834 641265453160723303 208428118517676035 417401708101235702 343097580113009908 639309749936948736 203345235183380735 857416754955241332 945075781900693995 289871554047340540 419483115463309402 64021460035866633 450276379448865183 448207371534662068 387791646466443963 469148317532174235 234673814117175862 326794064106387202 427823971344493331 629201155574169453 452728780710762118 459414669627064977 313855399639622210 500894321685660298 667275471983401138 980667916158350877 536840266411733263 486006841784167991 987408189248411789 907283589483910984 959605001062373620 600007088600043095 635107202102187032 909704510287233365 254436584073101958 914376429681900778 776681334716134611 478504422174027276 894596051813353679 43497837776216544 440141540840462772 128922131096647474 258753773076710518 137619933513444817 292538513834144027 975927716739437539 804419730330791738 526649218582968415 31995373289234319 168533621149171168 607985504585803056 911733212994786162 757471409917848909 477828564961467071 29524037891155023 1900217675915698 526932578761668557 867959753424959970 186715773520947944 358713746467098431 382487822718786464 359353306523785527 40091303457345792 418823757947792666 567187473388462312 613404686801935587 108297879894324219 736105636423294549 601137398523366007 659349899592992076 55968239637866843 90428837976775926 150494281891623970 206436634033892898 858782887786466355 519590285076833522 179464048126274828 992049834369867710 234897165430499873 976918115035354452 366159155842753202 5037928400814862 566398292512497231 643488056821869447 813633317137930554 980833928083303708 403989714714549776 270396010774084741 133012058777377812 900212577418022008 620629499156005513 688728738014520074 512208966644318856 413847652191060833 278601262930634343 660081376353225994 804384468156751279 319449407726106847 776270452223876227 86091232602173027 318561300990085255 156637282059273770 865936464352147614 884925977015284036 562954392157941643 413079552712597268 597627830985057856 832322999377267339 532895898152320465 740760205384611096 566768845484704010 32878086864473550 588171608760915882 922495441870268879 724634235723772294 746813851946680602 677132316969358331 181103089915518538 523234642958938169 681635713662994361 611293784871523620 647666527551633667 154688189839796499 641863123654885686 694058805848272146 628141858048812475 755496444707091332 349016659532965975 124596435167454687 216691328429941514 2614701126274064 332588158374880333 385249269487478138 323837172004508706 907547883885018212 474189162536047085 256974345035796341 426891564694798883 153646406067158293 186731820740599469 135969958265731060 96489727876352612 191328814500192382 93459324518517334 676546943980653197 647488785502220026 40817886799396483 118838915455925679 905130295550943344 743539483629697263 718837085109246874 709189915302521789 743453049425025909 940312796187101088 757593567145825724 775605289933468770 412059616445225372 452857262085535305 594755233872514219 909767039794308984 435976697307383275 366081332545927297 13154649030455414 664250685118894611 376939647559254570 801459281482727278 247689000502315062 13480521320530735 887859370300985075 711929040517231618 280827257961708444 914281440746293451 415708152199687737 677520015765174551 314750258315328987 417215586322610684 881887935672691617 199038413208768585 624082933163762136 19344757134628061 353583330151233823 450562194474718124 416119808720587954 375392864252666570 197984212221517067 487048672830416297 176261371874603070 864804446633446670 348486673323023577 266095576784420664 723918341197386227 287509916075502509 678707913886992941 679065553045157904 332467664288319476 474108149664736449 68435848230212453 262438719726512057 947081478690172193 145490133085628088 594369225727918445 336782910001417862 223536034827360327 445746537959733123 308547634233147826 607514048897912727 84231086463729082 47428971573974389 534558642151795281 303446584107386918 634093881765537231 792855250085741980 375817237446586069 888044597827974138 705907236281405867 920950161547906801 997561979292436480 494632923851784265 516609702222147958 71748227500249307 40972488889209941 771600744062935093 653007635262282539 251695321706982620 559444047986462917 58181699190384203 15406380798742909 180363420230457082 152877911170116320 842634910560432701 677594942447359144 538806287972320778 696819644237833043 108632889336222537 288968374759768396 288354237096057568 530342330509796475 632212761212316937 662189265499531119 76441067091914959 490014276152338189 420163327552690620 558933114225194354 714517477879685714 292049793991763079 432860505177773685 997813282190298289 833923995543776505 788367194146683653 306365700714980006 697818320047988507 825444560565745438 37822722059543987 182103914088246740 825722168521094940 5361684073941896 589881314777905011 728075139335087844 228086557867921487 781708093339948133 578778163811290847 560190171537585364 277728998155622901 852895746256289538 31887760073575472 481083137498666654 218153304323132507 234937460567999143 357442453746733875 397364186583533848 97110282954243943 410240982106866041 945152802052364414 842272742118283759 345851357915701953 106603652509513282 725343659543691515 289545707600174446 114455710890722373 120936296310744171 37139348761671398 463484046991376458 758987847318176023 335512810787472838 204880050782075809 83481270135260693 554777151034409824 911617780236193943 494473938899428170 701197735270648162 639654943471586872 139000640782863017 18441281374187894 238713646039746461 342831292945833081 571221993396245849 30829222524368216 439047378123521974 911150243057443477 138405895024541287 146327113876377501 587606409637505187 473601132839086853 47144629046222152 766605397172602241 101635104115020572 646518307367670774 165715462233699151 444834460496974793 42804116968540346 755402444917170170 257270599261068688 356823836480990412 413848071285053748 273440481944089132 195013030639441003 139898412037972060 520593628845329340 613938833548153881 212692927513070798 175150246021342762 932893752777790456 388080845820039234 179477744723742389 326588008288156662 776568979764731571 63653589388663885 416786762237724627 10013431799491403 690570488686205844 79316382935909901 819154218959205296 764329635328381263 740195777273969875 795599184349531698 587736370029371880 303772502234764744 29048007890835406 592621708760749816 710370972849172003 525980853283678659 996254468520005765 114192552913465916 531012271939414235 65181286644195463 33923642373284089 378226210904808162 49204956660494216 286115098884803017 943675275895689745 562194374993900140 631031171748178903 101740936758603687 847270352049201682 594685824126225855 755959043532309895 938445539133191579 256500517678018245 739546244007942436 350195055965339990 956306398801590401 977489847489975621 907087584209453404 331198844674950583 35107422739748380 854891094629196910 617632274790067139 439497367121912235 427407628496360305 57878287196031362 560136015276219645 20670476948439310 220931996536221314 995125141719947497 720690575351282523 207371010276292885 401678652000844214 1124765286470119 598022525545609864 298132969298771437 682168467440601711 718679062576761117 157830649884783178 714311952846000047 195898346250184592 119704159137592218 158495605900228639 878956277200125776 194108269110256771 758733823838874657 517885152381379304 894336467797500508 180824969757864807 440459010133158382 404506295688810288 61820841534844667 10080066286614195 376270448801814200 650744476999287343 961484871120633828 64767920341348984 493819406182241622 248096858448586901 409545800102016005 773522557420167479 635260413014212357 13123599828302267 25795836924281325 692919261208190589 575947411736050003 19194946978617779 968415580863901746 531653828719428443 437570594468650608 582860585683681143 842044198383781832 698865965402738282 230693971005607865 357270686422382567 783005081290285424 397486917219460025 495289450803947395 984074007167381344 32267579286153198 868202943342529822 692290713157647678 461221478811842764 953889140724234426 82528057144592892 975306223227794707 194560968599528616 489624154875590828 305811990523366742 479395330081483999 36904429959349448 547203037231278153 344159022418882167 174166013463945215 698896664082838936 254307737160554553 720210393483072936 927452462286755993 118891446851677034 35820249271308387 184253660288733688 469835961937887615 363544518354141119 513123347083228295 910178513829695038 407541737441443233 384931110928733869 33762093613949992 776992931793480281 756231030812610134 326052134359791357 682114316545219208 371681048388321750 445304885535008603 481593273546908681 511478186982544118 614436707319479198 565596085901572817 16438949048672714 704786236158156730 163046849687857482 559858655032537824 714881282129496812 37157308385719599 293024660799290134 547554954591752245 906014756464161819 508688960830853502 155388449333961373 847179146379863484 93977779580900252 38649986217615816 63017164419209933 685137197951671326 212517335263040382 435929733702679119 573524880414218954 315687625513075426 706995006715388276 934101582702663860 988243492337630167 65842748133198030 666224990893232922 883318102697551393 355282139701208319 638205370723699741 555487511543207613 887476825516793163 523066016407418757 719606627200260740 657726861464885793 497198286643572429 321894005406720051 106087882893900725 289519866239585465 88034676022913384 590420502931843209 126941949029651459 419785895301532448 449178889884282970 543338221302543132 728962395845044897 173542891943991691 625438169487742774 332286336034267339 858023319564008276 497669982959764274 454367823583312533 329882037274101539 199273621485634536 607734833618420691 2238387918933999 683767731435859815 212043689488596540 773569635862878977 837836287724511492 854749219331500755 128716882291200155 341223817256049772 120563396555551418 533296906395995986 731017266233456744 789324732249779059 270697106963463949 901533660890624833 637553957429926713 611933615771631424 364271099953050362 379970783451290370 956288383490776317 327230528697731862 198386069813039641 546870274547133739 765373481774065497 49100364341892888 455874718421437957 550911071617209677 29958164503203528 74360119624152769 919544276943901142 473142876530017717 410055752494917926 214298435973589430 416089674512725543 21796171222329132 703012613217124076 658387510556037420 76014360313819228 852030438897299073 436656231531417193 385057296421458730 931060692029972008 779194219528281410 909427736039824790 497287066344898706 947601756681078253 127423926095003138 613282456881925262 777668243937305256 187838293604180520 139818409379855857 310656630957134621 280065913946206021 120907493279736528 190493612725614806 957750430670544729 679439788015566783 939374752517980493 415441370087714433 757884408460769932 213438402015592902 380310621928989153 682947179447088369 579257354641897880 759049166248709449 828085933810651434 929364437959759968 17421157666434299 776833445629176288 139254519548437965 74485353622316066 148831482285012516 324045610462104470 448238175498277015 489301846661471109 263350789528698859 105671746330986591 952584931713087945 5119244307691717 539318664309347269 630811133236347531 521320550304539336 682244883771494668 475833561275729057 70618320538824907 891006618558500004 343632262746065864 809608440589048283 154867451038413991 743923016026128863 880654843477274974 853422615627722108 137992602478258600 160433841266891933 584254250745873209 967271022383459165 816643203826503461 21920480469426377 203268425330320094 49251173152287973 128240346221379252 100420206200485738 461555410959647101 283929945427041600 421946886045655312 269315678129489431 551477195026560260 140761558701190568 636782727572830907 887305926044099730 747067346815794173 324697333134465574 865511809199280295 329124337501926654 770775923868131161 86833149167849059 348178254237412248 442631982738186333 515109093240345174 950559307113901887 876688644109348819 644319152587622813 298181238360128596 835751997021785488 575458141335049765 164601751635201397 464784074183593950 579161745936611607 64642812217038929 387430450622394233 151908342458109769 157384976269014469 493080227788163995 180771155476127856 862566421943666519 559185096490963058 964210354666852264 210309609168458443 316750181063359910 62150310701088360 535741318761695259 638586068972620967 801202525770040649 851530910268511399 687809499442118880 235377478105075706 488350092634378921 825870617699749910 399613487278959929 840340307261369743 773792236959628241 894749261308920217 814226472679569276 968231192177228805 546868174287497908 271634967990250131 499819614507210118 600824925740545184 208461635107187702 686424906700025056 76266708972025654 417534599579320998 174826787237227600 669382543775816202 581120372571953112 266435774529214994 906610684331829781 252318188745977264 333776538129609498 101806327341830135 2006604955146839 537201388596593190 573092957683987381 419974591781505828 331281746472899498 593834497462719861 447762172944296421 696496935030580685 872913365854639328 21455428487498072 805393341634385341 770331371046415242 997177966098377451 839870436870843314 842472901306014992 698185425753455283 322630688968382181 638774531733344395 729682761394962135 297496231669698698 304437280952155904 19736509609649435 32427237671590976 834026093701214138 303849143840293982 194365926114477674 769047712825401156 411758292508988039 535161383347150893 588844769779491374 924405134437277135 946456256705400551 227657757290557315 753978766538189613 520645843363359231 948947129710626999 277545060906648734 22377303701658362 868537317551549519 26724346483183570 930808635283491364 612950736394979278 994038204762925261 553490910617462941 919170846071093047 980139146622038954 2866229699821717 691349655952032995 989711414165579798 393307726343726570 712930390104625464 255311967735612919 722843778661988313 478452033643781807 997264151635652162 662821546620490445 708575231572481729 446554846574753259 671991644117702252 802270860202936101 97786737298186808 985578159661720640 1979669150015694 330931198999351143 588196924528357613 189903863569169762 348027750919383291 422510555318878067 948720981231202494 472132681116863896 828445342303784712 965213221848897713 782022368561293652 77796902216986519 863226932483117897 40624353580464687 903234336342423733 874386022247493258 13112524738700444 442411714660633881 649604645052756346 611135974338766413 37443233085933977 596010789869363348 118556477875569870 796808208662940448 913586436910512246 382915752931213774 155495210500945578 350917303270599180 345601537147078530 356202241635120063 189938850603704459 29510118320799733 208007338669754782 823433870778872123 516373470652740700 948737195002406731 953520133255088609 934450615039926339 593556609674222021 121821167845678826 774866311240073772 561475841835204082 619796850801199746 668836281232043789 121067967775612709 354812472993884677 808276283193299615 314427068611031929 689542514838903144 490640598848566594 915573942178276581 87216582032212732 39769741890744216 763863550091772103 944256743232142752 216268898659154329 280288701047984297 341610288205191538 637670996604325654 426519323102759149 342523274184434066 879236162330602138 10674840815277730 428597972874995369 481277237113173020 358305433964739914 359793375053066420 12614431745376861 93958871613885831 92100321978971042 951195863658814143 98821725464360310 567406618093495243 180001932660638445 407450464700995081 371377466704363328 223692534193873945 512621105112882521 477831472933159325 67585013381178914 379513504223808534 558862353336635953 698950666349484326 892286752211077400 583702184801418246 958439261013299168 915180968640438041 939100501031631333 658540176248335317 7205295364697921 928513802161377933 135178725285952424 474119173778110017 558733143895289654 550935339652763211 751865174401053345 516596006755431175 899301265160343206 312987263591738743 448621401786589889 789056746885931908 278835230665310228 858888899074473201 741999437209753743 405356692037377309 98564454014584690 721728163009970198 334622693705847633 811897138891917740 18051452154889639 274393681999384411 127932923565592657 421202645587441336 230597224307918451 741851890723202549 896076145646543777 104306412032539161 986595969418732575 731626237370779113 273185387856746624 898596725491407569 638020429967425025 334905909017157750 610394981788174105 209708209301817895 683718076551780603 989137506265355258 709272825732528406 918386901492363838 914523431491506158 147570016183092526 185492394199308429 627372319896458485 606472718597740470 242632339248244533 647391802533484315 252852298238409786 319636384964068345 778002020592926942 192180120005633483 223941918505910517 823809944846640362 423109495638959818 469526113085587649 223742620014199095 140337712271354339 969584436319262987 876234323482798894 747144278072610890 422551087970198115 312350511346213566 75721075163001362 689201334975002507 92126141892115452 936030071534972067 575485198353557545 261315326363062837 260628515696705751 26301430820300049 499200824672431588 997673265711005470 333754028881993094 809069575349241357 115357451568704447 754951979746804992 367872621408415338 345912139001959966 129524880210595307 292398928158313984 647120357417460358 926588457985117723 58240192983947235 44434330502116487 956465399859360648 880416249246101929 114842867210403831 551463446369610378 560201794847763942 480784855726896885 738850690455961858 691357110983430243 55660549038973057 672372416175649026 368540113949445376 843440253880068514 162485787182173841 577236647457676412 957782312552141295 659898161842659939 947718299580044894 473210533091982795 515998036283385319 138883681333971113 269396342167461889 482659736307723751 511201718342341580 436430380838390873 509144936709399521 409622800789345479 177071211241020063 790673863888113641 673318732100703892 45040772450182521 327682360392676541 696871318096917912 830261198548156985 542824909570142709 682269921960645808 920607649975572944 123086040671981016 417197483278465400 863895495647536420 798918190221761978 659965798208169632 955692566730472991 810525297544279593 667514206339670555 417445370191359665 272665053619273965 925042188175077025 810497697168302655 636015989882891637 142711003792255196 117148715036848049 564564680795415539 859047984840086153 171603035176445827 692641598142235515 36110290621791035 663493891378340945 952747759246403571 231064381179830207 691770843678797564 632676030839544056 827264176247346803 306523149280701795 944214067565638470 468034991058076036 488015131845451561 899712933961004414 642093824650475621 73748472363009700 421652042693056038 675463671957451927 989833564385363725 596905243051906642 997425768291452571 428931742188558046 983995181987653516 637324082079531023 71652649992054034 978487056550230981 20820541856029031 219935237299697751 351768994025752386 777096970291731327 848627671905796134 350447587408452392 289172009423894578 953897580625972570 857822370053450831 277304193574497555 182617233330730398 905048503042730035 818081516669292407 954430595031314145 296133015230772132 376472787138807643 499862029335170286 391929903695427304 666898195453756945 6356394172390321 482043978822498174 597934496095114721 379179610920356331 764689364082857791 71899833010245264 76532929812993170 784578022109403538 734879868415117641 45716909996356556 714864776936149230 730620066151932722 959376236673276875 602903098294244647 609800364542140677 111706720581070911 207810277382063959 963835322697998722 368200976130675587 216564198765775180 587682185017177402 996865970796188140 735382772683146835 893791416080546292 722671108754269601 685950690470585444 80633039507695759 911192973753812023 42507536321369389 303901311354728506 907635564341468326 861583539640659305 475363550793922541 921665373838001632 491364820323833813 755144627728913419 385570373692652604 235666196598173359 241007572570260835 603938122588178933 897805514579407025 667532108140720125 210442081367165944 196528947356319362 792225083632023366 115974648880936338 47485646631849172 404260472471542623 487464297441827740 236017136277080136 87602367924012442 560217893467117195 28179493361557482 232842886446338134 48724839627643569 732029968029726723 194850299322547011 119559103861454966 707743768601044459 838979245931872436 426639054421130614 297036597833579701 592844023815342058 759489436578899306 389395444459397629 240336679741756767 304069325038916106 655047592549769906 334912912588962272 893918331509053362 969024513559649636 958207202862596866 277099686537989180 64761948805284433 35039667639867707 320849199254658806 701147179864285161 189076474951536442 904664855008469029 20055218969683519 661906235229515882 503180041777501332 338699301903266928 412776817856534173 186723419194483402 779091322561643630 822089175693158060 874946391970128032 53803386475905559 174725497986790457 269851020435115787 929275719316604577 654702621586077567 616349084341292040 519332905455570301 721674994107963869 767756356506485749 165245696204150746 877265182583413442 699007707208101227 653646281661909013 979109357972517783 687973972276066020 82659647945950480 241334228302931318 889859575136519912 319121175691111506 459522288373485324 24116818950451076 237889606778739620 743894562682726497 203529118338195109 294024049829899532 765689758823030707 418488553466294410 495827820236401750 121482721489437306 292262007559079322 513498048768284228 486252094208562302 972378104944501510 643613797433784127 144560507069969188 296011246032139748 347889794114542156 228503807517330151 923045119810912027 965733919575570344 694895760658065968 669301235819798477 541253382630271130 692752487202263052 593478165699168329 99643971023023265 52354029432938552 52687783922625580 884507529061693247 953914962388917414 742142254263297694 40394992350955347 245671512796085167 224545508894216187 224037761987485591 852877289450645693 985618112926004351 268898808149216480 575697801726614461 324806636403897081 643571207944835333 249738456476915337 845605792195303043 359700743977932005 136780032522398968 936555757438273078 942354535593745513 805806427085002412 452636546722695987 631422381076263835 527049379448414961 925520441790084832 477955795674501088 198063761011636425 842159422138481586 998897845239056004 808338183981840071 770549021271474440 655322998600412678 457237856762931161 984642304751243423 559818149407085003 911426760623159913 882638553216173268 275823909279606779 340930960007629276 923658141087765871 405303595812572205 365433712230035033 190516693771728914 740195569666730908 867588204997599929 64491392220369712 497931492432599447 21430534441794392 503241328064393411 535255031673890665 337723056956715019 738741235624097273 548860984813268130 535191095002258427 330789161248487887 309459709956103263 988228573576409620 340379922568687628 554037315452229714 292212336531383355 213477428475647045 112295806442318166 347184214947648968 584769823204236273 448583123403765448 821512022224503224 555444523078583415 162843438772119448 615681706802286675 215094349783621473 472250595429857131 644355970613623342 244700016886828511 233966461890688249 786992854923272825 208088390612674458 408551393448957668 353262990428421532 145159392472419941 813673275331177318 65418040520751266 797815314333646505 926319619240105439 943375860805364856 14958124815728076 499261581544638542 245578036214059948 142510683696427782 666981220325115561 969355847192864572 789144719510982031 254454825866923246 515767883183578158 198048021284055576 982441208342099283 499464210843277710 28508653618101815 212510030904190714 852676959869700937 450043271012675203 326313609502176700 802686162151445365 735587285224567174 659558263486802450 416191851769110309 107020760996437143 876109164109829782 332553213455720279 790227778401046861 56065414227761088 119807066689172067 553378247124352846 217170009479182423 386271407563916707 175562517926550577 736286981494495742 374544410426044051 739387013732410884 145094849466195077 765027534234227428 531871090444677652 51482999311684021 296479829532432595 649137733715556591 212492533897573269 42688057874938471 762387373230451282 547805459096249656 913100627773315488 117367288375208035 129639947909251222 735510420359851076 574625978338330774 290617137296443501 69441327410270399 964664251201741266 695681426116005685 343821303627208569 93169021430025022 287947448299907942 880451212093738916 250431770320775851 498340813318966828 706181030368121178 712661596123670586 514847805673288053 820645746335376164 380808583201272396 611267303945620459 268998214181212306 592482397158359348 325296951144677854 618499078679321628 151952205688973833 130640017475112801 881905927220788323 890350845732128076 832218246736058534 598362254295253392 425059918034195372 601418361253302345 455695233520976082 986961550183936071 191646595916102616 496005807854521061 128782953263655084 525613869121389568 987752078099944776 363599728589582668 345346761361867962 430541639790287664 898369459926591848 851301204099728272 897002688587031292 89532713352009958 604217611611202338 237991109586314223 847079999660218773 842275233130724487 187307974983793062 27204021517951754 292751036950168555 717521006567721011 652608271872998117 936841407639395131 946308196793253481 848867327172827267 428595797093971045 794651009888677900 555123460166615889 94774748265172984 990142246287812906 57183612272115486 805003349571015367 791260110980663737 275221328348775451 942441183713650855 809979343448731394 122279200782668740 429398742596321426 357344816779252801 29168308950589257 119227887441757603 281975650603635759 967648408816029112 372580429877607022 994975218687681253 994717481899926281 371294008309062177 696627956385472 502454387707548992 106170553738498391 230819303602182842 860500759658342022 744632892790988337 677333807043263399 641599675176199615 240537830738020446 813561842175807908 474760037683354478 590877964874912619 132869644414253389 950446044581635277 282542992634612452 377011208073489784 711861217230219628 182308456864534434 11283301655531472 44803513746462485 608658035963933561 255058450921129031 80550798217010102 223218783736754744 42604372329457194 945248997387878886 912190335372323595 299918165675488374 29006369313044773 431027494245828173 105802071132107190 884644189381913295 604451937338883120 882044668810267126 301579655041114092 186798307214535530 621492971302855790 437721341626696351 235594992358861780 356404310183741345 405017319285789337 70104874073917193 43094218228884119 684692464001381588 366105799130486028 149802654965589810 706930855653465579 312689839751544202 719946197106678099 34870828412067362 201618620383920107 540019231203789695 24148862441579974 125662037516176628 480912280391587805 34071718852981810 99469796754834629 604565966766454744 368545165331480141 125073579859956248 212527153919565518 190165888046870046 801974191303765028 882220759628054860 378903495528775926 96057000139017964 924762141886982396 667346229245111730 837979880110737891 420447453371158307 816039694471165777 891206916392893410 881075728953524326 608295981653794530 543866158413584737 525851251491998259 263143881281683673 258499810384527277 411179821328397253 727446800170314773 872015275974703592 459988682466839955 552128418149988296 594096520296443273 24202677218730968 407518507137253344 238535532713145239 421311562974893626 885761626723253843 384887542165446868 685579718162311217 172017703700268513 854102103129058793 827559745420591759 536938435230582225 99722249351228706 356159472382407589 876619059270395071 565890983481484214 425934995193639833 976051233651915174 8650788234516826 316349126620178284 917104875525583483 554902568930744975 357606678921499141 755310007365895536 917335518668643415 429614234489487197 511177333244179273 642451032658552821 246885327572120569 631017918463952367 154001229103677723 423161984538808669 537719836412113027 50394101731368715 55841153456448993 407024474106829519 544580725851618638 137281447120464169 365561054161292220 758045827192168310 521752034701831701 745648745558825567 139852849230147976 26993899027500047 255718689715891506 554736307856613458 781768223315018695 156604625977538318 57259560768981847 585201984404289688 781552262221027686 100059508958477469 928352320419606774 984102273002750740 530206585900962029 64284073579428958 239733522701308504 418167674381577430 479398146514284480 939540596153194597 559309648986918389 712604670259704144 244637697932476212 88665428288682778 378921305951939242 796673037483541709 657577767450717338 895536057620275111 352718606001337211 193662476739709595 600156864940615764 681379873282408752 317683911731173971 122313013415581840 783256014469543693 469205534450931068 42694854113070693 873380060930307343 421802632686897322 813289152038125206 212306217560884616 417772364418819299 489827553274494919 323159399376178403 252776775793588829 885355580524019906 109384027354371425 516384975862554691 989382415346834973 704068857577526216 607932850915913684 423189008631504314 349104533914133017 43376524751135040 852635860332491610 557737775530696642 813203993103111193 977033586164826471 637906917387492556 889132745038731249 395896145380306049 335545702434846599 464863724461082024 630265237063482981 355117357438090719 260602723169228664 788348060093751512 54661005164669039 998913389681840913 957891646475925838 2356 1000000007 0 1000000000000000000 1 999999999999999999 2 999999999999999998 3 999999999999999997 720692 999999999999698400 218394 999999999999006297 162419 999999999999348589 150442 999999999999273464 181241 999999999999740982 84650 999999999999198937 730274 999999999999703246 904364 999999999999490500 398088 999999999999190967 871737 999999999999679432 899768 999999999999505369 308173 999999999999760279 328785 999999999999812064 988904 999999999999073705 549700 999999999999025164 309997 999999999999345243 341534 999999999999452660 751904 999999999999315856 809075 999999999999495940 924952 999999999999538634 887153 999999999999306313 12900 999999999999161001 407249 999999999999169283 282977 999999999999388194 895746 999999999999363069 287967 999999999999474060 212596 999999999999854852 618814 999999999999572037 412331 999999999999441645 954283 999999999999878092 909945 999999999999949153 856007 999999999999928661 672233 999999999999707420 63152 999999999999055870 468291 999999999999609768 788021 999999999999553868 630363 999999999999818692 853757 999999999999218366 825058 999999999999382157 316878 999999999999056263 357227 999999999999616374 71690 999999999999647086 302489 999999999999070884 965148 999999999999378662 135804 999999999999868938 174785 999999999999662886 731479 999999999999237723 299477 999999999999219214 93759 999999999999810931 844408 999999999999123334 250221 999999999999402635 257046 999999999999014450 546104 999999999999648055 620780 999999999999908557 937391 999999999999254222 750296 999999999999838193 681660 999999999999760530 578435 999999999999600804 274630 999999999999644287 839994 999999999999970003 555085 999999999999712072 3762 999999999999950296 838370 999999999999566533 547390 999999999999322439 490722 999999999999684473 629498 999999999999843499 769076 999999999999879965 610162 999999999999972857 350236 999999999999325402 982032 999999999999211290 985286 999999999999105129 638785 999999999999385591 152935 999999999999202694 514170 999999999999742601 469644 999999999999098559 344084 999999999999819180 919946 999999999999092257 221939 999999999999055732 993835 999999999999889416 805786 999999999999085923 602800 999999999999810168 758873 999999999999159773 644032 999999999999372074 247699 999999999999718033 584755 999999999999776314 883489 999999999999414103 21898 999999999999293213 270801 999999999999236484 447049 999999999999430317 25036 999999999999870709 107512 999999999999087407 265636 999999999999374348 896956 999999999999486043 220863 999999999999155280 449777 999999999999250433 252084 999999999999698960 341441 999999999999767808 19545 999999999999954060 747722 999999999999629258 159269 999999999999436627 252617 999999999999958069 19943 999999999999712727 76829 999999999999655494 327465 999999999999580631 843818 999999999999429862 317295 999999999999986819 497145 999999999999105168 660952 999999999999775997 949207 999999999999319943 611080 999999999999498352 100245 999999999999069281 587304 999999999999216807 243525 999999999999408626 75304 999999999999822260 268189 999999999999579725 312891 999999999999657887 170020 999999999999786814 600267 999999999999989116 201623 999999999999644835 689135 999999999999827192 146305 999999999999000589 163015 999999999999937258 328153 999999999999092366 60262 999999999999680088 838164 999999999999649271 734327 999999999999214999 187592 999999999999100588 86421 999999999999335903 192480 999999999999182322 293456 999999999999409209 276412 999999999999264522 815195 999999999999553042 66631 999999999999559644 622103 999999999999146191 558466 999999999999120558 977646 999999999999506684 653112 999999999999991698 250808 999999999999658566 726020 999999999999997448 328396 999999999999029367 822074 999999999999559546 78210 999999999999985664 294560 999999999999105678 661277 999999999999570435 687055 999999999999507957 21010 999999999999258108 52703 999999999999056591 332111 999999999999732174 610172 999999999999870406 762781 999999999999124360 835442 999999999999838361 87320 999999999999849809 646746 999999999999545769 317207 999999999999022454 881006 999999999999630855 282864 999999999999123122 802880 999999999999534018 237971 999999999999755350 402329 999999999999437316 469127 999999999999300582 689015 999999999999188187 745542 999999999999725583 270986 999999999999475103 636291 999999999999368831 837916 999999999999625426 330711 999999999999913789 95695 999999999999252979 235892 999999999999932656 518355 999999999999337790 167180 999999999999532155 759449 999999999999147260 851697 999999999999248820 159959 999999999999109639 120522 999999999999988264 500310 999999999999347701 649096 999999999999252044 848728 999999999999487380 220355 999999999999375857 530998 999999999999129667 848609 999999999999399758 571629 999999999999756822 304441 999999999999121265 886635 999999999999870560 79893 999999999999528236 98316 999999999999004070 99090 999999999999006053 523536 999999999999809271 426801 999999999999308446 610954 999999999999961396 676035 999999999999605167 794755 999999999999375906 290430 999999999999018739 728013 999999999999945259 352250 999999999999898270 599446 999999999999361092 332116 999999999999352466 747256 999999999999061622 32664 999999999999701408 394479 999999999999108365 231885 999999999999215083 291885 999999999999129270 766532 999999999999490999 230368 999999999999121858 983654 999999999999054719 26784 999999999999773055 875324 999999999999115452 598921 999999999999636002 893514 999999999999839399 298107 999999999999667377 697691 999999999999146381 593479 999999999999864400 36849 999999999999460284 4406 999999999999784219 367544 999999999999346402 272079 999999999999940634 9076 999999999999826515 208152 999999999999108847 841744 999999999999543550 240255 999999999999868843 325503 999999999999692166 621092 999999999999121579 73505 999999999999739819 816964 999999999999062167 978537 999999999999173038 200299 999999999999489816 951286 999999999999740393 617700 999999999999501228 632719 999999999999574820 99862 999999999999162560 954197 999999999999246728 812410 999999999999018966 205623 999999999999220270 59678 999999999999656555 119958 999999999999618702 885757 999999999999098956 946889 999999999999611653 100332 999999999999855292 979988 999999999999655789 699034 999999999999075571 507519 999999999999169592 527456 999999999999071172 543917 999999999999777815 863018 999999999999631446 26223 999999999999989170 956029 999999999999566421 947862 999999999999155915 879324 999999999999802550 490258 999999999999424031 578051 999999999999386472 263597 999999999999338182 424818 999999999999145755 803428 999999999999671120 590937 999999999999277229 119010 999999999999376889 56384 999999999999584937 886265 999999999999543486 111875 999999999999699391 347994 999999999999139282 642470 999999999999270555 568052 999999999999446305 686147 999999999999246459 165056 999999999999153403 594940 999999999999218802 748290 999999999999963890 755890 999999999999261936 352071 999999999999365429 443418 999999999999531444 422741 999999999999711564 724943 999999999999229687 224995 999999999999321461 668914 999999999999515332 277665 999999999999873687 791787 999999999999577043 453704 999999999999619557 755966 999999999999012282 406320 999999999999179747 758258 999999999999284483 940140 999999999999608685 698270 999999999999062363 946826 999999999999541081 26563 999999999999780770 343606 999999999999114834 510592 999999999999615315 721684 999999999999005278 419668 999999999999856163 947637 999999999999736579 683522 999999999999705564 996432 999999999999765756 354076 999999999999877005 409249 999999999999908873 955926 999999999999705511 949864 999999999999112645 898186 999999999999275968 549448 999999999999088438 381751 999999999999017954 765612 999999999999188212 515450 999999999999647927 716992 999999999999177082 939808 999999999999966644 922346 999999999999662350 489561 999999999999007487 828739 999999999999296112 127500 999999999999229126 850770 999999999999138186 688630 999999999999373196 507805 999999999999639887 408102 999999999999678157 223392 999999999999534436 752794 999999999999010814 137991 999999999999912954 307611 999999999999252223 149112 999999999999685976 679549 999999999999495758 493547 999999999999655220 36349 999999999999359172 554250 999999999999182892 698863 999999999999141162 65356 999999999999044975 210161 999999999999442404 549747 999999999999234013 925542 999999999999782572 333887 999999999999328178 333295 999999999999591276 828583 999999999999922019 18179 999999999999482869 782317 999999999999875896 34307 999999999999160865 381737 999999999999831066 517164 999999999999665194 807603 999999999999452900 837463 999999999999645865 127809 999999999999773380 19240 999999999999064573 645742 999999999999899019 735590 999999999999120855 644787 999999999999856351 83138 999999999999651855 392654 999999999999183316 242246 999999999999358180 912722 999999999999902180 964389 999999999999192241 972708 999999999999139444 916583 999999999999640908 611672 999999999999882850 992363 999999999999086882 793267 999999999999259063 883080 999999999999301865 164425 999999999999290327 920276 999999999999136295 502386 999999999999656544 540052 999999999999357921 64159 999999999999306556 993792 999999999999569407 491352 999999999999936557 168200 999999999999005116 612485 999999999999684182 922720 999999999999077797 118643 999999999999178833 507445 999999999999268735 174185 999999999999547505 222879 999999999999153982 996935 999999999999631997 17787 999999999999008336 82681 999999999999569992 852748 999999999999625295 451139 999999999999578327 546932 999999999999273698 798500 999999999999269747 437770 999999999999647921 120296 999999999999570766 304214 999999999999153753 792760 999999999999794973 947327 999999999999839252 564763 999999999999135517 619644 999999999999767188 879834 999999999999148601 730987 999999999999190919 767225 999999999999684949 693451 999999999999696020 483065 999999999999899246 98804 999999999999683172 624356 999999999999127594 794527 999999999999829627 314496 999999999999323019 310265 999999999999756520 648235 999999999999793692 280788 999999999999990985 723382 999999999999649450 449832 999999999999040074 786825 999999999999452364 811008 999999999999862942 896674 999999999999973920 284989 999999999999522967 983816 999999999999356293 288910 999999999999661822 116602 999999999999176550 7656 999999999999500088 356442 999999999999031756 237474 999999999999157196 396266 999999999999965999 342548 999999999999631038 389497 999999999999750568 844722 999999999999209265 683846 999999999999718529 517573 999999999999062452 570142 999999999999967464 88358 999999999999679701 102338 999999999999456463 672689 999999999999051784 762136 999999999999983593 967260 999999999999642803 793711 999999999999893189 1676 999999999999621386 212863 999999999999937910 639356 999999999999543996 398853 999999999999208687 159831 999999999999130740 82833 999999999999429589 648978 999999999999260027 310867 999999999999600939 572314 999999999999556274 623820 999999999999942093 985869 999999999999875650 830909 999999999999486549 846722 999999999999161719 31292 999999999999527681 203353 999999999999123928 607328 999999999999816356 676785 999999999999426688 581942 999999999999171909 118797 999999999999732614 849613 999999999999938045 226137 999999999999949943 674190 999999999999791669 263593 999999999999632305 591768 999999999999914242 201479 999999999999091895 586343 999999999999121869 516883 999999999999017318 613593 999999999999879188 176093 999999999999811481 282097 999999999999146036 889008 999999999999682328 92236 999999999999455920 23101 999999999999139775 988214 999999999999111281 104739 999999999999674260 610273 999999999999829358 64130 999999999999454464 818578 999999999999687012 72880 999999999999281174 199032 999999999999464408 664961 999999999999562548 953307 999999999999437101 779703 999999999999711466 73689 999999999999780523 532686 999999999999318197 794730 999999999999620522 428525 999999999999974407 848393 999999999999391750 267783 999999999999130233 728365 999999999999324260 301422 999999999999505032 923108 999999999999984229 304105 999999999999712887 634402 999999999999174033 815074 999999999999852878 122994 999999999999214884 218985 999999999999506931 558989 999999999999744183 155169 999999999999807286 330394 999999999999318981 184279 999999999999529251 752850 999999999999347122 511978 999999999999120872 815593 999999999999223059 19092 999999999999619332 765531 999999999999236202 279305 999999999999200921 543990 999999999999927131 839594 999999999999744539 948262 999999999999045589 563070 999999999999759888 383557 999999999999240145 631098 999999999999248381 145830 999999999999086245 92890 999999999999960805 80011 999999999999949263 437555 999999999999322121 741322 999999999999557319 119398 999999999999747973 103923 999999999999611565 697874 999999999999314023 864147 999999999999100917 32438 999999999999681715 524396 999999999999962637 466431 999999999999189117 295675 999999999999337392 977645 999999999999362731 949466 999999999999048078 972121 999999999999846425 40303 999999999999535049 578591 999999999999296209 175375 999999999999929160 85331 999999999999586151 311321 999999999999917454 848250 999999999999561371 35716 999999999999573689 455815 999999999999820978 931602 999999999999804912 555790 999999999999494797 828629 999999999999399743 814004 999999999999965980 48201 999999999999877721 259006 999999999999945802 157053 999999999999676175 395497 999999999999646548 562035 999999999999131308 343858 999999999999585485 717467 999999999999054105 158914 999999999999020837 357262 999999999999144020 828430 999999999999270592 780888 999999999999423577 820275 999999999999015259 274875 999999999999052144 331777 999999999999983468 455635 999999999999037789 990331 999999999999221762 461636 999999999999825351 617677 999999999999985203 52209 999999999999312128 296877 999999999999049295 289232 999999999999778095 162244 999999999999792914 656281 999999999999995323 557674 999999999999082724 172837 999999999999140983 313141 999999999999340566 126787 999999999999428701 75313 999999999999673792 895465 999999999999464994 623415 999999999999731846 248215 999999999999228248 850992 999999999999185566 147673 999999999999014070 923226 999999999999591531 560464 999999999999867780 425182 999999999999047206 319158 999999999999106931 157592 999999999999435305 61286 999999999999150000 858333 999999999999932753 273499 999999999999974842 421624 999999999999944959 344827 999999999999723531 865848 999999999999503861 285212 999999999999406319 645301 999999999999969531 886618 999999999999085366 219258 999999999999355138 739357 999999999999217889 863650 999999999999321300 252444 999999999999303112 891460 999999999999377267 307741 999999999999661908 393942 999999999999495956 859780 999999999999940726 436173 999999999999846013 904974 999999999999989790 217186 999999999999683648 716779 999999999999398964 2112 999999999999900796 109510 999999999999716033 784347 999999999999712946 838082 999999999999668827 972732 999999999999874595 170758 999999999999319715 737340 999999999999665433 590111 999999999999103575 457394 999999999999832870 908517 999999999999755655 441319 999999999999890807 190371 999999999999561172 37009 999999999999568175 420407 999999999999451002 337734 999999999999078559 126955 999999999999109519 584544 999999999999054181 513659 999999999999552649 47238 999999999999362031 317337 999999999999910954 53500 999999999999006894 270289 999999999999733084 231794 999999999999380256 130507 999999999999343924 190556 999999999999681151 396847 999999999999559254 816305 999999999999565882 413034 999999999999631129 518231 999999999999950933 726726 999999999999195541 420081 999999999999642771 72209 999999999999592327 878189 999999999999172974 978095 999999999999762281 699685 999999999999893717 410146 999999999999744575 457545 999999999999582731 29143 999999999999990244 984912 999999999999391703 148614 999999999999351733 314030 999999999999513619 862526 999999999999609387 188905 999999999999256128 54507 999999999999878873 316567 999999999999275231 253327 999999999999483503 138341 999999999999695020 616003 999999999999040718 196404 999999999999654267 870534 999999999999620229 648538 999999999999818624 146570 999999999999952564 463344 999999999999160048 68488 999999999999979030 407466 999999999999642844 925338 999999999999804361 588731 999999999999665272 258458 999999999999564569 225201 999999999999793336 173919 999999999999547291 39137 999999999999192043 830457 999999999999066516 928027 999999999999873440 998046 999999999999835427 885132 999999999999310772 70983 999999999999869497 145900 999999999999363706 683250 999999999999084305 162915 999999999999862580 807515 999999999999403539 669202 999999999999201982 708505 999999999999914155 653277 999999999999229427 90927 999999999999736160 875693 999999999999539054 240284 999999999999625583 906459 999999999999817830 520034 999999999999216255 13443 999999999999339338 529849 999999999999116215 552969 999999999999913049 39722 999999999999982359 536918 999999999999890781 536530 999999999999482054 231016 999999999999329256 810894 999999999999345101 173863 999999999999166365 78063 999999999999562371 468216 999999999999802178 513125 999999999999678410 289192 999999999999953555 674985 999999999999011064 551558 999999999999707226 354534 999999999999045424 315046 999999999999769265 653485 999999999999864151 655250 999999999999722655 884807 999999999999251205 158862 999999999999103892 574928 999999999999875744 536441 999999999999263867 55439 999999999999020773 198005 999999999999314534 61076 999999999999042188 668152 999999999999648260 849818 999999999999229426 696837 999999999999420737 50140 999999999999287599 349624 999999999999114050 946254 999999999999170172 615909 999999999999887446 620732 999999999999038607 853543 999999999999688448 899467 999999999999893542 730386 999999999999510077 488308 999999999999026232 464046 999999999999777898 293373 999999999999207314 617508 999999999999373961 902219 999999999999923836 491747 999999999999448855 121375 999999999999305126 330344 999999999999002419 64692 999999999999409711 883739 999999999999754549 631782 999999999999114676 649688 999999999999464785 957006 999999999999129365 548962 999999999999648633 181220 999999999999602032 709159 999999999999724335 604050 999999999999733583 684151 999999999999758050 144266 999999999999427916 801267 999999999999863285 206618 999999999999424082 922092 999999999999696785 865078 999999999999512344 585575 999999999999605532 837727 999999999999955630 911845 999999999999433640 264782 999999999999925151 64130 999999999999585936 667075 999999999999163218 631471 999999999999278752 105080 999999999999336501 518855 999999999999825868 328062 999999999999992256 700280 999999999999536007 149242 999999999999069956 294720 999999999999145032 375962 999999999999984873 816453 999999999999346349 89568 999999999999154167 720291 999999999999014038 291509 999999999999475620 730094 999999999999964850 248761 999999999999560791 815207 999999999999504050 870750 999999999999190380 951867 999999999999447798 887890 999999999999287772 554611 999999999999352442 898553 999999999999756693 504297 999999999999830110 815812 999999999999244563 446554 999999999999851539 587619 999999999999539022 260135 999999999999257467 291836 999999999999976480 634871 999999999999154465 899572 999999999999452440 134452 999999999999581970 255831 999999999999701603 599489 999999999999452897 499974 999999999999937117 258119 999999999999311337 753788 999999999999353631 283823 999999999999294210 674522 999999999999989267 834668 999999999999862479 274629 999999999999797641 57858 999999999999272411 853675 999999999999697643 18581 999999999999954661 565539 999999999999851400 123447 999999999999492992 536616 999999999999718812 577579 999999999999259533 269124 999999999999753627 951153 999999999999958548 861014 999999999999197424 792347 999999999999146440 970015 999999999999742180 431878 999999999999895048 308581 999999999999542660 73315 999999999999756963 816059 999999999999487690 684806 999999999999890522 62135 999999999999447128 610381 999999999999809781 665982 999999999999612291 431882 999999999999210787 758688 999999999999510047 693091 999999999999701778 872368 999999999999007876 415756 999999999999921763 572111 999999999999111625 417946 999999999999823464 97338 999999999999129616 389425 999999999999035687 708302 999999999999074117 617258 999999999999876590 269486 999999999999632588 267743 999999999999119633 411694 999999999999256139 781995 999999999999814940 133493 999999999999179812 23585 999999999999319530 968227 999999999999606569 396878 999999999999489781 694197 999999999999338823 196588 999999999999067994 53954 999999999999656062 698571 999999999999616368 397030 999999999999408308 914560 999999999999618946 422224 999999999999909663 194476 999999999999470162 331106 999999999999754308 817927 999999999999500249 506203 999999999999829865 746316 999999999999894486 948516 999999999999578708 981908 999999999999923726 30830 999999999999757966 966871 999999999999682692 578528 999999999999649183 723247 999999999999973511 909943 999999999999869772 297613 999999999999966683 365593 999999999999308297 776009 999999999999912171 192716 999999999999904410 798021 999999999999304592 235160 999999999999990886 85467 999999999999872716 287975 999999999999399870 887154 999999999999419398 952842 999999999999655568 941827 999999999999503560 811449 999999999999435211 238377 999999999999781438 237319 999999999999748497 892542 999999999999064983 901116 999999999999783518 473124 999999999999305890 975814 999999999999673922 440359 999999999999993725 802892 999999999999169266 987430 999999999999495528 605220 999999999999393406 873836 999999999999494995 333290 999999999999964095 471203 999999999999655927 12187 999999999999040029 621599 999999999999160744 609700 999999999999497958 179690 999999999999095584 696850 999999999999270625 166695 999999999999846093 766304 999999999999778348 888786 999999999999274025 719477 999999999999182765 533153 999999999999497749 571598 999999999999419282 371626 999999999999642280 24723 999999999999266257 163662 999999999999706876 978670 999999999999004454 108293 999999999999961962 776114 999999999999269362 849554 999999999999029506 432642 999999999999491873 595788 999999999999344413 334774 999999999999293999 199172 999999999999151318 272 999999999999596790 666902 999999999999926692 370275 999999999999934716 985678 999999999999333596 972778 999999999999659817 751398 999999999999179184 913607 999999999999418882 925768 999999999999079253 275760 999999999999212997 698777 999999999999242003 527106 999999999999842264 283261 999999999999262241 892727 999999999999310306 392009 999999999999364205 285715 999999999999628704 770315 999999999999398485 460087 999999999999309290 10861 999999999999463643 813740 999999999999611652 951126 999999999999695532 511124 999999999999433714 32248 999999999999158798 500912 999999999999083270 221723 999999999999303175 490341 999999999999186946 820918 999999999999370924 915265 999999999999524970 271486 999999999999718334 133983 999999999999956645 392446 999999999999117553 221766 999999999999935064 201715 999999999999623919 45118 999999999999872965 872601 999999999999176177 37430 999999999999015881 37600 999999999999215334 576041 999999999999924430 665481 999999999999229637 897256 999999999999073147 17664 999999999999290271 397331 999999999999687852 292444 999999999999143240 497692 999999999999118000 716414 999999999999978481 179596 999999999999475054 465553 999999999999265138 20174 999999999999348165 854981 999999999999255935 779432 999999999999254495 884725 999999999999189558 70422 999999999999295746 687938 999999999999885357 546707 999999999999810833 739316 999999999999018604 274031 999999999999838116 267032 999999999999520970 920335 999999999999671375 864531 999999999999261062 85318 999999999999010632 638054 999999999999422374 598673 999999999999177100 936631 999999999999027513 381998 999999999999515133 693501 999999999999094679 265066 999999999999005818 845489 999999999999654005 796162 999999999999226795 806174 999999999999355414 628545 999999999999333844 595056 999999999999706860 578738 999999999999393429 901220 999999999999097358 463914 999999999999477832 25063 999999999999080039 926684 999999999999767369 285028 999999999999917700 251902 999999999999040761 1548 999999999999175571 504420 999999999999533671 217182 999999999999015068 890533 999999999999555618 139565 999999999999620957 88810 999999999999663992 79801 999999999999415424 378369 999999999999405823 642899 999999999999528236 344063 999999999999721449 315184 999999999999173235 805220 999999999999371922 806949 999999999999925395 156224 999999999999050261 704241 999999999999529839 885174 999999999999939110 793782 999999999999339040 608052 999999999999163557 565105 999999999999455339 263175 999999999999714255 646376 999999999999196798 69714 999999999999561006 451909 999999999999514010 902966 999999999999636061 69120 999999999999040838 690544 999999999999082880 837276 999999999999540864 44282 999999999999220711 282298 999999999999094228 25546 999999999999232541 807009 999999999999340500 129460 999999999999515813 301195 999999999999156011 194567 999999999999450512 527084 999999999999867712 222295 999999999999788757 659699 999999999999348890 188032 999999999999234719 550138 999999999999537556 974911 999999999999874195 967258 999999999999612445 545105 999999999999559372 609450 999999999999016470 493598 999999999999070848 847217 999999999999115227 65419 999999999999279560 158606 999999999999881841 784409 999999999999409415 904827 999999999999519075 688460 999999999999338605 968461 999999999999511006 784470 999999999999833626 727166 999999999999277496 852102 999999999999690739 280437 999999999999004011 357773 999999999999936977 654762 999999999999160482 481868 999999999999671892 226432 999999999999981501 424386 999999999999013778 81807 999999999999423994 702318 999999999999377908 401737 999999999999935874 238097 999999999999598055 67804 999999999999104039 478465 999999999999420417 634782 999999999999362471 753194 999999999999206621 313777 999999999999582743 495033 999999999999647185 47325 999999999999462950 182212 999999999999733055 999095 999999999999291979 645606 999999999999305220 563733 999999999999966964 161488 999999999999242738 772823 999999999999894530 141 999999999999131200 257526 999999999999490590 65497 999999999999104461 181746 999999999999791546 232748 999999999999691154 888008 999999999999865602 916484 999999999999463287 559974 999999999999745509 996682 999999999999482353 643250 999999999999645866 372048 999999999999073283 592087 999999999999777783 458409 999999999999697057 655648 999999999999361249 131997 999999999999413209 975476 999999999999976694 216159 999999999999816523 195500 999999999999798341 355887 999999999999352997 607002 999999999999540686 409059 999999999999480928 319712 999999999999329799 966992 999999999999831402 541042 999999999999108147 509438 999999999999112438 540050 999999999999327669 259357 999999999999726465 494476 999999999999816945 237193 999999999999779875 409493 999999999999451659 216486 999999999999900768 580938 999999999999397090 298584 999999999999766160 857235 999999999999893528 829371 999999999999094335 744005 999999999999754796 734480 999999999999301767 973014 999999999999463801 452719 999999999999509728 667831 999999999999436091 558524 999999999999748887 258142 999999999999600755 330616 999999999999164908 514990 999999999999917168 760481 999999999999627469 112860 999999999999784542 251142 999999999999891643 853701 999999999999052409 31600 999999999999603479 519702 999999999999934758 800737 999999999999480928 62301 999999999999327261 423186 999999999999455121 355939 999999999999084013 245419 999999999999635033 267660 999999999999347469 116908 999999999999622544 719613 999999999999393920 132056 999999999999870904 652245 999999999999518013 475306 999999999999142715 637427 999999999999844704 353457 999999999999952511 408813 999999999999305562 877580 999999999999188172 877313 999999999999482880 644829 999999999999333219 432582 999999999999220896 218377 999999999999043102 303241 999999999999205206 990738 999999999999037220 147501 999999999999896785 950757 999999999999401214 603449 999999999999701863 215078 999999999999473348 341677 999999999999389502 507634 999999999999072030 88961 999999999999731973 154749 999999999999965737 507239 999999999999562172 931541 999999999999597520 249862 999999999999843248 608489 999999999999183707 400388 999999999999759956 475116 999999999999945018 750001 999999999999476517 498019 999999999999771362 622559 999999999999914277 544701 999999999999198012 589087 999999999999550006 163904 999999999999019986 98093 999999999999225584 512629 999999999999561556 7378 999999999999764320 877184 999999999999773360 606524 999999999999176006 794712 999999999999089147 91443 999999999999629848 166154 999999999999082434 544526 999999999999108681 62752 999999999999337393 411718 999999999999888450 468834 999999999999172452 682524 999999999999224308 140359 999999999999143653 991282 999999999999263295 993701 999999999999022856 953067 999999999999881082 979436 999999999999423373 270392 999999999999266316 93323 999999999999285510 294728 999999999999729529 930066 999999999999303166 297022 999999999999928393 67089 999999999999896546 138527 999999999999963206 405094 999999999999486380 261192 999999999999162706 279225 999999999999628408 612167 999999999999915314 780820 999999999999303758 368088 999999999999139876 447770 999999999999140507 609160 999999999999990333 50525 999999999999098292 276342 999999999999329322 929463 999999999999137756 549142 999999999999176767 638029 999999999999167151 686846 999999999999300732 643913 999999999999363268 110845 999999999999724473 765891 999999999999939406 373945 999999999999740072 749822 999999999999933767 266464 999999999999950305 869466 999999999999687879 876763 999999999999118924 634843 999999999999249866 165924 999999999999191986 418542 999999999999255670 854858 999999999999095974 221724 999999999999482652 992535 999999999999246996 497215 999999999999494022 267345 999999999999786167 672051 999999999999282889 82775 999999999999969032 772941 999999999999975899 671523 999999999999425021 696577 999999999999161979 796962 999999999999975375 596985 999999999999211616 220233 999999999999980041 643037 999999999999058815 253751 999999999999072323 670855 999999999999662544 295759 999999999999281811 513511 999999999999131751 496443 999999999999070025 849418 999999999999249081