1000 262143
187372299518279260 43602130474742763 44819282172062712 812635660484197841 226375635306150259 559039644582067944 779127849085348606 117222698568555847 622976529403712494 522573396036996536 272507386723622601 241028528469806392 164166249682340806 833596779272797921 589117856332929992 877411298455147824 465109725682992987 333942929035641769 988554094229931388 755985013930349644 476589354846010135 507183170528354696 264045113408349298 482641130987473132 341084992503327006 902415254666297014 56038791606562663 257357255829170556 593159919960042262 461358236184337796 887919113833379626 387838292474405529 970529183164127757 20069826020222543 672554344263881208 719685944402692665 909975881957979835 193472652429676842 550264221048841614 380911450585214706 481151204946199760 992397651044560347 307315785025174640 799409753916287471 587452006074985556 258564567692885884 884946060561342977 844860430329027155 318811516559125117 31812460880521082 921139919238403213 480015868187127428 570748422327529305 341932951499200691 697499074785608314 248775722177160471 896558538517313367 714938284496746712 141415449260777765 198691798006013774 393347196224692781 101256727389459233 22320515293528509 286361356485913165 245176865781956364 697659489637887612 881137519518320772 503635382024185320 940554760376610362 326568909198853789 302163122271726306 556633505384903185 395723272079599713 964585536200267115 217212678210396389 272048205731752950 883857511472203444 56132582492904933 190806766906674693 506769450457028791 733110171269017178 163025862809478791 515943326472291447 935499955895590945 212285965011052886 574043299232568703 834072316931911366 563933753072531346 857073543379055450 18406198538157076 120452691456280740 106327854963535623 933260804373492119 416624684389122434 248547357308637457 426018051460777571 607292506406485867 39367763752461429 461699300063731421 406553622096439205 184692901039067610 282259013677021043 555187181561256902 286723626227353753 651399671524050916 51750095177683387 214655733547828071 214267577174343902 917018043180373385 571372018615672542 617700023431290490 333466494631738776 225566250745757555 700493757178441731 658135142527332205 125367488785247383 687002482904235902 843288239394304803 445747195592302186 600945942161553874 596940776898490526 990809106331579309 216520901970598162 354292262645977856 684172148833726174 982250665894672592 664656105004997178 338895884947857346 389073348927644699 421113468249112165 352447493682945674 997897159430876659 474292399050583267 945922121348463657 135048231795223564 374198515676610799 224 21732990503798096 818200357611821639 316653708211611260 58594765381890384 458752 410422016283371885 345320731321909685 193518460872493004 474858471540638757 553965102985981953 225148215204468854 267429315125971819 823713200069784278 801051501789983814 486057512832160037 700364284594904776 338570906576204255 570125748393615227 763623063895483532 418162895776731925 896 996944783095070163 623379849630393772 757863974393740496 307222078984648076 11082610222845627 315188155221444796 729876350949353263 561074720687636805 790892782593708762 314851623270806243 911494475000743764 66512689004724149 697448213645133410 787618134169984851 651415678200958187 19853193297503195 407058891692972077 53912061575522694 344980933199649079 103731618318481356 114690018416166142 7 705843453358472785 920174381763271757 992205172606690895 791695605827571997 704720456454747123 563540630032003605 666803435759786673 61491994701405299 442305811861726848 635914913574059436 28 695288418658220688 943090010539123299 825569287163816747 790623635829638945 958810575972690931 160304064928863561 185278717094919996 442959276410288486 479591435944374162 554068751330500649 506383796383670528 384306934185312491 824411429945512794 821626658554591802 256951716541082115 172664119018912593 378436826754746068 344453127285104632 457331787138230712 563902822343628419 272090219019735461 736192224166059077 144268086790779098 5871875914081416 413643980745741224 574622417009185759 759669133328043413 917353419757278821 746626600179845143 209159085656512866 694280925235941191 695316576540384122 134219084228674226 402677549396133922 777437358644104086 757834449249736798 237485129448118838 740905673578824460 568872360290531052 346747316625862145 797394187860397408 931593582564081430 910356916320126093 107837450962680364 621747855600864908 999652491586013844 951341161224587840 349001261032825383 266620814495734618 629217956125859786 495617889188018719 955062442652968841 218095604479882284 284222147256133277 992921561771388070 904602021751433443 72130273314792231 488050623598633167 49028531388945949 455758628231592504 293223964769377377 261760206094659095 988750958348384994 342902931513079150 275923173363922187 608979868037776479 320327584464515974 653810935535192854 887209818680452214 562027298739206272 196900059003727529 141063640060321991 529235814651225237 686651359012821035 398978576494214229 125995283035405959 623604314878145057 30609185545259966 448892885670587786 898435805530551915 732827172785543660 111479413319287743 175694179632366590 38321777995203888 845879708535671754 127161457489489263 910405664960835570 846003566094494232 469759798682465731 735979517154512690 597043636487412618 548856585501242542 15598041776013573 773775406039605772 992319025816073336 879341909616915126 84193091107075727 785027841895920204 713351906743322273 914498099457572397 900108540702548677 79772070580099434 993331108854176525 949797844692531007 139515624919776457 880782735838738703 337986341104716691 159488692731064509 49217922952187551 196572199298682149 67828233345969406 603906984814266382 112132990791774204 100379340254181196 686992921289848055 772632377599759667 784844755202756583 768152566066896636 639773521409612282 765285507561297880 924337200834929231 416136787803002287 301698819045326293 155662681414587201 567902291274022656 229920535656644978 311409223689734927 94885695727733288 681115085450620138 94726495042728867 402462717995434190 683294279498112431 109380199532027773 793934577063619578 194970553833216154 213303039041675624 579547249248374063 470123595820366529 632568334790197752 774366438147614669 307157140153629004 438555184971622284 520973638643268997 257010999818514960 701343926795048848 323102380221962099 635310287384716998 691261920037040078 795165226962072077 477461800164788100 3432701527786255 216392276011772888 581954072479727202 208612999591085197 739490828416467766 265813373874946484 782822871101969871 113882411726639887 310719766681183181 396606068805490168 577825911272200568 789111614180414146 292636173697069274 80654140802987698 952467720698573552 483247309858403786 57244885034384661 525656784111834266 30727716684107060 773719507100884715 140244016778318143 349893080671457638 136680443705984168 390873420326633325 644974773627636553 452144513879412454 983572331299708716 529845033041006732 879078436307586673 857373456139851883 280180293160967394 732776610852051231 977453754406441744 416748119877954182 9444604864096767 687571417427262559 618750485541640827 474151043282227219 413524758483333482 566288092805422444 22629955545019778 982383915929901365 496773398735451198 752515797460537645 455686367280978951 965168104577735169 899537893784606037 91403760799226960 456282580020018787 28544057239070877 778558532667862847 204145062445104917 718641587584048530 301707244156915789 27262241957328297 855476215182237759 396380612681881537 989380566642448320 205724974625604920 547413901982812691 101599142271369086 186041597748694492 483620740159126919 398223361726122998 254188528360321328 64830918687841583 485042378353542716 39893756073887958 455374816540293630 445623795965886303 273898179557265230 832679807237306715 404063449032164635 319446726189870832 974312421865805911 825892320345228046 798187425588781039 479147686178627042 570477659596684828 234003300560366626 775262580476095392 31161903490155109 96516105830757067 718525855183166468 409952731969916241 65281424503023360 470100810747311256 292288998864069714 301464917883476743 335558738862146713 336318881315158131 519990713567292052 502499914163965562 180333368359094390 745854482813329548 408500608901748749 339911669195397080 972043247651762784 305992098589195065 923888672984880635 992407845427177354 456441358926825000 791877645776776185 319864222224739351 695116750867130494 940046451417948433 537000495987188569 265632344718537683 956883759624451644 165388456318163816 560992950549557693 61379124986309801 737030417162023281 103118413216719875 554043245182691845 56 552162864261737710 113330508620524704 370644382488866573 880971906551483977 379976940029053380 952400065389209565 1792 413486741700666410 622241140099628323 57851452400593162 797875752709305455 909348006495410618 827474759988999483 449926219567798753 7340032 313676500077990147 112 368601716615542671 308832417071143657 682781122520594857 636375243256505715 404232110296012769 136852063871385595 965169922767299698 224755750293946728 944984443160253331 148115195576145515 424113342205067562 520679215685063995 524568146473614419 125394662990827077 833573355052210872 127971722469812145 887723539635138578 546946555254801924 141411986841626521 592464745738486095 696462230276172586 962407181673158674 805589832665275824 90691217121146898 630298993788700407 526880608101849079 821302411403668314 603340655693229848 316347961609592035 121967273236533105 203602662309580038 375788773888720770 3670016 28204410133741083 874776437241456644 785518451800748349 444101455807660823 236393468967721422 980736145493856523 544310279647125321 992939671931653224 552301160930229455 607180069763627970 580349121176531352 926047408220875759 318283669166656660 361460268660333141 424696996407326937 420313544242499421 61418302862097049 899516180783468499 816680499044718528 395467623455868721 11650690236100361 264949222950723441 690488851075766873 74037116086176864 813487080347007105 318402551535564450 1835008 29668187718519233 745216827309642464 757771154115231785 478363871611447836 339527360680565466 27397361947423209 999850964977137698 282096092094876553 168103386392556489 562067042204499576 37510407407291092 726049989609606023 175932093507141142 948054481157699 925409920571511325 453869256272715180 413070236513133377 736063096006322523 449637680587897268 102320070085364506 820802604847040607 369483460933137444 563685599987269360 709860894232296315 736585469746267782 973709182618157397 79477451603250016 500619353653193622 555922791482859949 131215533542508364 971141354637464741 797111178720255164 676966040706261412 126735569270874237 626811903981311229 25599683733365115 917504 950063238108569444 803932264628416856 584328429962710028 51487380346731089 38178980115546720 853617737885743677 99024076511215006 749749790731642629 890835436574778794 85340809446330159 566154550244101356 104539283455151016 171811347126723619 305042867473439393 657148430566002556 121124075796786335 205533523417490624 959873920205409303 136843676825845923 661554851100340005 154279389616759977 900950071298611869 295466627211460609 199845582616163350 561054081216698452 646913652726400893 109577924918761308 796178548224991044 269762210850374918 419601211759818338 143051594208423978 31117607657832586 357974927169280202 210269897108892271 488429607562806800 860892867162939773 986823292525778070 912410034297659282 646384118689214894 699124967359191699 800903309224553160 764335016735376917 629466727270833343 954453363719026678 700270311393806931 389001593289725080 801186084931410632 63023628063280319 642106266178165644 406238847900435598 302685172978048136 199942045985385767 189074562558060529 992274306488354638 693611963527964762 203461406351534909 631350942782614766 20915547360471083 496643088382404509 516143585109078158 115999922606684066 473287083393946762 639900549900094001 737445931881635329 890480668663271557 58798375998608514 243255435130087595 771016460803334452 688092943942754651 257084957125850717 123282389129389716 346882746502934318 353053811211344338 886034315735531045 528125372408791568 794873885589575845 521680286234684209 493167133199061395 569348159841984976 456231968152619640 646642116668053575 640621675576412459 786188390924115673 464372138479067931 918057874431424926 739397698687544733 893588302504339678 496688926346844611 285530458961658408 157639566167842483 223602522267887231 817476494199183426 559665307262107203 84370183708269442 605684731926107747 432720268815989514 133917789968969446 40069414572232221 600668684539870858 890386067374617425 292862453550702138 201301271691647090 180144184866338963 520215728111940286 766413560980757444 61776096785703507 67439397680982096 58743815194376743 421602841180585642 122691359087952610 508608897265624295 960805781866747535 258189042404552490 93713051071738694 294656488361598016 307460908534340759 513341994942060566 897904944226594448 839719818421677112 939984579682425615 69068062394704341 316528841871775678 661705134502583793 155719910479570998 854757119175180361 89346554322449085 767833703531532880 855572360026477601 909252680490191440 397767648489488047 847929472927182156 771854648686030786 747440474907495289 977596392264721410 504659040690905130 325163518630925767 433623243383798517 969652908923425408 187960477065792962 236934509312636503 480528875479980027 266681989437921861 936852468574396989 967831376455161182 445201114325717088 976904408001880893 15041184536827494 460955190818283773 931034688420520455 146714534880415641 18731773430844299 805214818707296175 836513765452804206 561157866087428235 784594842869049555 229376 619709288920539772 101857626569816685 310636009514928709 799100820609335253 937966561469624532 83937337752904465 901729488474634613 138403929602225048 314769170825981979 300512295506048716 895858040502641979 849815943896451670 74022018495399956 711866272920109389 12226855139973401 732236661553110567 299154995392906709 316400363285431405 386455989556713416 273503246246799032 823766050361970991 957231323390324715 423026430060445235 274519611225714297 909462154897348493 2193631200026638 440062773056574353 5084288531196633 235871419068054898 404351457799337669 865733858451287311 404551428211515558 254993387769151095 457127446580062900 139065510234553384 120230181491091601 593528553114282110 288796024449183586 991669762900077925 583292865588787163 873394352737859929 888499330447844527 462636543218430686 508391092642249575 409111758208649569 784550443457848363 879551142443418715 512153497802641129 213474221135603315 112459493969626490 748344544883114733 843150985151907935 457752559776889094 678527715472758502 479966626346273645 866563374299477947 143931508592135748 226764996648813765 652390710382430323 825844457636635297 104088041228349311 57344 73051230526802031 857627641322585336 933962460493341763 636267986457669798 44183462492783974 356205026628328277 222018242722515487 198672052684226296 316180951763577516 686868082027828841 12747405638352873 77836508986354308 436235411381482979 532412768129505012 273110995576837846 730749029944220490 536124974322143601 804305056954881328 98627592022289097 9602363271177614 443349512106493217 761010997693331471 739931121674231976 986389296232711375 114105322452647134 288655827514774324 372019742076139359 114688 731414703013798318 431324429204962430 648387653888549553 446142151164310740 358716044455448508 236633910424707864 847092205520711381 740697922086620284 131374880608255151 850100300172493404 233715437409567232 988284331969322229 976789743441276992 478050962965038648 475252573109219195 93573858669592150 922656870183838763 45278777266440186 43819440557053821 998970888062607870 752676989428838333 108913829928563227 204149317819348110 701414787959193967 284854126836613172 792109844195549554 651561515469156198 468848388524581466 749662878820675147 363290858298470609 608152425829498426 14336 7168 704841063931654423 355486926462313740 177712737473923365 215517103962658065 372747270609201902 383040758971860674 200065661456520701 509794431126968712 68207659185013855 650021070026953056 246970317243737140 518892915258699087 893714960445513340 766771382149352255 51331854716639650 303195935893910560 376418332704008054 715471223651786102 835125997342988306 448 104738659615458913 188207184133471193 952956362481424550 779496504665879166 597377941430963349 270880491450680784 390476731478977573 520315390329069899 783527526170433011 613261474720953177 980397181432558729 588635521470906443 464941411707612531 813819306217942098 825579600515039525 5355937754494511 514059919330158329 920303952231115324 713545799145847707 894967303741028171 309773668438198381 319602296428316713 543893734812229637 573395606478999457 779379690248733029 440196461569669073 437737298191485248 365965234566664424 60910925086117860 399974882711880102 172460812610146540 292348592470587639 472847820486160988 568710516235441700 263024956885858986 104979907410464307 28672 835789024467210069 2989734927715659 829287739923230517 559635311178356819 968224931575610014 526980456510972487 946323201676156223 3584 233388312826744179 149512240542648657 941591768487757979 755603363315955631 551541121999018665 878268633743305166 79835318447739660 306055812194217829 979053978164809694 207329083622148392 715201157741339565 555686183699537274 10513401382981473 870116390810708937 661927148553836648 439635981221163286 942895726291414831 271119693404322435 283502494034142019 546975769820469978 39715866351518013 723331853607323022 634193289632194739 879571172457892265 434708657569554428 545771039560526000 14 670565318131560768 63718434093213820 698246578538520754 693968809352095984 759932527254311234 361309899465436567 53292186456123355 381414027443391311 616774541447471415 847327035539578271 247258422414308373 430534560409270856 582182340084904863 991177280714730467 813495170072248561 768689300294631557 539849046131175954 791804556931557037 921254630098425602 608274381609727353 651911373158583555 60992314028912178 307586275865909414 380776828399668531 450482418488536743 492573518959499357 217528143589747250 457475531345577353 756918596893832632 966950804900700794 762989281879277272 475626741222181151 250544218956068693 42625458398888458 817867536850398561 35920523723275611 632759295819457509 898811176142913397 68913548313486127 758575532023228241 961450348659924856 558920870753708445 778814708088622712 973932106027371483 831839392469218348 84487216274053918 241835296953816853 683520572280241548 467521822046194334 494212953741894653 294081037298826233 801012889355916172 910914713729563366 19624779932025158 736082096870342115 800011004205389668 623777322864778423 690253145412015457