1000 262143
196459294168122057 634354265635305343 769826666322937037 727838616694226973 134324075725246619 861721995905645884 784101824876776039 991811055045103578 249047974812567687 193802584274654114 658839080142524394 930467737159650896 122570253288636095 820681595721520748 1152921504606846976 523391598301355399 103536040839349589 949942544938936803 653828109576474814 399174743274623956 67895614595722016 47610822255498891 384036958990267259 474547145936998832 782163491281055699 677434195161589037 293783168561485638 850184464712047461 818228824101382153 637859276725838698 277132865207696775 37131605716328294 814875333406603930 435970918359649561 281474976710656 566820147070534534 80425090606147540 683939661928268684 335186363237936621 306652656717233484 562949953421312 326166538930681485 691773575912996455 751948805262091846 98232577419112844 177132072311873219 646455522473888036 512605813699729133 551031924028646187 191306644022498395 216538170540801748 869155320384610394 701947760025847454 82292729529396227 695976904689889128 179913784541883539 610477920240329676 969899311805747193 901617192059399559 585853154333863290 250962069852415737 454124551881730076 722049120770522183 974388847389529866 482107120173315500 736439731702851722 108370519126791295 117143769002362791 552247592429618613 565395904773531165 860819887782922772 184876584408362428 808417333961211495 294079226074028759 910620982452789592 956938826330306801 1125899906842624 919792468268331878 500839195228602346 241186346332801438 448374134710032254 734074061961956539 954162337251904667 994635409857171021 18456444184318806 2251799813685248 945387406376377135 501650299003223619 378603955190181336 605176079234422934 540851983812347329 339364474202880438 106487824067089291 399604380624309035 929928854096692065 298930323377548794 963118097681695494 603497791988166981 535106501328356490 437907332335823902 141705593224003978 576810280654579822 2199023255552 580802293745513971 209368238501112541 146700789336874217 646772172540033431 356977111530606913 232785830110441527 312758318053763655 801500706887100049 785356141563657147 10795768899541807 87419740434574459 229087552436817969 892784095267918842 485940187488245468 556022202417699865 310651394939468140 571250765096880204 550332524374567880 20020914270612157 631918212128350620 847405450001288394 574911430611816938 101671589861482387 832895652282348857 477763544532261095 792659123718895574 845978052043581848 936084056934113961 422022087121642018 23218582395437369 875752852612696805 733916623572948979 280554030006543136 645608021529932480 173814617676334444 300098241651466523 6894534762210941 563823368426564336 748516321038070462 174768832690876069 661614423273598977 707637537471566783 492440232278372210 208031625346226927 62926752391081713 148743317620101138 313574365079386091 997695733407199647 809469101500669097 300987674975253433 107647518749160101 843433062291626183 183072251823126335 144115188075855872 117668585895876870 150791951601368575 184177537259380959 996184722316432250 255888439008124908 71133076824888111 103878232853988440 614075304662726396 376273563111944730 635595406033527862 477801834799929330 66808379336071561 942693908233265784 860468328140358097 966540369824594707 330852174828422152 390828215994549689 176587951800214168 847238798523158058 985357063805072918 506662130106016488 997467941927763705 444203651967219667 852854845833563434 845275304844660170 573448579378055806 911565484778776232 143168626773877820 221690329390031162 512457072335069832 512730929109201319 420976238886244739 793638564139543837 791388782302326944 251631559606227146 329782226199107267 450722176825412469 82845562808998579 59885987196924976 911569088818718905 482261679359931375 43413308696476035 20193838662705668 56412623799906462 890092946315221213 374782817969435835 540151502911238153 877679688093332888 346484186481757390 207055896062729484 609804137858625334 346228298249828263 392407675489407294 537550995879145196 41321119465819854 498309707207550145 812039688787875678 477043511832614008 156680127558807213 458814131917239736 883949603970724966 587641478305760794 138413226218218011 421598478562807812 174557940709489485 372818325314463602 330216079290035935 674535542626070611 816952725335687712 698363438061694379 594414656852748168 12266131030192684 786213424557860433 427383000511029264 243979731749336393 687800900426064729 971015600760094149 200753573497788910 720735303738288731 489919798701176101 370442807297133445 45764986738359901 781371060439080001 854361843029143927 885632593254269084 623433248622854759 888931974204765125 91505300697760295 544539784666397068 966482720665331686 915291770350689596 983751798232900033 236486112774272316 477661658477855329 956134240595459345 536946776489542229 671613473626443309 765517467516428939 653933600319477221 498019354383629173 364143151357183812 557518929507125146 528940549786395770 420070041705162473 681016780634053450 791182339053403775 162652724623281376 818505606068327982 483515512005520700 70368744177664 852122086728993199 679807984691168289 467829008839843746 899222507084388458 249500647782227177 291265023284253120 573910561303092759 562296402234113372 479583890014009715 788395642805553281 674957524268329426 181405084657316187 595046113705881984 872495979403832316 223121655541480098 454650574803780559 406228273588567640 403120153799727288 930123817936331952 844930580116232174 816684500044828218 764773151984450073 380709558234020191 525289476915904724 558628986992223693 734105922389143228 61081139779409383 986439442271300431 267845631982008942 559419003766029143 917095026608667081 330427839247964304 855115123385954069 49807839763433587 556613010048493474 312377249191993377 492895755855209549 940227827240575956 65570212558478741 297773267437469798 472526075544111468 528148336186925105 276000152151509854 496385966269608819 645282274598182814 949639977233893350 149387150207255684 836482230465776837 19210240685897356 936246577197633497 477296823757561891 602508976458308241 466398897873351281 755585058203289819 931327921594268508 39042220344497977 263225924972380995 399114678138080624 345279422815777187 75457784059961595 743550806444122421 395041329327452410 58901998521400864 478298889009942974 263220833656848533 641831732134917981 404151515109684569 624756037012979277 605548582318474672 42602300797862306 24447031929698915 418808297080520928 261475388877614038 394450492343374497 837411230564676207 661105388740039671 885718965540320905 332729869591846187 933585570297199519 353010502731694007 22278095323032073 941238645905288706 643647845143751675 99762099604115423 120655228102577505 200934878039411710 471908067728099988 74046525181269055 121158207927850707 893017615201431546 592981417845716477 97987230299658286 493787589414876563 186124956711039281 36028797018963968 552256233477207033 918804402393553404 254136714684069626 745321233476291578 162574307568193456 88896454866410021 894045550480883082 4398046511104 191814332090293422 98955386951676381 366563307879832897 981999162117199708 437035116007407327 720187940166913421 803685220525188343 501057859191661286 700305443719404521 252536600362422509 276943553289431363 655299318927774903 999005899619782441 944742521430845137 60944859172913232 154137001350693122 11042635121795029 271626754997818742 565479600872394545 671352627135599487 417706426197476218 87543503057937316 271219800823042920 182927464335313466 180676697828323750 445466905253985812 764032480997327030 157165924910339655 946569553596207579 661010034239284722 241424708895691957 150864600489941749 147702697153985225 559930074521294449 537373419670139602 24746873876951327 839730206522898070 507823514786539479 110646265558892884 851807363096321659 122436649738219699 776887914188299819 340233803711383655 80252335716947341 242414998117448189 6496201481229633 653375675638556972 98088152937468313 721278659250863938 850505973789596519 420542868993742785 862715244870045398 572031232533411459 810331486724712672 993206551315880261 814317400830229106 593619199587449237 824079217096796831 802022438632337625 9007199254740992 73803127537356860 926723071508284161 845137356566641716 288230376151711744 141951698329410322 670917914304474919 939290229904300190 842290022355239895 700683654003966059 862669464356299489 607933419172216919 86931722860235909 333931670685827858 110616259933362705 268800548431767446 639183313021706195 769662443470235452 993347083904020969 641797797418454235 877095958310135559 61810033078645564 270407317155597594 29209485140484074 916687774797891974 531800233297743692 17632382649816653 46586321919377191 688651024482690303 705992044807512256 469400903573512329 938910050412989573 934378126815615795 148486223851692414 81647138851182352 596146526992579873 528235354032400414 279398721587094365 376405373809315104 874390795237414541 721534626557562559 14096203031161581 587064622261340257 142911167778663555 686253145712469240 937128087959890619 641022971831869228 755859673152584679 332113172287975511 682347893196902298 761169311995281913 387282006561215511 585506957968997847 378981154305559985 173369367524069006 544067924231457837 219665664766310322 8796093022208 195928520543299815 538006647173695175 976542029547069526 802582110313806712 234655675352687235 963666029729046502 323529853334221175 474342611296210668 775777617962439666 60864685941152438 176745764462947550 130120206497266300 772067722271489384 637385578939928049 135324719424285296 703512266158466534 964915527203940404 118262417691773052 192825644978759261 397083239882913157 709573548196184628 248903479990438147 488394874094996316 468920995866407510 120591808000449645 213892653441763232 902251401576274121 681046697118613724 647361573551722767 820725896504631694 38661464678620778 410974603119128313 68969082696475195 245691346318218327 90006503981448804 215423363179317967 828899904569679755 314849706598221596 191297648160254830 593730244247168077 315697747750982973 299844305330971293 779555496645796455 471987723614789848 384239243792707060 129845601319472509 141156038869879734 993341620184229381 86074438747292805 441454710289903389 364895576517464351 883702645875083242 534567753315567936 906304469517923311 180414916658936280 397070116128767947 151102813782430915 4503599627370496 18014398509481984 300136188905832761 633019274935021029 220190168909693639 507770303470924491 375422514818343418 588130913107712689 132254063899066308 760140245843229217 856414965494308951 54990059320618055 359547264694158991 416731420618016521 134613002612803547 460930313320572663 611693249420261972 707482090864603722 903971155451574659 511618276732389229 220177784625752311 555956615350710011 556836075808923680 271166889294826011 184515872034859504 888043251936582475 528177791861746401 616882908209461083 227747532171018198 702797126854602951 729303248833526729 423675993981493056 413241892700132842 446541725812427644 708682271074211763 921266445963290126 56847517788195289 652835455306375493 966049209399686929 154467185586426031 385280855391917702 918088740611068239 572437427715800850 592826478601596572 818483017433001582 314426572477925161 519909384686046287 931369748439759786 962732659618530603 770101110732342242 519454600482942588 417774841044919386 396494445479460200 445080225689155590 332049081436943064 356256128357646927 370724965882457204 559017773226329357 54925240321107306 828325531961408133 56768225517552175 59818412769540009 696851650067769791 782388886675457349 978943324941478524 481589258233973144 112883303014002697 77783333031176681 781067985942148151 451931191777393455 707845402974509585 44725679854445039 548917562235702046 636639222712215752 10505689130999067 96276324834155591 428673648017422169 686931900586854451 147971060680191786 388400305610138697 794740703055645710 708629077492686127 408389741356785289 125832586203114268 613282602092480336 224952084619517697 490187423984165528 158152682303490949 666310197279001258 115191582388744574 743238649649826774 793989691427594146 217014533283294983 344117871874242783 835997718040686361 826042447358139549 332052735585777953 876084202810160717 819419022318189116 504375585571476637 970728031627167578 889987926765809576 88430229472725547 330091686763352597 96674255505878490 108839775086767316 214551059813181373 631663396432753656 714096460839365626 765906319518301167 155495234846079714 341944930439141582 667055490642375840 523370259340796980 39798297207434013 571806738531344350 825921512025057877 181424451857623697 138015132815499948 513756521317568547 544534113906575877 793691452332181706 657061759767045655 140737488355328 778347643778513855 137765083542606315 659274880126242099 177817446874650223 158723577895699536 869219727844340028 449583923261738196 228661668169161189 687428247833074777 396790947332175562 716582614922472630 451197647868154488 360074622606134460 707618062473898043 129226956879804458 319955089753419447 463223895028497579 415375733480362639 851256542281174083 876853750954201488 831055850282644425 424927836140100925 972531794970145397 12170049231840219 388798714523383488 319012748664030692 174806911668473905 22655838651670210 310594481716031699 677723493305748768 92295083791753066 292299651995479082 776944568056918262 345667326781128693 275015448584579255 571627429055955796 383089278636185029 37699827137582134 342613644416648708 931911237010427210 683799723683867398 751561936379140827 184443041805170867 443313911318039766 384534452888167093 380690942848284928 56928215024220027 265084845475928722 576460752303423488 106108360571146128 460603048340378596 999431045107853227 102822968915753951 944666803410781903 769338218287364021 19441818420584193 146630865566601581 60279521776008778 932414905363631598 801050336405146684 854749109209066709 756837914259142995 40432158442905827 902700425772265976 697723620294106104 896826394660982702 314355242487090600 17592186044416 735306134362558349 369957881985314153 138386106345381538 395684863732754497 403661384628300073 166699200400517807 19334230192210286 463747286730022284 458761682369154963 262863579873919407 668901030592857197 72057594037927936 348809245591361785 957334869001396677 472878486679149819 677095040790022913 477902311174231624 685710590255513362 207354190043784364 609751781181306165 716615095009257588 862003907446217130 41699996758483201 414803019590620182 834104918029753512 479996697525364652 686835794912576822 434100471550896884 152238618772637469 782467395680775321 339200998705931213 246584921678362792 75338891715965936 127776922877401541 531854153743991354 615002306375261157 292636031853018244 54973401842272167 357733945073685587 10032214684667248 297686994659319933 610501994199469880 160269092223311579 388064612599751134 236492924926372716 185771931472555030 574424131445221446 812179754282830533 366059827787061284 903955033468968519 84609061021824159 85181343838168715 414403113173941964 643802423130105046 496468338035201410 287612816747781374 91051341203822561 727744054391502485 875339405712076431 315512712983930251 208512332427815747 464357939374449625 475088830189032630 144876141085120236 10388813866401086 590466070787506529 795303218133366867 763455122978944594 480993711709353486 8594305984837251 982622226251495957 944621373389926732 771242647014655929 540288394879853910 33144838425104248 966438092432568632 549580427179268754 16464556642688089 317841492355337910 782188621256387535 307632258343932446 615014672764697378 711007193695756917 548638857230648831 189532744784492295 395316861486433231 880753472949232154 451881477860945753 380814752000191083 386796701954326182 63824453277785176 772540895471715122 467541334511604891 750542626285540331 638310017058257240 343911933334101530 803018917980543495 1099511627776 552353038330728462 137362493767439748 231224731106852888 808642982971184956 157858167352643435 122978902673252723 77623396011779867 615933213141451184 251178532564728284 646871371597709488 391825682267991406 895148351010076667 581561710899241398 364314867874580327 800037394952967754 631269239812365911 951722897783179733 198893687947222268 232548223443312163 153294183403300221 626797544447739383 370794330189049602 248305226262684362 844821270330510649 834492135472400613 73609012539640152 221085530008754480 255493546190728337 854240503391409230 634951790434697518 500472585762106127 995740268927256542 537976631305655613 183774080680542525 244410911477230644 180405906178952290 911402576165868397 371882659170248698 502569976915775449 303764498438189623 987634492720489835 330810999526046561 329235344883181415 243848264922515540 783272509103730102 732721943339390523 567806113100223458 387873094698436197 303319813831277132 400892438895891139 42248139108954241 673409187934608130 837909729096843189 673596117642176323 407776467210962484 132586765381289797 35184372088832 957319557210853067 6677179361491963 32977639781426924 417841741487009183 739969797121220114 686372900291540439 528131011217948172 922101739626867302 59195672359613263 374444859189586886 88770791629094921 485203500624457972 168649089993870330 205164196484087180 143363379293961204 734635733560707069 219373127715765347 487500234889139571 231631773037248562 349235517417374092 632021101734384756 328607985403412585 211139075365738543 905667791779709146 409492824564042234 580190011092830053 657673497555810048 948232569138447604 106812340365010639 469573044173538425 425062107424228858 156281972667836325 484979675723344828 765003728147750516 537806045456739493 184341614102744390 163109865314777121 210643708303348044 713703930715648600 270281618896216125 814272431739339829 218330432902867565 953633669027010744 569558101409245982 689517235489120233 609749502556142688 590287759968226836 678824127569463391 771499848951631675 796765599833863144 597906212398858575 180750464325033716 596663994778090907 751917127267474984 903764533680438661 464588397620818997 882366672955710747 329826818942646910 3460996347571118 301391873151767849 170258095487676913 202433843624959060 173695634902401890 507754232639620645 895313433092986429 100992434730853056 182791899063467422 685576449626629909 960110644181875279 634590297575751063 964251076151819681 672504796555853516 628475655983504278 950483299563266208 320922884629606271 464375073445544816 760916663878954176 554764779180498675 252959349853035692 133355038371824219 121327944317700985 726442729310041625 611479461637776706 937018322127666403 779809937942565347 95079042201225536 186469113192607452 407714845612931860 361534944758372314 505962024547876783 871705203577791162 815262468850654766 970621339359533439 85409472915977608 522483415732908209 900083763440221431 167980282989306538 484638853898323193 944234009848717563 704853339934163577 76424409579712491 426901267134208757 908959440329953001 801360242628157208 74291325903620265 949675539871773744 695334128790807502 770791494895628953 980570547311005041