using System; using System.Linq; using System.Diagnostics; using System.Collections.Generic; using Debug = System.Diagnostics.Debug; using StringBuilder = System.Text.StringBuilder; using System.Numerics; namespace Program { public class Solver { static long[] A = { 1, 272468856, 563649100, 860328847, 1166232007, 1469980682, 1783570422, 2114790145, 2414927516, 2724982506, 3043866212, 3368356714, 3696447371, 4034088073, 4367783000, 4668805409, 4983291841, 5311700055, 5632446048, 5962746493, 6304910373, 6633258325, 6966338873, 7301312879, 7647208853, 7993963848, 8350979267, 8692305690, 8996693216, 9310446866, 9642632564, 9958899872, 10290894339, 10635395858, 10961388861, 11294354943, 11631498032, 11975500737, 12326776476, 12683283123, 13027785740, 13355538914, 13693313090, 14038027713, 14381449601, 14738125641, 15100567476, 15442905449, 15798371073, 16166060498, 16528261375, 16906557784, 17264332938, 17566921170, 17880976368, 18210846386, 18530180413, 18861209427, 19203828677, 19531758542, 19866094009, 20200842854, 20545291667, 20893776691, 21250418457, 21598491427, 21923954489, 22261218014, 22608273828, 22950906730, 23305273534, 23670191814, 24010979129, 24366015250, 24734965862, 25096174497, 25471796065, 25842297747, 26164838803, 26499153595, 26851772374, 27187340501, 27541187813, 27914172354, 28248844171, 28602397046, 28973123644, 29329894832, 29703616942, 30089944778, 30427698867, 30782140032, 31153579736, 31510893952, 31886182974, 32270214646, 32632414911, 33010343011, 33394480827, 33782295560, 34179892637, 34523152775, 34832156390, 35148796432, 35476588679, 35795799216, 36130194883, 36480943054, 36798991078, 37130838192, 37474898933, 37816945391, 38168327856, 38530029323, 38863519344, 39197471652, 39532744146, 39877248944, 40226443498, 40582963016, 40939570400, 41286912813, 41643820417, 42009688165, 42377640293, 42754518130, 43106018740, 43435219978, 43772319823, 44117394206, 44462028976, 44820014965, 45179326243, 45522928237, 45879798982, 46246138687, 46609701908, 46987727319, 47357207033, 47703142216, 48061009294, 48425512331, 48792273164, 49169196783, 49544485554, 49915842586, 50292078218, 50675865247, 51067373801, 51472185050, 51804505761, 52134752072, 52477074082, 52818700345, 53170975039, 53529119448, 53879955833, 54233065497, 54589442905, 54952916975, 55324780533, 55705204302, 56058804034, 56410699097, 56772014039, 57133698007, 57505226047, 57888149231, 58255379360, 58625752167, 59013445746, 59392769277, 59786991162, 60183426398, 60525078043, 60879847551, 61248412940, 61610149400, 61986287799, 62366056429, 62731107733, 63108690096, 63493508847, 63885363445, 64282614398, 64657845640, 65029351186, 65412717008, 65794312624, 66187046733, 66594902248, 66975285229, 67372611031, 67776921688, 68187563034, 68606219970, 68934810714, 69249229138, 69563214155, 69889053360, 70213317069, 70548792816, 70896440274, 71214025117, 71548449057, 71896995173, 72235775351, 72587898602, 72954789126, 73281428742, 73611431536, 73954116149, 74295352127, 74647629903, 75006086342, 75356722003, 75709657389, 76066476715, 76429844397, 76801655356, 77182126886, 77521035394, 77854879280, 78190494896, 78534903935, 78884623046, 79240902799, 79597019778, 79944882229, 80301624822, 80667255480, 81035843735, 81412578197, 81774573184, 82126709234, 82482422734, 82846466951, 83219305556, 83595802433, 83966130352, 84337635812, 84719748804, 85102940644, 85495003021, 85903678348, 86217961301, 86551199349, 86897380693, 87239709626, 87589330442, 87953309938, 88299966376, 88651217362, 89013582802, 89376526789, 89746820666, 90133132445, 90478715504, 90830070298, 91195948847, 91556662143, 91928917768, 92318023926, 92676618595, 93049983122, 93439998092, 93820356302, 94218075480, 94599746239, 94945522504, 95303593667, 95668008293, 96034652099, 96411494050, 96787038863, 97158013922, 97534340077, 97918157161, 98309496002, 98713990453, 99080204117, 99453474470, 99843074535, 100219967016, 100615653808, 101016865959, 101402921372, 101800524148, 102204666861, 102615505268, 103042167188, 103367140606, 103698858755, 104042470507, 104384424189, 104735939624, 105097612720, 105445535326, 105797766382, 106157848850, 106520038461, 106891489332, 107274235133, 107625497518, 107976680264, 108339020461, 108701865647, 109072273412, 109458484061, 109821244629, 110194551904, 110584707099, 110961378111, 111357125985, 111747571294, 112090962920, 112447517929, 112814316419, 113177498741, 113555672022, 113932646967, 114299740451, 114676919658, 115061026450, 115452565842, 115853066778, 116226216308, 116596240038, 116982898326, 117362587875, 117756428334, 118161596450, 118543768613, 118941558853, 119345552459, 119756595296, 120178877341, 120533828633, 120884139647, 121249132308, 121611143237, 121982138043, 122370471866, 122729992530, 123103513707, 123494368506, 123872887789, 124269913992, 124661141895, 125027893958, 125404818570, 125789131046, 126180932589, 126580448550, 126970141277, 127360339056, 127771357210, 128168809057, 128586646178, 128985909917, 129354551818, 129731274419, 130115209628, 130506363333, 130909206971, 131294634763, 131687304762, 132096591970, 132497264357, 132915045706, 133318905970, 133710517905, 134111472771, 134514011902, 134926874071, 135350966231, 135755141295, 136173201237, 136597646522, 137029535272, 137462808125, 137759182972, 138072373432, 138396573406, 138718181714, 139052375614, 139387263292, 139722982077, 140049262364, 140387408077, 140732668145, 141075526632, 141431789682, 141790463807, 142111020199, 142445346067, 142798286786, 143133469103, 143487358382, 143857011733, 144194746393, 144548714742, 144916552250, 145274865347, 145648225021, 146037422438, 146352334380, 146685993086, 147032675069, 147374206797, 147724195504, 148088629994, 148435095124, 148785631119, 149149075971, 149512054409, 149882089846, 150268738007, 150613169053, 150964933688, 151331584274, 151691599299, 152064555992, 152454113788, 152811415545, 153185209653, 153575001573, 153955534708, 154353633349, 154726734363, 155051645119, 155387899956, 155736319002, 156076627173, 156431926045, 156798952109, 157137575827, 157492146179, 157862645872, 158221107575, 158596635939, 158975752978, 159318255423, 159672959626, 160041017058, 160402984627, 160780366868, 161158963756, 161524770483, 161902120281, 162286550795, 162678433494, 163077130750, 163436218725, 163787963244, 164149606192, 164511277395, 164882870465, 165265927541, 165632628250, 166003338830, 166391382684, 166770240178, 167165011852, 167564557338, 167926774511, 168305223781, 168688960027, 169077182533, 169474740422, 169866379992, 170257921203, 170663002671, 171063531653, 171478517823, 171876516828, 172200303917, 172534512697, 172886010936, 173222317218, 173576727178, 173949104558, 174283996068, 174637498410, 175009281200, 175365124328, 175739358679, 176124540595, 176463203203, 176817588144, 177188326764, 177546482883, 177922065801, 178305570797, 178667873929, 179046824749, 179430231579, 179818840477, 180216276681, 180582802771, 180935812837, 181292503713, 181655909949, 182027702531, 182408189778, 182776411125, 183147515364, 183532001795, 183913175460, 184306041773, 184711441709, 185070714646, 185446255978, 185833103318, 186217776606, 186615413487, 187009120727, 187400891844, 187802136889, 188204498002, 188617425859, 189030613453, 189371970901, 189726804355, 190095501438, 190457184794, 190833065703, 191213106972, 191577940659, 191955578949, 192340450187, 192731827893, 193129137335, 193504635163, 193876283026, 194259404542, 194641225561, 195033859133, 195441963222, 195821972488, 196219122517, 196623510203, 197034497965, 197452803437, 197830778378, 198200809867, 198587480528, 198967163788, 199361007593, 199766172020, 200148332580, 200546136023, 200950122647, 201361154932, 201783473449, 202170968418, 202564213699, 202973076904, 203374783546, 203792708069, 204206289209, 204617496631, 205043511058, 205463749728, 205901605015, 206291552308, 206617092652, 206954985996, 207301105038, 207643556190, 207999147186, 208362812882, 208704941082, 209059602546, 209427975691, 209789717168, 210166401061, 210539932178, 210883962839, 211241331372, 211606934845, 211970952249, 212349023226, 212726029370, 213093610490, 213471105767, 213854589804, 214246255316, 214647882597, 215003148329, 215354169177, 215716862092, 216079823682, 216450083172, 216836505698, 217198961226, 217572090834, 217963153522, 218339524784, 218735376221, 219130300531, 219495115388, 219872768869, 220257648778, 220648995196, 221046311026, 221435927962, 221827039627, 222235311161, 222634272589, 223051245661, 223447146764, 223792750930, 224150935785, 224515285202, 224881948287, 225258661454, 225634262498, 226005034764, 226381324929, 226765329947, 227156519976, 227560780296, 227927467940, 228300450871, 228690056611, 229067031511, 229462711316, 229864119873, 230250049627, 230647419412, 231051557994, 231462612055, 231888869015, 232251736410, 232625258768, 233016113227, 233394644853, 233791662873, 234189550667, 234578074839, 234975486856, 235379590348, 235790901205, 236221817282, 236597532732, 236993951888, 237399469289, 237808099240, 238226943962, 238637796475, 239048615955, 239476745421, 239898799642, 240337250967, 240718182584, 241070585786, 241427944677, 241791561736, 242163091985, 242543758169, 242911954903, 243282777192, 243668234157, 244048564328, 244441961634, 244846646655, 245206435374, 245582174037, 245968381379, 246354023499, 246751530394, 247144906930, 247536205081, 247938214498, 248340289572, 248753689891, 249169343989, 249531608877, 249910104217, 250293791186, 250682070234, 251079618110, 251471228540, 251862740592, 252267865239, 252668369149, 253083427939, 253497943610, 253884567692, 254282368803, 254686441361, 255097540306, 255525495774, 255925051308, 256342539975, 256766924261, 257196764397, 257640282068, 258008550324, 258381856246, 258773902383, 259149922031, 259546407774, 259946115862, 260332956441, 260730619929, 261134651243, 261545748643, 261974620506, 262353169362, 262748836993, 263155014595, 263562275526, 263980820614, 264392085346, 264803579556, 265232334890, 265652863074, 266091238420, 266499308735, 266891020775, 267295743209, 267696445371, 268110983060, 268531551868, 268939733186, 269358344420, 269782948626, 270214432927, 270653190668, 271058307147, 271476380235, 271901042921, 272333014057, 272777094984, 273201385098, 273639889437, 274084589524, 274537163542, 274954969328, 275256585885, 275570833646, 275899977510, 276220806575, 276550885608, 276893355677, 277221362134, 277555010020, 277889700156, 278235349289, 278582404274, 278939453583, 279288160709, 279613361806, 279949996554, 280297873316, 280639051583, 280993965973, 281359996865, 281699656520, 282054817240, 282424472084, 282784011342, 283159636287, 283532815989, 283853991566, 284188280466, 284542383019, 284876998796, 285230291483, 285601515912, 285937742162, 286291725643, 286660829943, 287018460850, 287392134685, 287780049124, 288116736056, 288471032567, 288843338529, 289199247412, 289574843642, 289959345704, 290321127384, 290697914218, 291082994188, 291469877297, 291867499733, 292225596028, 292555622135, 292892083193, 293237342432, 293582727254, 293941204916, 294299027632, 294643670923, 295001598892, 295366304445, 295731181159, 296108809336, 296477580277, 296824482717, 297181343624, 297546391728, 297913802581, 298291028752, 298665064249, 299038337956, 299414169438, 299797478106, 300188731346, 300594830153, 300940722962, 301292706058, 301659455418, 302019442106, 302392909184, 302782647624, 303139250106, 303513296426, 303902975032, 304283570332, 304681623600, 305070319063, 305438074433, 305815602021, 306198988159, 306590455688, 306992282618, 307378730113, 307771179944, 308180942926, 308580525059, 308998168532, 309375584150, 309702228342, 310040492873, 310385420526, 310728417888, 311084691351, 311447641182, 311790090574, 312144839708, 312512898104, 312874881380, 313252320771, 313624690967, 313969299744, 314326865492, 314691888318, 315056459071, 315434187295, 315811536234, 316179444874, 316556574461, 316940220538, 317331554514, 317733761048, 318088540201, 318438834135, 318802384050, 319165667684, 319535590021, 319922366890, 320283900459, 320657198038, 321049488257, 321425133978, 321821635044, 322215373230, 322580679794, 322958275691, 323342801770, 323735019206, 324132816437, 324521954755, 324912661618, 325321725972, 325720216447, 326137829796, 326531960462, 326878073736, 327235768075, 327600378151, 327967124398, 328344168319, 328719203507, 329090926490, 329467154842, 329850743236, 330242557302, 330647207406, 331012699805, 331385940946, 331776265114, 332152890057, 332548663356, 332949302105, 333335611784, 333733585567, 334137527103, 334548337509, 334975736521, 335337160498, 335710857866, 336101055438, 336480827113, 336878020255, 337275158847, 337664009017, 338061750962, 338465760385, 338876971341, 339306800513, 339683323432, 340079884926, 340485204509, 340894639741, 341313816873, 341723231862, 342134460788, 342562364126, 342985479341, 343423982076, 343789429912, 344122610962, 344457527672, 344803514957, 345150179777, 345507238667, 345864465250, 346211041716, 346568279070, 346933020305, 347300064350, 347677237653, 348042442044, 348391825412, 348748304608, 349113030840, 349483458997, 349859876448, 350232133330, 350603988850, 350984406135, 351367456413, 351758191745, 352167509680, 352506179838, 352860264736, 353228746418, 353586441114, 353959976604, 354349728061, 354707032557, 355082312075, 355470060658, 355853133389, 356250931829, 356636401290, 357008103261, 357384338707, 357767934986, 358159725869, 358564384537, 358947047991, 359340597769, 359748930020, 360151639648, 360569937186, 360949458593, 361301942211, 361657515893, 362021385491, 362394197650, 362771180675, 363141281442, 363512777375, 363895119940, 364277970856, 364670362334, 365079193491, 365435138349, 365810705153, 366198335844, 366580889061, 366978564769, 367373822066, 367765728401, 368164629325, 368568273747, 368979662887, 369401234853, 369761246628, 370136993397, 370523119695, 370908873236, 371306326316, 371699639818, 372090932249, 372493008264, 372895037591, 373308529954, 373728188040, 374111296941, 374509101599, 374913087888, 375324178391, 375748638325, 376151464705, 376566735456, 376992499684, 377423283509, 377862283693, 378224220960, 378573791593, 378937809271, 379301166975, 379671116421, 380058390875, 380419190289, 380792684686, 381184164591, 381561054003, 381957670005, 382350695979, 382716541106, 383093788053, 383478195738, 383870119640, 384268873005, 384657901324, 385048519578, 385458394038, 385856452156, 386274690051, 386675148092, 387042908925, 387420387422, 387803833108, 388195290241, 388597147509, 388983554864, 389376014230, 389785718954, 390185404192, 390603065716, 391007973020, 391399435954, 391799556548, 392202572772, 392614805711, 393039657209, 393442810131, 393861322106, 394285074566, 394716718756, 395158774397, 395517102640, 395892667666, 396280130332, 396663880074, 397061465498, 397455773322, 397847294362, 398247899893, 398650639743, 399063459829, 399484449882, 399867029816, 400264685066, 400668724406, 401079613911, 401502406550, 401906744673, 402321458969, 402747347190, 403176725486, 403615767698, 404011963610, 404404188890, 404813934876, 405213251413, 405630767434, 406045283138, 406456112686, 406880295399, 407300998595, 407738084917, 408166458655, 408577136610, 408997693611, 409419836346, 409854838905, 410293988630, 410723904198, 411165192284, 411607003789, 412064701934, 412459892513, 412787675041, 413125434853, 413470177564, 413813599048, 414170300487, 414532674883, 414875055295, 415230531724, 415598208178, 415960418167, 416338754957, 416709751898, 417054435999, 417412997744, 417777139873, 418142353090, 418519948662, 418896774625, 419265501228, 419642241648, 420026208319, 420417331777, 420820252091, 421174445522, 421523913358, 421888019177, 422251267533, 422621285932, 423008592777, 423369329089, 423742809746, 424134311353, 424511279122, 424907933415, 425300867467, 425666765428, 426043956205, 426428353526, 426820292310, 427219090689, 427608146253, 427998743258, 428408653557, 428806725968, 429224980146, 429617152385, 429963863592, 430320980018, 430685820402, 431052903006, 431430068739, 431804519400, 432177395739, 432553210740, 432936691509, 433327999033, 433733530012, 434097972525, 434471270047, 434863107905, 435238889956, 435635177453, 436035044250, 436421737138, 436819529994, 437223521918, 437634615299, 438062734708, 438423000365, 438796401986, 439186369819, 439566756993, 439964891115, 440361162568, 440750473367, 441148023505, 441552087077, 441963574824, 442391779385, 442769590824, 443166351690, 443571343058, 443981552035, 444400242354, 444808941609, 445220703704, 445648451420, 446072758561, 446511151826, 446887863691, 447240138170, 447599345941, 447961965780, 448333437741, 448715363575, 449083546035, 449453713512, 449840189964, 450219957229, 450613672574, 451016138940, 451377843528, 451753933965, 452139310790, 452525875722, 452923691653, 453316542661, 453707576621, 454110917603, 454512303700, 454926738270, 455339433310, 455702958070, 456080937029, 456465371949, 456854519914, 457252089173, 457642861328, 458034042667, 458440607830, 458840409321, 459256482677, 459669087958, 460056865178, 460454459144, 460858503477, 461269868218, 461699656553, 462097779607, 462516131473, 462938986011, 463369384418, 463814559471, 464179262642, 464552796690, 464943655977, 465322055399, 465719100268, 466117040797, 466505438580, 466902891538, 467306976618, 467718323666, 468149074299, 468525009072, 468921314677, 469326966506, 469735448328, 470154279181, 470565134403, 470976069404, 471404162967, 471826195769, 472264601503, 472670820245, 473062030890, 473468254665, 473868179974, 474283949228, 474703374234, 475112937781, 475532126702, 475955007807, 476387578333, 476824486461, 477231052318, 477649605214, 478074609345, 478505727674, 478949396296, 479374621143, 479813901853, 480257549621, 480711226772, 481137046691, 481481680156, 481840655254, 482204364671, 482569846746, 482947439062, 483323794065, 483692977544, 484069679499, 484453724985, 484844914786, 485248080048, 485616841740, 485988588035, 486377450536, 486755371546, 487150637682, 487553025941, 487937470898, 488335220753, 488739231350, 489150436333, 489575733726, 489940639767, 490314176858, 490705646259, 491082492471, 491479109530, 491878183069, 492265546930, 492663323054, 493067305904, 493478499445, 493907875573, 494285702773, 494681424791, 495087537843, 495495281496, 495913796787, 496324830959, 496736570450, 497164718363, 497585752377, 498024185200, 498419761392, 498791098622, 499172368535, 499556395751, 499946707989, 500357443142, 500733994162, 501129897532, 501535793424, 501944025241, 502362698075, 502758835083, 503149878702, 503558370652, 503957121730, 504374434052, 504792318352, 505202589872, 505621537289, 506044055582, 506478515443, 506906580542, 507293438198, 507691103349, 508095124201, 508506218675, 508935069724, 509334007506, 509752007401, 510175605302, 510605633736, 511049944011, 511453769128, 511869845667, 512295264444, 512725373619, 513166144224, 513591107941, 514027271879, 514471819850, 514921730267, 515389888649, 515746151976, 516120645966, 516509586091, 516890936346, 517288857480, 517685071701, 518076656879, 518473954299, 518878102214, 519289749375, 519714645823, 520095012656, 520492533268, 520896827462, 521307331285, 521726074118, 522133460995, 522546285667, 522973779777, 523399099799, 523838389842, 524240198445, 524630950719, 525040300253, 525438600325, 525856504978, 526273017638, 526683535170, 527103457680, 527525826917, 527960458550, 528393449648, 528803353699, 529222405933, 529645152611, 530078026637, 530519211692, 530948280332, 531387366356, 531830142929, 532286129145, 532718052818, 533109760393, 533507089380, 533911179954, 534322751540, 534749127736, 535149690863, 535567499478, 535991669365, 536422408674, 536872350337, 537270016027, 537687311634, 538110881857, 538541410642, 538987738083, 539408887646, 539846264102, 540290279141, 540741118155, 541201884407, 541603610800, 542021554402, 542445766977, 542876951076, 543325032609, 543744721780, 544183093660, 544627454221, 545079102727, 545537031039, 545964300682, 546403938376, 546846436546, 547301407375, 547758821020, 548208765687, 548677049045, 549136811513, 549617229966, 549964374392, 550277672281, 550592584322, 550918245602, 551242250913, 551577299199, 551926010993, 552243254512, 552577704794, 552925090775, 553264635618, 553616341876, 553982813022, 554309590979, 554640297977, 554981805974, 555324210529, 555676647128, 556033975615, 556385134381, 556738921500, 557094184963, 557457858658, 557829972985, 558210035836, 558550302810, 558884634865, 559219382831, 559563840963, 559912363145, 560268979550, 560626369299, 560972971546, 561330089610, 561695378546, 562063150010, 562440594632, 562803275476, 563154351847, 563510753765, 563874584971, 564247426389, 564623255946, 564994400089, 565365797869, 565747207366, 566131414999, 566521828885, 566933008719, 567246871425, 567579851122, 567925491786, 568267447013, 568618071111, 568981357189, 569328054371, 569679357945, 570041556993, 570404156594, 570774912776, 571160501132, 571507737236, 571858247194, 572223399213, 572585220720, 572956553061, 573345170049, 573704289081, 574077826799, 574468602741, 574847491794, 575244570057, 575628611714, 575973613140, 576332482721, 576696346495, 577062073185, 577439508313, 577815644715, 578185235747, 578561935277, 578946061755, 579336945391, 579740475323, 580108586103, 580480751555, 580869843135, 581247549746, 581642857022, 582044949069, 582429876053, 582827469762, 583231514124, 583642878785, 584068232489, 584396611826, 584727935288, 585071044292, 585412682639, 585764635647, 586125736798, 586474043930, 586826320685, 587185448355, 587548125987, 587919588726, 588301523784, 588653612525, 589004843649, 589367087676, 589729513812, 590100368528, 590485643190, 590849466513, 591222092439, 591611420901, 591988736120, 592384285778, 592776838356, 593119490163, 593475532637, 593842941483, 594205217992, 594584205659, 594960809199, 595327558763, 595704567660, 596088834674, 596480632590, 596880218803, 597253735799, 597624161138, 598010325386, 598390213848, 598783770848, 599189711161, 599571165168, 599969170000, 600373164701, 600783880399, 601205178127, 601563213807, 601912655594, 602276789225, 602640000928, 603010036773, 603397357922, 603758078748, 604131558058, 604523043314, 604900047733, 605296717965, 605689622509, 606055535834, 606432710340, 606817108912, 607209049460, 607607861549, 607996922408, 608387515686, 608797434051, 609195499684, 609613776225, 610014086322, 610381871594, 610759278122, 611142821342, 611534193618, 611936152792, 612322481419, 612714947263, 613124606207, 613524410050, 613942070950, 614346953732, 614738366236, 615138531541, 615541515935, 615953831172, 616378579454, 616781796472, 617200385061, 617624104491, 618055837482, 618494644142, 618811719280, 619146269506, 619492775848, 619832855781, 620184162678, 620549989547, 620895126320, 621245164498, 621609731741, 621972254824, 622342935994, 622730866907, 623072645847, 623425191203, 623792407627, 624151612496, 624524910690, 624917226658, 625271673298, 625646427375, 626034991988, 626416648586, 626814638241, 627194398350, 627541178218, 627898157835, 628263363997, 628630920343, 629008378139, 629381935183, 629754754282, 630131499547, 630514787180, 630905954546, 631312495869, 631675273944, 632048750926, 632440248323, 632817224875, 633213883629, 633612831737, 634000281796, 634398003041, 634802011556, 635213242456, 635642733172, 635980006757, 636333922093, 636703471280, 637060973981, 637434612463, 637823298243, 638181438445, 638556986940, 638944611997, 639328046749, 639725729309, 640110461978, 640483343578, 640859157032, 641242635036, 641633944666, 642039475338, 642421663991, 642815476756, 643223603787, 643626997911, 644045468191, 644434745133, 644806778506, 645187107110, 645569938552, 645960717029, 646369655949, 646748086675, 647143563748, 647550141597, 647956716822, 648375252409, 648773087377, 649163971231, 649571082101, 649970536938, 650387040722, 650805719865, 651216210240, 651634663327, 652057494947, 652490864964, 652911366356, 653254667986, 653610984478, 653978043083, 654340820929, 654719196150, 655096078772, 655463076448, 655840271968, 656224576189, 656615911432, 657016239714, 657389495268, 657759658750, 658146134026, 658525904076, 658919619890, 659324951012, 659706970877, 660104803135, 660508803182, 660919817414, 661341860359, 661713381400, 662085614135, 662474707972, 662852364121, 663247702173, 663649754406, 664034735323, 664432349345, 664836377279, 665247776668, 665673142858, 666056469887, 666450612654, 666858300237, 667263109743, 667680818409, 668092915894, 668504407901, 668934374372, 669352980318, 669790325820, 670191528127, 670564089628, 670942265558, 671325445931, 671716289869, 672123851671, 672504195165, 672899222436, 673306256613, 673711367646, 674129434810, 674528754572, 674920073842, 675325604446, 675725875770, 676141175724, 676561168356, 676969973128, 677388916803, 677812606610, 678244658509, 678678164008, 679062473569, 679460277667, 679864255700, 680275412064, 680700568090, 681102545215, 681518440086, 681944051001, 682374196306, 682814636496, 683222796403, 683637673925, 684063382255, 684492287082, 684931492095, 685358688850, 685793112805, 686238800343, 686688081834, 687151958521, 687481139203, 687812631750, 688156163565, 688498052941, 688849652255, 689211343502, 689559265892, 689911535279, 690271265396, 690633746282, 691005135593, 691387675852, 691739036991, 692090271191, 692452546881, 692815473721, 693185927451, 693572016540, 693934884550, 694308398049, 694698010808, 695074792956, 695470517830, 695861454783, 696204766375, 696561122856, 696928134215, 697290992240, 697669335632, 698046236609, 698413261424, 698790443109, 699174717779, 699566093251, 699966479693, 700339739044, 700709823543, 701096333492, 701476114233, 701869844140, 702275134877, 702657186657, 703054998548, 703459014946, 703870054605, 704292108860, 704647732706, 704997855662, 705362572698, 705724983246, 706095694277, 706483779223, 706843614895, 707217077730, 707608109375, 707986281273, 708383228428, 708774850992, 709141525004, 709518372333, 709902766909, 710294474152, 710693865398, 711083438845, 711473757901, 711884474135, 712282057557, 712700171442, 713099812794, 713468162786, 713844885121, 714228648026, 714619883261, 715022516642, 715408154703, 715800888416, 716210181941, 716610614309, 717028460170, 717432489725, 717824036379, 718224852507, 718627498906, 719040292107, 719464426290, 719868450949, 720286559106, 720710847860, 721142705765, 721580806772, 721918806699, 722273251364, 722644633790, 723002026267, 723377336004, 723761306174, 724123504132, 724501658298, 724885629032, 725273620348, 725671199568, 726051331129, 726422583615, 726803561592, 727187482745, 727577976530, 727988412840, 728365291154, 728761045579, 729166981354, 729575153362, 729993764865, 730375895797, 730747568720, 731130678463, 731512464850, 731905144965, 732313170702, 732693287993, 733090432253, 733494813784, 733905748702, 734324108109, 734717019390, 735109163321, 735519189936, 735917871398, 736335089691, 736749758874, 737160661600, 737583427613, 738004906141, 738441229522, 738856174302, 739223609714, 739600927269, 739984698792, 740376345601, 740777465961, 741164718224, 741557051266, 741966794834, 742365961900, 742783307821, 743188874590, 743580598436, 743979991572, 744383356533, 744795165468, 745220377148, 745622885657, 746041140776, 746465205389, 746896572050, 747341747230, 747720872292, 748117943188, 748522525321, 748933922639, 749351708985, 749759697502, 750172097793, 750599629955, 751024347007, 751463306778, 751880872432, 752292435373, 752720302619, 753141880458, 753580360109, 754012739492, 754444633027, 754891381148, 755336643853, 755796796009, 756166419406, 756517676961, 756879947881, 757242843585, 757613224286, 757999459349, 758362211186, 758735424501, 759125818601, 759502441938, 759898210819, 760293710398, 760658121328, 761035892927, 761420952602, 761811682354, 762209023794, 762598901987, 762989904072, 763398070845, 763796995650, 764213815204, 764617557232, 764984543942, 765361722530, 765746055984, 766137370648, 766537676057, 766926219065, 767317734941, 767728469239, 768126681142, 768543759538, 768950249380, 769342102036, 769740786111, 770144544094, 770555585864, 770981663499, 771383308571, 771801069085, 772225415477, 772656417793, 773102984407, 773459300656, 773834660178, 774222391612, 774605120671, 775002837011, 775397873618, 775789708589, 776188881492, 776592421689, 777003979124, 777427173616, 777808469461, 778206272362, 778610252894, 779020939116, 779441824544, 779847611133, 780261406507, 780688157115, 781115568136, 781555204200, 781954726787, 782345447050, 782756848675, 783154062627, 783571696993, 783986616204, 784397490184, 784819265983, 785241482314, 785677079533, 786108175801, 786519107873, 786937469003, 787360097555, 787794369346, 788234164601, 788665127917, 789103912328, 789546215920, 790004251744, 790422169791, 790792885424, 791169191981, 791553252818, 791944406391, 792348616898, 792732190565, 793125745635, 793534166666, 793936199809, 794354207463, 794756728906, 795148075630, 795550462220, 795952286337, 796365990188, 796788895388, 797194369610, 797612465334, 798037198887, 798469038921, 798907709237, 799289399447, 799687356918, 800091304255, 800502117783, 800923732951, 801328972319, 801743227036, 802169596528, 802597656888, 803037106708, 803449706202, 803862443625, 804289818583, 804714759389, 805153948274, 805584580099, 806016345293, 806462750916, 806912321584, 807371886246, 807765161324, 808158770188, 808567159262, 808969241060, 809387303477, 809800999862, 810211805541, 810638544883, 811058624008, 811496355429, 811921057876, 812331967883, 812756245695, 813176851351, 813614103313, 814049923628, 814480115181, 814925000879, 815366581984, 815823723357, 816254195533, 816665287720, 817093384796, 817513331061, 817950499985, 818384553332, 818815284449, 819265588832, 819704108373, 820162741412, 820602171717, 821033071135, 821480220758, 821927081237, 822387103092, 822833188399, 823291446296, 823753887272, 824225443064, 824682389702, 825002406262, 825336664996, 825688098649, 826024354516, 826378750356, 826746806109, 827085965369, 827438839894, 827806265541, 828165340384, 828538638817, 828930392300, 829265121436, 829618514685, 829989997557, 830346115282, 830720144582, 831107748747, 831467379610, 831843071698, 832229503850, 832614810573, 833012364707, 833385182994, 833736154186, 834092500400, 834456466214, 834829059133, 835205045601, 835576293417, 835947648405, 836329001352, 836713379215, 837103543758, 837514540685, 837869849205, 838244378913, 838633219127, 839014628312, 839412606178, 839808753739, 840200563740, 840597829493, 841001974696, 841413439586, 841835193780, 842172566043, 842526985416, 842898746380, 843255710591, 843630833308, 844015128001, 844377113023, 844754556333, 845139162413, 845526512265, 845924301194, 846304666105, 846676402847, 847056962704, 847440316457, 847830932678, 848240782396, 848618287413, 849013979593, 849420121421, 849827622308, 850246151856, 850629346045, 851000862079, 851383818991, 851765990426, 852158442536, 852567187068, 852946045846, 853343069725, 853747688137, 854158852380, 854576859776, 854970850502, 855361923865, 855773169362, 856170680213, 856588039158, 857002925005, 857413905805, 857835953013, 858257837778, 858693602005, 859102581348, 859448191066, 859806361441, 860170710178, 860537366735, 860914134590, 861289710925, 861660536604, 862036785630, 862420769138, 862811992366, 863216289474, 863582897550, 863955921348, 864345547592, 864722519533, 865118183262, 865519592653, 865905574594, 866302909929, 866707040528, 867118060161, 867544389704, 867907177426, 868280712714, 868671555089, 869050133827, 869447143816, 869845011459, 870233585965, 870630966941, 871035094970, 871446393635, 871877377915, 872252989167, 872649460782, 873054931794, 873463619464, 873882468917, 874293323683, 874704090728, 875132241129, 875554302728, 875992771661, 876385953970, 876757433560, 877139429197, 877522802074, 877914541507, 878324768992, 878701185752, 879097746098, 879503038972, 879912442888, 880331586089, 880726445725, 881117063341, 881526923742, 881924987388, 882343219476, 882758961035, 883169665968, 883590032966, 884012143117, 884447043197, 884873137193, 885261124468, 885658701687, 886062792258, 886474307565, 886904290352, 887302123590, 887720236940, 888143280200, 888573665350, 889019150173, 889421408978, 889838183538, 890263656122, 890693026294, 891135486516, 891559165826, 891996345815, 892439997159, 892890241589, 893357076781, 893692061855, 894045653774, 894417665466, 894773301921, 895147683754, 895534897170, 895894981736, 896270721715, 896656828737, 897042618034, 897440059694, 897822674154, 898195333951, 898573156269, 898956528245, 899347259018, 899754550956, 900135304724, 900529957294, 900937436114, 901342249519, 901760199509, 902147625629, 902518966064, 902900291363, 903284534680, 903674751149, 904085632388, 904461959210, 904858018617, 905263873833, 905672137367, 906090855432, 906486869570, 906877843100, 907286546765, 907685190026, 908102558732, 908520312270, 908930597650, 909349687556, 909772129132, 910206629748, 910628351787, 910993978876, 911371577766, 911755883600, 912147946301, 912546500343, 912935197816, 913325959871, 913735370979, 914133619903, 914551550925, 914960862660, 915350463714, 915747908991, 916152060532, 916563592891, 916991610209, 917391126900, 917808707287, 918232550082, 918663363469, 919112044954, 919489944535, 919885714570, 920291660616, 920699835678, 921118285558, 921529197170, 921941106979, 922368908269, 922790149282, 923228594605, 923648457879, 924059753965, 924490741365, 924908557081, 925346212987, 925779513448, 926210825894, 926659221254, 927101005980, 927560339376, 927953326671, 928324426778, 928708929555, 929090084628, 929482964507, 929890215788, 930270736126, 930668850692, 931072771711, 931483231506, 931903018314, 932294263359, 932686617460, 933096349589, 933495757285, 933913308351, 934327743215, 934738659715, 935162943841, 935583558606, 936020823191, 936441420445, 936832250268, 937229619734, 937633721709, 938045542316, 938472256198, 938872494293, 939290376882, 939714206628, 940145131973, 940594928117, 940992532852, 941410256794, 941833492114, 942263956316, 942709938290, 943131417526, 943568922441, 944012581889, 944463451804, 944923194197, 945303774069, 945701829433, 946105733139, 946516246785, 946936098999, 947342882416, 947755839267, 948183340778, 948609286489, 949049124016, 949464077559, 949875656530, 950303402824, 950726958682, 951165540848, 951597756820, 952028704023, 952475956768, 952922640513, 953382717840, 953795945236, 954209928426, 954636556054, 955064181066, 955503787985, 955931841037, 956365519301, 956811050770, 957260544932, 957723191654, 958148043412, 958586212635, 959028881135, 959479472149, 959946162612, 960388044820, 960847472586, 961310898488, 961786926704, 962209863199, 962557180887, 962914103801, 963279921820, 963647875815, 964024768740, 964397663566, 964770214719, 965148557266, 965531663221, 965922590824, 966330252636, 966691377997, 967064911245, 967455752662, 967834326487, 968231336754, 968629207861, 969017773865, 969415159722, 969819285239, 970230595632, 970661562733, 971016196875, 971390899993, 971779514592, 972161136306, 972559143829, 972954996960, 973347373580, 973744657012, 974148842453, 974559938585, 974984582019, 975365006125, 975763287764, 976167131474, 976577472175, 976996777124, 977403849004, 977816739031, 978244422268, 978669818586, 979109454076, 979495535605, 979866439343, 980251382282, 980632158312, 981025204065, 981432355954, 981812882713, 982210942474, 982614888897, 983025485067, 983445676163, 983836311144, 984228763218, 984638498788, 985038134994, 985455796533, 985870025629, 986281071494, 986705404745, 987126039101, 987563621527, 987983393422, 988374849517, 988772143338, 989176344142, 989588068311, 990014429317, 990414867206, 990832716217, 991256821463, 991687547224, 992137825273, 992535096437, 992952552801, 993375995680, 993806560489, 994252783159, 994673968319, 995111414744, 995555297507, 996006161642, 996463258969, 996822842586, 997198486019, 997584975853, 997970187874, 998367757387, 998761263169, 999152819172, 999554552659, 999956784736 }; public void Solve() { var n = sc.Long(); var p = Array.BinarySearch(A, n); var cnt = 0L; if (p < 0) { p = (~p) - 1; cnt = p * (long)2e7; } else { IO.Printer.Out.WriteLine(p * (long)(2e7) + 1); return; } var v = A[p]; while (v < n) { v += BitOperation.PopCount(v); cnt++; } if (v != n) IO.Printer.Out.WriteLine(-1); else IO.Printer.Out.WriteLine(cnt + 1); } public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput()); static T[] Enumerate(int n, Func f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; } static public void Swap(ref T a, ref T b) { var tmp = a; a = b; b = tmp; } } } #region main static class Ex { static public string AsString(this IEnumerable ie) { return new string(System.Linq.Enumerable.ToArray(ie)); } static public string AsJoinedString(this IEnumerable ie, string st = " ") { return string.Join(st, ie); } static public void Main() { var solver = new Program.Solver(); solver.Solve(); Program.IO.Printer.Out.Flush(); } } #endregion #region Ex namespace Program.IO { using System.IO; using System.Text; using System.Globalization; public class Printer : StreamWriter { static Printer() { Out = new Printer(Console.OpenStandardOutput()) { AutoFlush = false }; } public static Printer Out { get; set; } public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } } public Printer(System.IO.Stream stream) : base(stream, new UTF8Encoding(false, true)) { } public Printer(System.IO.Stream stream, Encoding encoding) : base(stream, encoding) { } public void Write(string format, T[] source) { base.Write(format, source.OfType().ToArray()); } public void WriteLine(string format, T[] source) { base.WriteLine(format, source.OfType().ToArray()); } } public class StreamScanner { public StreamScanner(Stream stream) { str = stream; } public readonly Stream str; private readonly byte[] buf = new byte[1024]; private int len, ptr; public bool isEof = false; public bool IsEndOfStream { get { return isEof; } } private byte read() { if (isEof) return 0; if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 1024)) <= 0) { isEof = true; return 0; } } return buf[ptr++]; } public char Char() { byte b = 0; do b = read(); while ((b < 33 || 126 < b) && !isEof); return (char)b; } public string Scan() { var sb = new StringBuilder(); for (var b = Char(); b >= 33 && b <= 126; b = (char)read()) sb.Append(b); return sb.ToString(); } public string ScanLine() { var sb = new StringBuilder(); for (var b = Char(); b != '\n'; b = (char)read()) if (b == 0) break; else if (b != '\r') sb.Append(b); return sb.ToString(); } public long Long() { if (isEof) return long.MinValue; long ret = 0; byte b = 0; var ng = false; do b = read(); while (b != '-' && (b < '0' || '9' < b)); if (b == '-') { ng = true; b = read(); } for (; true; b = read()) { if (b < '0' || '9' < b) return ng ? -ret : ret; else ret = ret * 10 + b - '0'; } } public int Integer() { return (isEof) ? int.MinValue : (int)Long(); } public double Double() { return double.Parse(Scan(), CultureInfo.InvariantCulture); } private T[] enumerate(int n, Func f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(); return a; } public char[] Char(int n) { return enumerate(n, Char); } public string[] Scan(int n) { return enumerate(n, Scan); } public double[] Double(int n) { return enumerate(n, Double); } public int[] Integer(int n) { return enumerate(n, Integer); } public long[] Long(int n) { return enumerate(n, Long); } } } #endregion #region BitOperation static public partial class BitOperation { static public int PopCount(long i) { i = i - ((i >> 1) & 0x5555555555555555); i = (i & 0x3333333333333333) + ((i >> 2) & 0x3333333333333333); return (int)(unchecked(((i + (i >> 4)) & 0xF0F0F0F0F0F0F0F) * 0x101010101010101) >> 56); } } #endregion