1000 262143
903180121091114613 611535431953358118 77828605464411109 545275249615134953 879799372887574656 943485323788464599 41145221342160255 479155126399505901 941817097355487853 994819713169974749 635188060231579632 47543724391243265 726757362638807649 195149229667171977 159459835271221512 9183520577389902 656007469290967040 160648075261555034 89892934706351166 244898582409024796 273462833672025715 16574138517802279 286129817250726778 785729736129708086 4731362234779443 381112614455227400 43115605958126741 282062693930904134 59738982572358889 180580862233932316 724283428367817114 741653333498083666 4503599627370496 358481047964756426 158553406939779493 126946263613396598 328316879480749446 250834304939118816 65796400202734788 248695822144845004 314455698408468986 691267812346072731 500371577176176824 575447368675087475 709976170071110791 357771959814993121 449944453875865497 676212135736256886 178324181015947922 285316235385248522 840327229431977528 838983235578326573 863730326136572756 550795489822025104 879655300326262474 425340280031328367 402553337324866896 654441531893138016 659473001401255682 209177581089753974 883284402339220955 66401953295911003 334740650588525646 300232668848175237 530187442067658090 89602766646513550 854738727245147697 527431119302793068 980259730492283464 331802509858060781 758702353838034851 736498031435204546 744289275244137004 495780039344662429 523111787914502085 378628767337324834 517704617637767556 296435652100993900 493557037830568945 968309458856541088 636292134629762727 237483699660549998 151694039847757330 585037158906344849 660892225071967195 506179149781056938 62447328004314619 678933944266923214 338129558887738294 484050275664494752 242448137174165954 938614269093390669 445812710390669568 56423710121995071 886204633238240198 371646059001001131 95547026238883880 843231455308435863 338276616123489100 893302363640344179 544793879036954354 463607660293398903 281474976710656 944406086747553353 156890627780400868 105412565192940905 858007067252194275 698332138780786812 644355514463482008 135229819435093244 688002746245918942 484337204494738255 510695038688180165 218009169972805252 944149974454123285 678471668081615926 942286750167619251 187536816859216999 706858039669251757 285346413340959897 181237917312897381 871397429725081253 351999441670538491 578186198084452555 348789060629109605 885615498472497110 961504779754259195 904695072678250290 71622077153071871 538676788471037668 394838953031222090 712813376680760820 126043039704803105 837113823660710236 217886984880121523 615658658946400877 8233941944788160 729008938811793422 536017985706562977 871424473824120761 897383546832521261 16907279607900195 17592186044416 992809684302304486 94243740467107814 113993542761290524 933500614813188215 792215967940658121 823084617124017634 15901010473642061 451258109975243160 199774720465853646 288230376151711744 523152629536414315 858993537212081155 228781417405547181 578902266476788218 488703133424695260 393580807095396041 350681179873073255 213521862129913754 275335937523813585 888511390029572211 939923915204429713 427904479901008872 840906003479711994 800987228459898116 759633259434613443 414083354193812507 115371944676560254 468174474961377405 563851757589449032 813122944609048763 292553385532093595 968425898042754551 808517105421153515 69077247133205794 640031397196345385 178180748824739097 784229663565781408 610585570318402847 512429286289641103 175490768508132111 830001254675084953 63404755773437733 652630526369216369 713165276324389564 181825537657736717 395484145714129349 285305504440823647 153777315316137884 253507126181221643 852870947322878088 202159860003300848 391122389634921001 21088575016403077 678337042398967228 269948437126009491 597309521333718128 247444113080369499 589464828335015086 94043427493438548 603444581595387897 272910538367432940 369328019659354527 479349708261928911 92439832179989305 277720516457912803 994073135590716306 598136600247179651 765938867680894890 930230659401837190 357487992736542830 676700500751338914 715057379676466817 758135818750744036 288543029738941986 691838654965449985 335049756768537043 674968282310344351 594168857534695042 822541441740240671 688383575681027870 545485730885743566 36028797018963968 255422993762264434 161262207057917015 94790483847210562 767384617618536599 391187633529560818 420757494238101802 89144568491631632 808044817118295357 268240520541899768 678279804969450508 782368564588894117 760533657776699840 453931712009847760 598743351908074177 296977494709759848 521164162611093718 460501995103905920 691657146420800073 260362624129709208 707042991140507957 321853946582710281 288731448132866914 945457380083836708 316524739989728335 947896023337934525 59094809244202375 164690379892384707 989802085865146744 198855726838959336 787665297619660924 743327608633259545 115666353377266967 141153866804241256 305345076450124059 932769901809969177 622348173795606072 876316139128242523 999664316010691492 751141875615946860 320748954868872250 593806131438664583 989044936497597204 872678644272165807 301941781125755952 390973423672748712 321517074876014335 240758603571947075 57180693373256296 851870623411021853 223176680407947453 693700399476846469 541487431549657727 783736985273230562 654969913797982257 935401528850207111 484037112703674910 610364607892884449 339955692573000058 796114349629718212 622096102087177430 655811969976354358 846590611369057626 335966915528229584 900073544350281788 195247873778964933 1152921504606846976 590281850336064660 816777680635696081 541808200866455226 491059683733180615 625092782320556606 946336392764947653 789519701198678291 506707153432959682 465431370954043777 448783763861244089 944146941633273307 315293864673889123 103074286071505665 369128614395910298 958086684939657668 608676731938326124 497684279103956794 884351572008285892 598936362600158570 771236440348491977 894499630389652415 968909984806000632 825512483492614630 817488477364230452 18014398509481984 945784608827260728 254354820542163916 391647569019342317 699346337479316518 1125899906842624 950249836019731056 571324754791257953 626697426375031764 461093524679933572 732342938246163856 332835473674274296 927629750354673330 12022288302985197 280376254870010266 423048485794549566 181789087951049345 555291228046250398 641312707822781678 936434161153767771 44514765905558918 473075595982250278 105545958610247596 576782299123840806 187692681373766226 802518701075456829 834732762147060195 924587445138668079 695890226367660574 715185881346456220 591517082986458303 262220280010574428 127020301041007956 237237613163218408 428207718166539935 965756566345318989 793969523141411593 593220183069721744 974315543684321127 918767825323090770 850625791911210057 335245272978673763 53715917523182705 530819155800155548 2529212067509961 796420509634638578 902551027721278743 212496878733325303 667067138900798806 950274723789436583 331010407054323675 69592536898047573 560030130531666329 109801320185462382 711463628312197585 913810022781869423 155179840005114084 70368744177664 937973360660909771 964450683007143848 990763656429265453 961021240321360652 23193846102832235 174086963144162040 542517390555782245 6960285258250619 417419860498947044 781714671908333422 199389807193018577 770045917178222197 701160226524191860 346957419534545510 116081556801535520 531062315342976746 645531956584313755 990732854173289255 538771732312185180 683212036476104469 151827340512691096 304575676409729476 270473031210224344 639856063677900670 490576099479465148 660027350093275025 373676606633867545 892394983578379313 758145581377287173 531742302668212587 466096227553848592 442238454633960640 272067489132140354 524755467320707159 665417061143453905 991594719816605918 621552611543390159 879075504809637132 867759433228878692 287376043283380657 201563534829266592 167137252013157531 484549274604967386 856213616160711466 935929697401422074 962396968251275817 493637284365671370 896978079946943141 880028429652605563 889761375387234945 619605474871711357 27235139061270718 608800832131233700 931755077036010224 172549512259237767 328632833684082005 770453750834012859 159091037044353702 610819052984357228 71456528702796571 389878943217388316 118692361766047335 752015962424331803 395841601723838109 587356901140321314 863873302439088990 642647898828814843 484258339552920355 650666414406118807 575698725991528065 947784005300253371 665316429286439630 679883888343626148 733290834585938122 871840268241251956 302580572001366313 997331593221855248 78066694258397005 866438320366283368 666767891646624931 675875106207323388 125192796806917534 945152105215952523 73946740439467193 240363296253024440 601632239294704431 875901651984329416 620587508059653559 357896388576417247 163554858873323985 296651478097766357 261301466544099649 972820758239571284 63838063450525972 198132972154725737 942589446140340877 600579397466427644 127274812500659078 643668863719906208 227836373236519854 561134899086734323 300062333571346563 240890212672601793 341557331303634017 683142184291618297 706423054190719638 477888945970019743 326025505795915249 635730673743247370 816477170275725191 677127118067635989 314882408586726382 151515007750347747 144115188075855872 996796069308552011 912575430568788394 169793031648504127 221311149465394960 447542759853913057 847675159459531806 60587967928397593 54467769107845793 92517673535094669 963034631403187072 482121740433652921 423111072028652958 966876852924705238 183622802486804903 773145946875592224 196283365196822528 109917866512222700 418627719165714598 340290441529203825 175492866417190417 658415210595072789 253502032125444573 247975711807333076 566936707630220613 858724716065122065 509606512517543037 717923766662778551 946126779444624201 899228027849082959 855705787351149295 996680704115586090 651553593790609812 624636269390577229 822601473888321857 622093304128111944 544449911570324846 393325150862182392 131462098466542163 386251214572080147 792480940753364850 859631800314928852 323597413784384198 796854976107559311 496544528842437356 273414658435847657 2188518596317960 786109399455275709 54194409643710287 517236584641211666 347976209971546664 637845191747569222 990865934611735294 819656224134681269 511030067386384217 101502171383724327 897318774248909859 938963029770365023 565148689421047929 26568358511346983 120306636932957328 301992223210519648 391891212299454981 664031070778568010 786504684311058805 231878273078886068 295173572772127355 804167058887815119 2199023255552 692773936337631728 477336090527786945 394161944380542296 946504544727969709 244717909792688890 445959581237350380 395159823697603864 138276450873743657 467597443530288905 52312127541604695 674791900474486728 464957619492134048 35184372088832 273881833284844452 95802622085055599 669749017263390167 818005162302921990 620355398888093263 636641719066092420 4764515295458583 671987057506617283 113011600893152319 575390256505413446 890891582534223254 535163940827018217 931580086931777614 54966613455236094 202292331764336076 676203763517741249 227454111142411673 692202314154514695 485366119364016002 52034925192987538 690901872481918797 988060167101345370 932405794025272267 432905083966987601 729973705029497386 755257087782521574 586906261034340720 33671855620217803 472133499466706545 675824882680051977 743249693237657508 610462946637222195 360058525880448708 251425333324827204 492798852952100589 814260187905409883 867505919788579825 201346081651619032 411893842438784854 2251799813685248 102376950467840701 947488662629176962 580908669717417631 71688698654918272 103474550764795376 62367732264603168 927626471543970958 941208723089024123 758321145335385556 159076767475050673 968760973655023973 956126306486981841 912530064773345208 680805397170617361 330114023249415894 504479108360889534 453472328097607151 825865519318554033 350236835706015286 943487264375844630 574041510023395711 795253116827942111 235673014916796194 732901148767513292 40446753622919208 58793785719130115 447156140023977817 58365872614232113 259151119917147931 4598845580116844 446711502024385736 229865664941275415 848300251882119797 492224879714350470 466406724350300830 84254592585679859 426078886231066807 973060646813512416 623933235767175779 72057594037927936 475511593853842910 671532803996188805 192856966862348692 333373232129009003 513990261330736489 155991959308626159 811108953509451605 700583313738838762 813375293426995342 762600697808475814 774367151178553938 349711167395878139 454435463262431036 229211826083778070 132333994684904284 492808978614535788 474640400490254982 197340412044052326 245973895755942222 634466062316797349 470347336430664982 37510306831367416 255496415141552137 907248012261679453 575450677390598471 159279432721712846 922855953075750164 503185087320571999 570677978655187528 874965959511079046 318273201557113741 724089228567917281 692840425415728083 877350866722381314 108590298798735722 956595950387418968 576460752303423488 899312399653096067 919242427946062026 827201877355143189 482545639916286877 699848507969657825 719618572926822839 748246307410472733 414413841176707484 371739098959858088 7972372778071340 860010597824147800 346472527302182095 412446117875117848 39039159095277545 199992052852569758 562949953421312 545900623080111737 992584936715052864 542131986294150229 642302368751078979 309639409844912997 140737488355328 400967667178730959 561812656085454367 164084950756513404 977677581403892015 493398171193489266 305226243637245343 294432873679495698 148896804389767676 399719987312509806 432123836192848612 496142495572760354 885766805559632473 527949317822916698 991577147731547122 994833269315029514 768939299773399079 620111342674395534 867815031277462746 816561099210409702 701643207015124245 162611446947724653 281064566885206408 90672734333019497 33709254495878074 535269209634000629 286689711785304272 212986424131319965 769328119536613685 297897305941331870 108808467360722549 268420195607988740 80965600601027499 941987628124483815 56366749239799771 363661720173628549 907200732447039388 757877940311609914 500800129276964820 961573754926250740 80996336466325675 203695213817295704 8448076235634431 538284048280719343 498529398173912607 959373085660026159 395816080953464646 360266633868983599 113301177940961726 399530428897000831 862349374992763342 339739343551931307 257250126033217870 800416464476109039 769573590655985900 773485819249031585 701534761515243737 443382364772811518 166666720712329996 744167711337090028 461981276743589701 226881938618376189 848492915923324299 851246857874218770 8839478569457502 188740756568427162 13670614238009301 623740679995735676 556070862660518952 752368142619514298 425931785909100359 647775593513383983 409877114817926405 230269298570862993 564857414592195683 193629784819727265 7002568506759689 522917909176130841 394494377181838407 990076011025510605 615292098146495157 975148333376341810 358183790510164742 428148304180344001 284225460341191559 978907272336717044 928873403726152636 698177409122406263 997946313667530377 753809605993840979 223384727301709794 844165438090998304 182208635012963083 85274259622820438 37473094876078224 821120170704687793 257153074903549637 185795153766431471 665178808592045237 998286653270436036 819566778606412015 707330612177201115 826752351182172741 647899822424830748 427456410300924277 95226984883508239 688344704639753561 723299907096791840 755825750300635267 211476798803842660 624626897344258086 137123740623147797 784339502372337190 51744622806203022 430608423114224127 250087460417095075 704279659150720181 236498482620734642 117866611884738089 587373856335577523 999088944358651613 97388836765609362 484013238366783978 839508861702933604 534790380006808936 667005335966961623 442584433105628335 375904269501653885 79109260876039599 988930270249879273 597942194301388622 61798878936952166 189032825742936614 217758121042675154 285143847534727309 692424926663877985 980058913434932764 488207717550434451 445216419411134731 142022111874710782 361378369659276679 106885708462940690 486152444953867017 273804656004110333 891878971216099197 1099511627776 150857616804983152 9007199254740992 341393777598829437 631955922058879142 579609403627929580 755893985568494649 194094925672348077 152132917215628719 330725055116757462 777165275131639169 752059134396886583 480088026301398795 698346701302451920 595480864178159456 30739650972458286 104252812846872045 748695055748124853 395915819613600297 332833546569773138 953072167207688691 88539631948165470 487009094412545527 640639993797508305 347956398633203154 277223329621770915 527427071552880568 201547420306496540 979405538031195704 478424793147584608 563550413165731102 724567159729470085 956386057417468847 613293502275600375 9862211078860956 562316215171809373 85927634222565746 427270644557157242 665618789243715403 994506721468717194 182313794104260682 594445385040086524 955697821525063103 305130757409620418 609241608274741726 865691756507404814 445688174763032420 957423678600090262 452420131807535833 615922975607727391 123036175617098906 856188263980810331 59604574875844138 397843543761589590 8796093022208 508796287545963863 139977450282276325 570301953271061688 411604175964296463 648771935848489956 297118310648993228 505767528801590192 421353527257647855 115502180782806895 728740023774772588 369440131559615470 132311330808491334 982793100476338955 803758611772430279 911914024728520650 218202224497466068 276461105711956666 855994745368595095 466219302084518747 565085623647863542 360582765579348605 129822049177462299 850542038550021051 521605720290807817 4398046511104 510978589005390409 527349301904926137 496937123506274682 317054203048607868 303378272984051498 678875959820461959 561257020617722072 222585299238301116 832981080564256747 293942566394691204 753686969767103680 278366069171019393 852487769261959851 226187258045698712 993052001961814262 785042416321115924 679234016884534328 532242659980357359 934418576142249390 469779546445175782 891653453041893795 464360495598366474 782960203943929152 77257405826010835 398436595918007289 753000068489239415 309998863261192302 525748419921262206 404721658757653623 673776766649675637 580744647665951357 367202530897168290 422953963860693757 567190583357924511 487282698925226586 393075598772171819 153331449651557438 741942550305705329 919675336560008126 660330112924862683 827504087713128767 577451607945430174 698148232443284290 865834085819305835 335329348061061727 646896420168979484 279088916583380239 620999663457833541 759951098486937756 859860672303908642 515947345857194743 836290031269326160 836983847468363935 626767759108634232 118007969189856796 892009377097147433 503581077880197607 454763191581504820 909286314088591561 384083500852667518 144264386178043878 916386859000310569 640099678663777860 853079306449083062 693783717379918269 496471841860497871 865556015383946639 301105230867623560 905437948024240151