Ethash
Última edición: @MGETH(opens in a new tab), 6 de marzo de 2024
Ethash(opens in a new tab) es una versión modificada del algoritmo Dagger-Hashimoto. La prueba de trabajo de Ethash es memoria dura(opens in a new tab), lo que se pensaba que hacía que el algoritmo fuera resistente a ASIC. Finalmente se desarrollaron los ASIC de Ethash, pero la minería de GPU seguía siendo una opción viable hasta que se desactivó la prueba de trabajo. Ethash todavía se utiliza para minar otras monedas en otras redes de prueba de trabajo que no son de Ethereum.
¿Cómo funciona Ethash?
La dureza de la memoria se logra con un algoritmo de prueba de trabajo que requiere la elección de subconjuntos de un recurso fijo que depende del nonce y el encabezado del bloque. Este recurso (de unos cuantos gigabytes de tamaño) se llama DAG. El DAG se cambia cada 30.000 bloques, una ventana de ~125 horas llamada época (aproximadamente 5,2 días) y tarda un tiempo en generarse. Dado que el DAG solo depende de la altura del bloque, se puede generar previamente, pero si no es así, el cliente tiene que esperar hasta el final de este proceso para producir un bloque. Si los clientes no pregeneran y almacenan en caché los DAG con anticipación, la red puede experimentar un retraso masivo de bloqueo en cada transición de la época. Tenga en cuenta que no es necesario generar el DAG para verificar la prueba de trabajo, lo que esencialmente permite la verificación tanto con CPU baja como con una memoria pequeña.
La ruta general que toma el algoritmo es la siguiente:
- Existe una semilla que se puede calcular para cada bloque escaneando a través los encabezados de los bloques hasta ese punto.
- Desde la semilla, se puede calcular una memoria caché pseudoaleatoria de 16 MB. Los clientes ligeros almacenan la caché.
- Desde la caché, podemos generar un conjunto de datos de 1 GB, con la propiedad de que cada elemento del conjunto de datos dependa solo de un pequeño número de elementos de la caché. Los clientes completos y los mineros almacenan el conjunto de datos. El conjunto de datos crece linealmente con el tiempo.
- La minería implica extraer secciones aleatorias del conjunto de datos y agruparlas. La verificación se puede hacer con poca memoria utilizando la caché para regenerar las piezas específicas del conjunto de datos que necesita, por lo que solo tiene que almacenar la memoria caché.
El gran conjunto de datos se actualiza una vez cada 30000 bloques, por lo que la gran mayoría del esfuerzo de un minero será leer el conjunto de datos, no hacer cambios en él.
Definiciones
Utilizamos las siguientes definiciones:
1WORD_BYTES = 4 # bytes in word2DATASET_BYTES_INIT = 2**30 # bytes in dataset at genesis3DATASET_BYTES_GROWTH = 2**23 # dataset growth per epoch4CACHE_BYTES_INIT = 2**24 # bytes in cache at genesis5CACHE_BYTES_GROWTH = 2**17 # cache growth per epoch6CACHE_MULTIPLIER=1024 # Size of the DAG relative to the cache7EPOCH_LENGTH = 30000 # blocks per epoch8MIX_BYTES = 128 # width of mix9HASH_BYTES = 64 # hash length in bytes10DATASET_PARENTS = 256 # number of parents of each dataset element11CACHE_ROUNDS = 3 # number of rounds in cache production12ACCESSES = 64 # number of accesses in hashimoto loopMostrar todo
El uso de SHA3
El desarrollo de Ethereum coincidió con el desarrollo del estándar SHA3, y el proceso de estándares hizo un cambio tardío en el relleno del algoritmo hash finalizado, de modo que los hashes de Ethereum sha3_256 y sha3_512 no son hashes SHA3 estándar, sino una variante a la que se hace referencia a menudo referida a menudo como Keccak-256 y Keccak-512 en otros contextos. Vea la discusión, por ejemplo, aquí(opens in a new tab), aquí(opens in a new tab) o aquí(opens in a new tab).
Por favor, tenga esto en cuenta, ya que los hashes SHA3 se mencionan en la descripción del algoritmo a continuación.
Parámetros
Los parámetros de la memoria caché y del conjunto de datos de Ethash dependen del número de bloque. El tamaño de la memoria caché y el tamaño del conjunto de datos crecen linealmente; sin embargo, siempre tomamos el número primo más alto por debajo del umbral de crecimiento lineal para reducir el riesgo de regularidades accidentales que conducen a un comportamiento cíclico.
1def get_cache_size(block_number):2 sz = CACHE_BYTES_INIT + CACHE_BYTES_GROWTH * (block_number // EPOCH_LENGTH)3 sz -= HASH_BYTES4 while not isprime(sz / HASH_BYTES):5 sz -= 2 * HASH_BYTES6 return sz78def get_full_size(block_number):9 sz = DATASET_BYTES_INIT + DATASET_BYTES_GROWTH * (block_number // EPOCH_LENGTH)10 sz -= MIX_BYTES11 while not isprime(sz / MIX_BYTES):12 sz -= 2 * MIX_BYTES13 return szMostrar todoCopiar
En el apéndice se proporcionan tablas de valores de conjuntos de datos y tamaño de caché.
Generación de la memoria caché
A continuación, especifiquemos la función para producir una memoria caché:
1def mkcache(cache_size, seed):2 n = cache_size // HASH_BYTES34 # Sequentially produce the initial dataset5 o = [sha3_512(seed)]6 for i in range(1, n):7 o.append(sha3_512(o[-1]))89 # Use a low-round version of randmemohash10 for _ in range(CACHE_ROUNDS):11 for i in range(n):12 v = o[i][0] % n13 o[i] = sha3_512(map(xor, o[(i-1+n) % n], o[v]))1415 return oMostrar todoCopiar
El proceso de producción de una memoria caché implica primero llenar secuencialmente 32 MB de memoria, luego realizar dos pasadas del algoritmo RandMemoHash de Sergio Demian Lerner de Funciones de hashing para memoria dura extricta (2014)(opens in a new tab). El resultado es un conjunto de 524.288 valores de 64 bytes.
Función de agregación de datos
Utilizamos un algoritmo inspirado en el hash FNV(opens in a new tab) en algunos casos como un sustituto no asociativo de XOR. Tenga en cuenta que multiplicamos el número primo con la entrada completa de 32 bits, en contraste con la especificación FNV-1, que multiplica el número primo con un byte (octeto) a su vez.
1FNV_PRIME = 0x0100019323def fnv(v1, v2):4 return ((v1 * FNV_PRIME) ^ v2) % 2**32Copiar
Tenga en cuenta que incluso el papel amarillo especifica FNV como v1*(FNV_PRIME ^ v2), todas las implementaciones actuales utilizan consistentemente la definición anterior.
Cálculo completo del conjunto de datos
Cada elemento de 64 bytes en el conjunto de datos completo de 1 GB se calcula de la siguiente manera:
1def calc_dataset_item(cache, i):2 n = len(cache)3 r = HASH_BYTES // WORD_BYTES4 # initialize the mix5 mix = copy.copy(cache[i % n])6 mix[0] ^= i7 mix = sha3_512(mix)8 # fnv it with a lot of random cache nodes based on i9 for j in range(DATASET_PARENTS):10 cache_index = fnv(i ^ j, mix[j % r])11 mix = map(fnv, mix, cache[cache_index % n])12 return sha3_512(mix)Mostrar todoCopiar
Esencialmente, combinamos datos de 256 nodos de caché seleccionados pseudoleatoriamente y hash para calcular el nodo del conjunto de datos. A continuación, todo el conjunto de datos es generado por:
1def calc_dataset(full_size, cache):2 return [calc_dataset_item(cache, i) for i in range(full_size // HASH_BYTES)]Copiar
Bucle principal
Seguidamente, especificamos el bucle principal similar a Hashimoto, donde agregamos datos del conjunto de datos completo para producir nuestro valor final para un encabezado y nonce en particular. En el siguiente código, encabezado
representa el SHA3-256 hash de la representación RLP de un encabezado de bloque truncated, es decir, de un encabezado que excluye los campos mixHash y nonce. nonce
son los ocho bytes de un entero sin signo de 64 bits en orden «big-endian». Así que nonce[::-1]
es la representación «little-endian « de ocho bytes de ese valor:
1def hashimoto(header, nonce, full_size, dataset_lookup):2 n = full_size / HASH_BYTES3 w = MIX_BYTES // WORD_BYTES4 mixhashes = MIX_BYTES / HASH_BYTES5 # combine header+nonce into a 64 byte seed6 s = sha3_512(header + nonce[::-1])7 # start the mix with replicated s8 mix = []9 for _ in range(MIX_BYTES / HASH_BYTES):10 mix.extend(s)11 # mix in random dataset nodes12 for i in range(ACCESSES):13 p = fnv(i ^ s[0], mix[i % w]) % (n // mixhashes) * mixhashes14 newdata = []15 for j in range(MIX_BYTES / HASH_BYTES):16 newdata.extend(dataset_lookup(p + j))17 mix = map(fnv, mix, newdata)18 # compress mix19 cmix = []20 for i in range(0, len(mix), 4):21 cmix.append(fnv(fnv(fnv(mix[i], mix[i+1]), mix[i+2]), mix[i+3]))22 return {23 "mix digest": serialize_hash(cmix),24 "result": serialize_hash(sha3_256(s+cmix))25 }2627def hashimoto_light(full_size, cache, header, nonce):28 return hashimoto(header, nonce, full_size, lambda x: calc_dataset_item(cache, x))2930def hashimoto_full(full_size, dataset, header, nonce):31 return hashimoto(header, nonce, full_size, lambda x: dataset[x])Mostrar todoCopiar
Esencialmente, mantenemos una mezcla de 128 bytes de ancho, y recuperamos repetidamente de forma secuencial de 128 bytes del conjunto de datos completo y utilizamos la función FNV
para combinarlo con la mezcla. Se utilizan 128 bytes de acceso secuencial para que cada ronda del algoritmo siempre obtenga una página completa de la RAM, minimizando las faltas de búfer de traducción que los ASIC teóricamente podrían evitar.
Si el resultado de este algoritmo está por debajo del objetivo deseado, entonces el nonce es válido. Tenga en cuenta que la aplicación adicional de sha3_256
al final asegura que exista un nonce intermedio que se puede proporcionar para demostrar que se realizó al menos una pequeña cantidad de trabajo; esta rápida verificación externa de PoW se puede utilizar con fines anti-DDoS. También sirve para proporcionar una garantía estadística de que el resultado es un número imparcial de 256 bits.
Minería
El algoritmo de minería se define de la siguiente manera:
1def mine(full_size, dataset, header, difficulty):2 # zero-pad target to compare with hash on the same digit3 target = zpad(encode_int(2**256 // difficulty), 64)[::-1]4 from random import randint5 nonce = randint(0, 2**64)6 while hashimoto_full(full_size, dataset, header, nonce) > target:7 nonce = (nonce + 1) % 2**648 return nonceCopiar
Definición del hash de semilla
Para calcular el hash semilla que se usaría para minar en la parte superior de un bloque dado, utilizamos el siguiente algoritmo:
1 def get_seedhash(block):2 s = '\x00' * 323 for i in range(block.number // EPOCH_LENGTH):4 s = serialize_hash(sha3_256(s))5 return sCopiar
Tenga en cuenta que para una minería y verificación sin problemas, recomendamos precalcular futuros hashes semilla y conjuntos de datos en un hilo por separado.
Más información
¿Conoce un recurso comunitario que le ayudó? Editar esta página y agregarla!
Apéndice
El siguiente código debe anteponese si está interesado en ejecutar la especificación de Python anterior como código.
1import sha3, copy23# Assumes little endian bit ordering (same as Intel architectures)4def decode_int(s):5 return int(s[::-1].encode('hex'), 16) if s else 067def encode_int(s):8 a = "%x" % s9 return '' if s == 0 else ('0' * (len(a) % 2) + a).decode('hex')[::-1]1011def zpad(s, length):12 return s + '\x00' * max(0, length - len(s))1314def serialize_hash(h):15 return ''.join([zpad(encode_int(x), 4) for x in h])1617def deserialize_hash(h):18 return [decode_int(h[i:i+WORD_BYTES]) for i in range(0, len(h), WORD_BYTES)]1920def hash_words(h, sz, x):21 if isinstance(x, list):22 x = serialize_hash(x)23 y = h(x)24 return deserialize_hash(y)2526def serialize_cache(ds):27 return ''.join([serialize_hash(h) for h in ds])2829serialize_dataset = serialize_cache3031# sha3 hash function, outputs 64 bytes32def sha3_512(x):33 return hash_words(lambda v: sha3.sha3_512(v).digest(), 64, x)3435def sha3_256(x):36 return hash_words(lambda v: sha3.sha3_256(v).digest(), 32, x)3738def xor(a, b):39 return a ^ b4041def isprime(x):42 for i in range(2, int(x**0.5)):43 if x % i == 0:44 return False45 return TrueMostrar todoCopiar
Tamaños de datos
Las siguientes tablas de búsqueda proporcionan aproximadamente 2048 épocas tabuladas de tamaños de datos y tamaños de caché.
1def get_datasize(block_number):2 return data_sizes[block_number // EPOCH_LENGTH]34def get_cachesize(block_number):5 return cache_sizes[block_number // EPOCH_LENGTH]67data_sizes = [81073739904, 1082130304, 1090514816, 1098906752, 1107293056,91115684224, 1124070016, 1132461952, 1140849536, 1149232768,101157627776, 1166013824, 1174404736, 1182786944, 1191180416,111199568512, 1207958912, 1216345216, 1224732032, 1233124736,121241513344, 1249902464, 1258290304, 1266673792, 1275067264,131283453312, 1291844992, 1300234112, 1308619904, 1317010048,141325397376, 1333787776, 1342176128, 1350561664, 1358954368,151367339392, 1375731584, 1384118144, 1392507008, 1400897408,161409284736, 1417673344, 1426062464, 1434451072, 1442839168,171451229056, 1459615616, 1468006016, 1476394112, 1484782976,181493171584, 1501559168, 1509948032, 1518337664, 1526726528,191535114624, 1543503488, 1551892096, 1560278656, 1568669056,201577056384, 1585446272, 1593831296, 1602219392, 1610610304,211619000192, 1627386752, 1635773824, 1644164224, 1652555648,221660943488, 1669332608, 1677721216, 1686109312, 1694497664,231702886272, 1711274624, 1719661184, 1728047744, 1736434816,241744829056, 1753218944, 1761606272, 1769995904, 1778382464,251786772864, 1795157888, 1803550592, 1811937664, 1820327552,261828711552, 1837102976, 1845488768, 1853879936, 1862269312,271870656896, 1879048064, 1887431552, 1895825024, 1904212096,281912601216, 1920988544, 1929379456, 1937765504, 1946156672,291954543232, 1962932096, 1971321728, 1979707264, 1988093056,301996487552, 2004874624, 2013262208, 2021653888, 2030039936,312038430848, 2046819968, 2055208576, 2063596672, 2071981952,322080373632, 2088762752, 2097149056, 2105539712, 2113928576,332122315136, 2130700672, 2139092608, 2147483264, 2155872128,342164257664, 2172642176, 2181035392, 2189426048, 2197814912,352206203008, 2214587264, 2222979712, 2231367808, 2239758208,362248145024, 2256527744, 2264922752, 2273312128, 2281701248,372290086272, 2298476672, 2306867072, 2315251072, 2323639168,382332032128, 2340420224, 2348808064, 2357196416, 2365580416,392373966976, 2382363008, 2390748544, 2399139968, 2407530368,402415918976, 2424307328, 2432695424, 2441084288, 2449472384,412457861248, 2466247808, 2474637184, 2483026816, 2491414144,422499803776, 2508191872, 2516582272, 2524970368, 2533359232,432541743488, 2550134144, 2558525056, 2566913408, 2575301504,442583686528, 2592073856, 2600467328, 2608856192, 2617240448,452625631616, 2634022016, 2642407552, 2650796416, 2659188352,462667574912, 2675965312, 2684352896, 2692738688, 2701130624,472709518464, 2717907328, 2726293376, 2734685056, 2743073152,482751462016, 2759851648, 2768232832, 2776625536, 2785017728,492793401984, 2801794432, 2810182016, 2818571648, 2826959488,502835349376, 2843734144, 2852121472, 2860514432, 2868900992,512877286784, 2885676928, 2894069632, 2902451584, 2910843008,522919234688, 2927622784, 2936011648, 2944400768, 2952789376,532961177728, 2969565568, 2977951616, 2986338944, 2994731392,543003120256, 3011508352, 3019895936, 3028287104, 3036675968,553045063808, 3053452928, 3061837696, 3070228352, 3078615424,563087003776, 3095394944, 3103782272, 3112173184, 3120562048,573128944768, 3137339264, 3145725056, 3154109312, 3162505088,583170893184, 3179280256, 3187669376, 3196056704, 3204445568,593212836736, 3221224064, 3229612928, 3238002304, 3246391168,603254778496, 3263165824, 3271556224, 3279944576, 3288332416,613296719232, 3305110912, 3313500032, 3321887104, 3330273152,623338658944, 3347053184, 3355440512, 3363827072, 3372220288,633380608384, 3388997504, 3397384576, 3405774208, 3414163072,643422551936, 3430937984, 3439328384, 3447714176, 3456104576,653464493952, 3472883584, 3481268864, 3489655168, 3498048896,663506434432, 3514826368, 3523213952, 3531603584, 3539987072,673548380288, 3556763264, 3565157248, 3573545344, 3581934464,683590324096, 3598712704, 3607098752, 3615488384, 3623877248,693632265856, 3640646528, 3649043584, 3657430144, 3665821568,703674207872, 3682597504, 3690984832, 3699367808, 3707764352,713716152448, 3724541056, 3732925568, 3741318016, 3749706368,723758091136, 3766481536, 3774872704, 3783260032, 3791650432,733800036224, 3808427648, 3816815488, 3825204608, 3833592704,743841981568, 3850370432, 3858755968, 3867147904, 3875536256,753883920512, 3892313728, 3900702592, 3909087872, 3917478784,763925868416, 3934256512, 3942645376, 3951032192, 3959422336,773967809152, 3976200064, 3984588416, 3992974976, 4001363584,784009751168, 4018141312, 4026530432, 4034911616, 4043308928,794051695488, 4060084352, 4068472448, 4076862848, 4085249408,804093640576, 4102028416, 4110413696, 4118805632, 4127194496,814135583104, 4143971968, 4152360832, 4160746112, 4169135744,824177525888, 4185912704, 4194303616, 4202691968, 4211076736,834219463552, 4227855488, 4236246656, 4244633728, 4253022848,844261412224, 4269799808, 4278184832, 4286578048, 4294962304,854303349632, 4311743104, 4320130432, 4328521088, 4336909184,864345295488, 4353687424, 4362073472, 4370458496, 4378852736,874387238528, 4395630208, 4404019072, 4412407424, 4420790656,884429182848, 4437571456, 4445962112, 4454344064, 4462738048,894471119232, 4479516544, 4487904128, 4496289664, 4504682368,904513068416, 4521459584, 4529846144, 4538232704, 4546619776,914555010176, 4563402112, 4571790208, 4580174464, 4588567936,924596957056, 4605344896, 4613734016, 4622119808, 4630511488,934638898816, 4647287936, 4655675264, 4664065664, 4672451968,944680842624, 4689231488, 4697620352, 4706007424, 4714397056,954722786176, 4731173248, 4739562368, 4747951744, 4756340608,964764727936, 4773114496, 4781504384, 4789894784, 4798283648,974806667648, 4815059584, 4823449472, 4831835776, 4840226176,984848612224, 4857003392, 4865391488, 4873780096, 4882169728,994890557312, 4898946944, 4907333248, 4915722368, 4924110976,1004932499328, 4940889728, 4949276032, 4957666432, 4966054784,1014974438016, 4982831488, 4991221376, 4999607168, 5007998848,1025016386432, 5024763776, 5033164672, 5041544576, 5049941888,1035058329728, 5066717056, 5075107456, 5083494272, 5091883904,1045100273536, 5108662144, 5117048192, 5125436032, 5133827456,1055142215296, 5150605184, 5158993024, 5167382144, 5175769472,1065184157568, 5192543872, 5200936064, 5209324928, 5217711232,1075226102656, 5234490496, 5242877312, 5251263872, 5259654016,1085268040832, 5276434304, 5284819328, 5293209728, 5301598592,1095309986688, 5318374784, 5326764416, 5335151488, 5343542144,1105351929472, 5360319872, 5368706944, 5377096576, 5385484928,1115393871232, 5402263424, 5410650496, 5419040384, 5427426944,1125435816576, 5444205952, 5452594816, 5460981376, 5469367936,1135477760896, 5486148736, 5494536832, 5502925952, 5511315328,1145519703424, 5528089984, 5536481152, 5544869504, 5553256064,1155561645696, 5570032768, 5578423936, 5586811264, 5595193216,1165603585408, 5611972736, 5620366208, 5628750464, 5637143936,1175645528192, 5653921408, 5662310272, 5670694784, 5679082624,1185687474048, 5695864448, 5704251008, 5712641408, 5721030272,1195729416832, 5737806208, 5746194304, 5754583936, 5762969984,1205771358592, 5779748224, 5788137856, 5796527488, 5804911232,1215813300608, 5821692544, 5830082176, 5838468992, 5846855552,1225855247488, 5863636096, 5872024448, 5880411008, 5888799872,1235897186432, 5905576832, 5913966976, 5922352768, 5930744704,1245939132288, 5947522432, 5955911296, 5964299392, 5972688256,1255981074304, 5989465472, 5997851008, 6006241408, 6014627968,1266023015552, 6031408256, 6039796096, 6048185216, 6056574848,1276064963456, 6073351808, 6081736064, 6090128768, 6098517632,1286106906496, 6115289216, 6123680896, 6132070016, 6140459648,1296148849024, 6157237376, 6165624704, 6174009728, 6182403712,1306190792064, 6199176064, 6207569792, 6215952256, 6224345216,1316232732544, 6241124224, 6249510272, 6257899136, 6266287744,1326274676864, 6283065728, 6291454336, 6299843456, 6308232064,1336316620928, 6325006208, 6333395584, 6341784704, 6350174848,1346358562176, 6366951296, 6375337856, 6383729536, 6392119168,1356400504192, 6408895616, 6417283456, 6425673344, 6434059136,1366442444672, 6450837376, 6459223424, 6467613056, 6476004224,1376484393088, 6492781952, 6501170048, 6509555072, 6517947008,1386526336384, 6534725504, 6543112832, 6551500672, 6559888768,1396568278656, 6576662912, 6585055616, 6593443456, 6601834112,1406610219648, 6618610304, 6626999168, 6635385472, 6643777408,1416652164224, 6660552832, 6668941952, 6677330048, 6685719424,1426694107776, 6702493568, 6710882176, 6719274112, 6727662976,1436736052096, 6744437632, 6752825984, 6761213824, 6769604224,1446777993856, 6786383488, 6794770816, 6803158144, 6811549312,1456819937664, 6828326528, 6836706176, 6845101696, 6853491328,1466861880448, 6870269312, 6878655104, 6887046272, 6895433344,1476903822208, 6912212864, 6920596864, 6928988288, 6937377152,1486945764992, 6954149248, 6962544256, 6970928768, 6979317376,1496987709312, 6996093824, 7004487296, 7012875392, 7021258624,1507029652352, 7038038912, 7046427776, 7054818944, 7063207808,1517071595136, 7079980928, 7088372608, 7096759424, 7105149824,1527113536896, 7121928064, 7130315392, 7138699648, 7147092352,1537155479168, 7163865728, 7172249984, 7180648064, 7189036672,1547197424768, 7205810816, 7214196608, 7222589824, 7230975104,1557239367552, 7247755904, 7256145536, 7264533376, 7272921472,1567281308032, 7289694848, 7298088832, 7306471808, 7314864512,1577323253888, 7331643008, 7340029568, 7348419712, 7356808832,1587365196672, 7373585792, 7381973888, 7390362752, 7398750592,1597407138944, 7415528576, 7423915648, 7432302208, 7440690304,1607449080192, 7457472128, 7465860992, 7474249088, 7482635648,1617491023744, 7499412608, 7507803008, 7516192384, 7524579968,1627532967296, 7541358464, 7549745792, 7558134656, 7566524032,1637574912896, 7583300992, 7591690112, 7600075136, 7608466816,1647616854912, 7625244544, 7633629824, 7642020992, 7650410368,1657658794112, 7667187328, 7675574912, 7683961984, 7692349568,1667700739712, 7709130368, 7717519232, 7725905536, 7734295424,1677742683264, 7751069056, 7759457408, 7767849088, 7776238208,1687784626816, 7793014912, 7801405312, 7809792128, 7818179968,1697826571136, 7834957184, 7843347328, 7851732352, 7860124544,1707868512384, 7876902016, 7885287808, 7893679744, 7902067072,1717910455936, 7918844288, 7927230848, 7935622784, 7944009344,1727952400256, 7960786048, 7969176704, 7977565312, 7985953408,1737994339968, 8002730368, 8011119488, 8019508096, 8027896192,1748036285056, 8044674688, 8053062272, 8061448832, 8069838464,1758078227328, 8086616704, 8095006592, 8103393664, 8111783552,1768120171392, 8128560256, 8136949376, 8145336704, 8153726848,1778162114944, 8170503296, 8178891904, 8187280768, 8195669632,1788204058496, 8212444544, 8220834176, 8229222272, 8237612672,1798246000768, 8254389376, 8262775168, 8271167104, 8279553664,1808287944064, 8296333184, 8304715136, 8313108352, 8321497984,1818329885568, 8338274432, 8346663296, 8355052928, 8363441536,1828371828352, 8380217984, 8388606592, 8396996224, 8405384576,1838413772672, 8422161536, 8430549376, 8438939008, 8447326592,1848455715456, 8464104832, 8472492928, 8480882048, 8489270656,1858497659776, 8506045312, 8514434944, 8522823808, 8531208832,1868539602304, 8547990656, 8556378752, 8564768384, 8573154176,1878581542784, 8589933952, 8598322816, 8606705024, 8615099264,1888623487872, 8631876992, 8640264064, 8648653952, 8657040256,1898665430656, 8673820544, 8682209152, 8690592128, 8698977152,1908707374464, 8715763328, 8724151424, 8732540032, 8740928384,1918749315712, 8757704576, 8766089344, 8774480768, 8782871936,1928791260032, 8799645824, 8808034432, 8816426368, 8824812928,1938833199488, 8841591424, 8849976448, 8858366336, 8866757248,1948875147136, 8883532928, 8891923328, 8900306816, 8908700288,1958917088384, 8925478784, 8933867392, 8942250368, 8950644608,1968959032704, 8967420544, 8975809664, 8984197504, 8992584064,1979000976256, 9009362048, 9017752448, 9026141312, 9034530688,1989042917504, 9051307904, 9059694208, 9068084864, 9076471424,1999084861824, 9093250688, 9101638528, 9110027648, 9118416512,2009126803584, 9135188096, 9143581312, 9151969664, 9160356224,2019168747136, 9177134464, 9185525632, 9193910144, 9202302848,2029210690688, 9219079552, 9227465344, 9235854464, 9244244864,2039252633472, 9261021824, 9269411456, 9277799296, 9286188928,2049294574208, 9302965888, 9311351936, 9319740032, 9328131968,2059336516736, 9344907392, 9353296768, 9361685888, 9370074752,2069378463616, 9386849408, 9395239808, 9403629184, 9412016512,2079420405376, 9428795008, 9437181568, 9445570688, 9453960832,2089462346624, 9470738048, 9479121536, 9487515008, 9495903616,2099504289664, 9512678528, 9521067904, 9529456256, 9537843584,2109546233728, 9554621312, 9563011456, 9571398784, 9579788672,2119588178304, 9596567168, 9604954496, 9613343104, 9621732992,2129630121856, 9638508416, 9646898816, 9655283584, 9663675776,2139672061312, 9680449664, 9688840064, 9697230464, 9705617536,2149714003584, 9722393984, 9730772608, 9739172224, 9747561088,2159755945344, 9764338816, 9772726144, 9781116544, 9789503872,2169797892992, 9806282624, 9814670464, 9823056512, 9831439232,2179839833984, 9848224384, 9856613504, 9865000576, 9873391232,2189881772416, 9890162816, 9898556288, 9906940544, 9915333248,2199923721088, 9932108672, 9940496512, 9948888448, 9957276544,2209965666176, 9974048384, 9982441088, 9990830464, 9999219584,22110007602816, 10015996544, 10024385152, 10032774016, 10041163648,22210049548928, 10057940096, 10066329472, 10074717824, 10083105152,22310091495296, 10099878784, 10108272256, 10116660608, 10125049216,22410133437312, 10141825664, 10150213504, 10158601088, 10166991232,22510175378816, 10183766144, 10192157312, 10200545408, 10208935552,22610217322112, 10225712768, 10234099328, 10242489472, 10250876032,22710259264896, 10267656064, 10276042624, 10284429184, 10292820352,22810301209472, 10309598848, 10317987712, 10326375296, 10334763392,22910343153536, 10351541632, 10359930752, 10368318592, 10376707456,23010385096576, 10393484672, 10401867136, 10410262144, 10418647424,23110427039104, 10435425664, 10443810176, 10452203648, 10460589952,23210468982144, 10477369472, 10485759104, 10494147712, 10502533504,23310510923392, 10519313536, 10527702656, 10536091264, 10544478592,23410552867712, 10561255808, 10569642368, 10578032768, 10586423168,23510594805632, 10603200128, 10611588992, 10619976064, 10628361344,23610636754048, 10645143424, 10653531776, 10661920384, 10670307968,23710678696832, 10687086464, 10695475072, 10703863168, 10712246144,23810720639616, 10729026688, 10737414784, 10745806208, 10754190976,23910762581376, 10770971264, 10779356288, 10787747456, 10796135552,24010804525184, 10812915584, 10821301888, 10829692288, 10838078336,24110846469248, 10854858368, 10863247232, 10871631488, 10880023424,24210888412032, 10896799616, 10905188992, 10913574016, 10921964672,24310930352768, 10938742912, 10947132544, 10955518592, 10963909504,24410972298368, 10980687488, 10989074816, 10997462912, 11005851776,24511014241152, 11022627712, 11031017344, 11039403904, 11047793024,24611056184704, 11064570752, 11072960896, 11081343872, 11089737856,24711098128256, 11106514816, 11114904448, 11123293568, 11131680128,24811140065152, 11148458368, 11156845696, 11165236864, 11173624192,24911182013824, 11190402688, 11198790784, 11207179136, 11215568768,25011223957376, 11232345728, 11240734592, 11249122688, 11257511296,25111265899648, 11274285952, 11282675584, 11291065472, 11299452544,25211307842432, 11316231296, 11324616832, 11333009024, 11341395584,25311349782656, 11358172288, 11366560384, 11374950016, 11383339648,25411391721856, 11400117376, 11408504192, 11416893568, 11425283456,25511433671552, 11442061184, 11450444672, 11458837888, 11467226752,25611475611776, 11484003968, 11492392064, 11500780672, 11509169024,25711517550976, 11525944448, 11534335616, 11542724224, 11551111808,25811559500672, 11567890304, 11576277376, 11584667008, 11593056128,25911601443456, 11609830016, 11618221952, 11626607488, 11634995072,26011643387776, 11651775104, 11660161664, 11668552576, 11676940928,26111685330304, 11693718656, 11702106496, 11710496128, 11718882688,26211727273088, 11735660416, 11744050048, 11752437376, 11760824704,26311769216128, 11777604736, 11785991296, 11794381952, 11802770048,26411811157888, 11819548544, 11827932544, 11836324736, 11844713344,26511853100928, 11861486464, 11869879936, 11878268032, 11886656896,26611895044992, 11903433088, 11911822976, 11920210816, 11928600448,26711936987264, 11945375872, 11953761152, 11962151296, 11970543488,26811978928512, 11987320448, 11995708288, 12004095104, 12012486272,26912020875136, 12029255552, 12037652096, 12046039168, 12054429568,27012062813824, 12071206528, 12079594624, 12087983744, 12096371072,27112104759936, 12113147264, 12121534592, 12129924992, 12138314624,27212146703232, 12155091584, 12163481216, 12171864704, 12180255872,27312188643968, 12197034112, 12205424512, 12213811328, 12222199424,27412230590336, 12238977664, 12247365248, 12255755392, 12264143488,27512272531584, 12280920448, 12289309568, 12297694592, 12306086528,27612314475392, 12322865024, 12331253632, 12339640448, 12348029312,27712356418944, 12364805248, 12373196672, 12381580928, 12389969024,27812398357632, 12406750592, 12415138432, 12423527552, 12431916416,27912440304512, 12448692352, 12457081216, 12465467776, 12473859968,28012482245504, 12490636672, 12499025536, 12507411584, 12515801728,28112524190592, 12532577152, 12540966272, 12549354368, 12557743232,28212566129536, 12574523264, 12582911872, 12591299456, 12599688064,28312608074624, 12616463488, 12624845696, 12633239936, 12641631616,28412650019968, 12658407296, 12666795136, 12675183232, 12683574656,28512691960192, 12700350592, 12708740224, 12717128576, 12725515904,28612733906816, 12742295168, 12750680192, 12759071872, 12767460736,28712775848832, 12784236928, 12792626816, 12801014656, 12809404288,28812817789312, 12826181504, 12834568832, 12842954624, 12851345792,28912859732352, 12868122496, 12876512128, 12884901248, 12893289088,29012901672832, 12910067584, 12918455168, 12926842496, 12935232896,29112943620736, 12952009856, 12960396928, 12968786816, 12977176192,29212985563776, 12993951104, 13002341504, 13010730368, 13019115392,29313027506304, 13035895168, 13044272512, 13052673152, 13061062528,29413069446272, 13077838976, 13086227072, 13094613632, 13103000192,29513111393664, 13119782528, 13128157568, 13136559232, 13144945024,29613153329536, 13161724288, 13170111872, 13178502784, 13186884736,29713195279744, 13203667072, 13212057472, 13220445824, 13228832128,29813237221248, 13245610624, 13254000512, 13262388352, 13270777472,29913279166336, 13287553408, 13295943296, 13304331904, 13312719488,30013321108096, 13329494656, 13337885824, 13346274944, 13354663808,30113363051136, 13371439232, 13379825024, 13388210816, 13396605056,30213404995456, 13413380224, 13421771392, 13430159744, 13438546048,30313446937216, 13455326848, 13463708288, 13472103808, 13480492672,30413488875648, 13497269888, 13505657728, 13514045312, 13522435712,30513530824576, 13539210112, 13547599232, 13555989376, 13564379008,30613572766336, 13581154432, 13589544832, 13597932928, 13606320512,30713614710656, 13623097472, 13631477632, 13639874944, 13648264064,30813656652928, 13665041792, 13673430656, 13681818496, 13690207616,30913698595712, 13706982272, 13715373184, 13723762048, 13732150144,31013740536704, 13748926592, 13757316224, 13765700992, 13774090112,31113782477952, 13790869376, 13799259008, 13807647872, 13816036736,31213824425344, 13832814208, 13841202304, 13849591424, 13857978752,31313866368896, 13874754688, 13883145344, 13891533184, 13899919232,31413908311168, 13916692096, 13925085056, 13933473152, 13941866368,31513950253696, 13958643584, 13967032192, 13975417216, 13983807616,31613992197504, 14000582272, 14008973696, 14017363072, 14025752192,31714034137984, 14042528384, 14050918016, 14059301504, 14067691648,31814076083584, 14084470144, 14092852352, 14101249664, 14109635968,31914118024832, 14126407552, 14134804352, 14143188608, 14151577984,32014159968384, 14168357248, 14176741504, 14185127296, 14193521024,32114201911424, 14210301824, 14218685056, 14227067264, 14235467392,32214243855488, 14252243072, 14260630144, 14269021568, 14277409408,32314285799296, 14294187904, 14302571392, 14310961792, 14319353728,32414327738752, 14336130944, 14344518784, 14352906368, 14361296512,32514369685376, 14378071424, 14386462592, 14394848128, 14403230848,32614411627392, 14420013952, 14428402304, 14436793472, 14445181568,32714453569664, 14461959808, 14470347904, 14478737024, 14487122816,32814495511424, 14503901824, 14512291712, 14520677504, 14529064832,32914537456768, 14545845632, 14554234496, 14562618496, 14571011456,33014579398784, 14587789184, 14596172672, 14604564608, 14612953984,33114621341312, 14629724288, 14638120832, 14646503296, 14654897536,33214663284864, 14671675264, 14680061056, 14688447616, 14696835968,33314705228416, 14713616768, 14722003328, 14730392192, 14738784128,33414747172736, 14755561088, 14763947648, 14772336512, 14780725376,33514789110144, 14797499776, 14805892736, 14814276992, 14822670208,33614831056256, 14839444352, 14847836032, 14856222848, 14864612992,33714872997504, 14881388672, 14889775744, 14898165376, 14906553472,33814914944896, 14923329664, 14931721856, 14940109696, 14948497024,33914956887424, 14965276544, 14973663616, 14982053248, 14990439808,34014998830976, 15007216768, 15015605888, 15023995264, 15032385152,34115040768384, 15049154944, 15057549184, 15065939072, 15074328448,34215082715008, 15091104128, 15099493504, 15107879296, 15116269184,34315124659584, 15133042304, 15141431936, 15149824384, 15158214272,34415166602368, 15174991232, 15183378304, 15191760512, 15200154496,34515208542592, 15216931712, 15225323392, 15233708416, 15242098048,34615250489216, 15258875264, 15267265408, 15275654528, 15284043136,34715292431488, 15300819584, 15309208192, 15317596544, 15325986176,34815334374784, 15342763648, 15351151744, 15359540608, 15367929728,34915376318336, 15384706432, 15393092992, 15401481856, 15409869952,35015418258816, 15426649984, 15435037568, 15443425664, 15451815296,35115460203392, 15468589184, 15476979328, 15485369216, 15493755776,35215502146944, 15510534272, 15518924416, 15527311232, 15535699072,35315544089472, 15552478336, 15560866688, 15569254528, 15577642624,35415586031488, 15594419072, 15602809472, 15611199104, 15619586432,35515627975296, 15636364928, 15644753792, 15653141888, 15661529216,35615669918848, 15678305152, 15686696576, 15695083136, 15703474048,35715711861632, 15720251264, 15728636288, 15737027456, 15745417088,35815753804928, 15762194048, 15770582656, 15778971008, 15787358336,35915795747712, 15804132224, 15812523392, 15820909696, 15829300096,36015837691264, 15846071936, 15854466944, 15862855808, 15871244672,36115879634816, 15888020608, 15896409728, 15904799104, 15913185152,36215921577088, 15929966464, 15938354816, 15946743424, 15955129472,36315963519872, 15971907968, 15980296064, 15988684928, 15997073024,36416005460864, 16013851264, 16022241152, 16030629248, 16039012736,36516047406976, 16055794816, 16064181376, 16072571264, 16080957824,36616089346688, 16097737856, 16106125184, 16114514816, 16122904192,36716131292544, 16139678848, 16148066944, 16156453504, 16164839552,36816173236096, 16181623424, 16190012032, 16198401152, 16206790528,36916215177344, 16223567744, 16231956352, 16240344704, 16248731008,37016257117824, 16265504384, 16273898624, 16282281856, 16290668672,37116299064192, 16307449216, 16315842176, 16324230016, 16332613504,37216341006464, 16349394304, 16357783168, 16366172288, 16374561664,37316382951296, 16391337856, 16399726208, 16408116352, 16416505472,37416424892032, 16433282176, 16441668224, 16450058624, 16458448768,37516466836864, 16475224448, 16483613056, 16492001408, 16500391808,37616508779648, 16517166976, 16525555328, 16533944192, 16542330752,37716550719616, 16559110528, 16567497088, 16575888512, 16584274816,37816592665472, 16601051008, 16609442944, 16617832064, 16626218624,37916634607488, 16642996096, 16651385728, 16659773824, 16668163712,38016676552576, 16684938112, 16693328768, 16701718144, 16710095488,38116718492288, 16726883968, 16735272832, 16743661184, 16752049792,38216760436608, 16768827008, 16777214336, 16785599104, 16793992832,38316802381696, 16810768768, 16819151744, 16827542656, 16835934848,38416844323712, 16852711552, 16861101952, 16869489536, 16877876864,38516886265728, 16894653056, 16903044736, 16911431296, 16919821696,38616928207488, 16936592768, 16944987776, 16953375616, 16961763968,38716970152832, 16978540928, 16986929536, 16995319168, 17003704448,38817012096896, 17020481152, 17028870784, 17037262208, 17045649536,38917054039936, 17062426496, 17070814336, 17079205504, 17087592064,39017095978112, 17104369024, 17112759424, 17121147776, 17129536384,39117137926016, 17146314368, 17154700928, 17163089792, 17171480192,39217179864192, 17188256896, 17196644992, 17205033856, 17213423488,39317221811072, 17230198912, 17238588032, 17246976896, 17255360384,39417263754624, 17272143232, 17280530048, 17288918912, 17297309312,39517305696384, 17314085504, 17322475136, 17330863744, 17339252096,39617347640192, 17356026496, 17364413824, 17372796544, 17381190016,39717389583488, 17397972608, 17406360704, 17414748544, 17423135872,39817431527296, 17439915904, 17448303232, 17456691584, 17465081728,39917473468288, 17481857408, 17490247552, 17498635904, 17507022464,40017515409024, 17523801728, 17532189824, 17540577664, 17548966016,40117557353344, 17565741184, 17574131584, 17582519168, 17590907008,40217599296128, 17607687808, 17616076672, 17624455808, 17632852352,40317641238656, 17649630848, 17658018944, 17666403968, 17674794112,40417683178368, 17691573376, 17699962496, 17708350592, 17716739968,40517725126528, 17733517184, 17741898112, 17750293888, 17758673024,40617767070336, 17775458432, 17783848832, 17792236928, 17800625536,40717809012352, 17817402752, 17825785984, 17834178944, 17842563968,40817850955648, 17859344512, 17867732864, 17876119424, 17884511872,40917892900224, 17901287296, 17909677696, 17918058112, 17926451072,41017934843776, 17943230848, 17951609216, 17960008576, 17968397696,41117976784256, 17985175424, 17993564032, 18001952128, 18010339712,41218018728576, 18027116672, 18035503232, 18043894144, 18052283264,41318060672128, 18069056384, 18077449856, 18085837184, 18094225792,41418102613376, 18111004544, 18119388544, 18127781248, 18136170368,41518144558976, 18152947328, 18161336192, 18169724288, 18178108544,41618186498944, 18194886784, 18203275648, 18211666048, 18220048768,41718228444544, 18236833408, 18245220736]418419cache_sizes = [42016776896, 16907456, 17039296, 17170112, 17301056, 17432512, 17563072,42117693888, 17824192, 17955904, 18087488, 18218176, 18349504, 18481088,42218611392, 18742336, 18874304, 19004224, 19135936, 19267264, 19398208,42319529408, 19660096, 19791424, 19922752, 20053952, 20184896, 20315968,42420446912, 20576576, 20709184, 20840384, 20971072, 21102272, 21233216,42521364544, 21494848, 21626816, 21757376, 21887552, 22019392, 22151104,42622281536, 22412224, 22543936, 22675264, 22806464, 22935872, 23068096,42723198272, 23330752, 23459008, 23592512, 23723968, 23854912, 23986112,42824116672, 24247616, 24378688, 24509504, 24640832, 24772544, 24903488,42925034432, 25165376, 25296704, 25427392, 25558592, 25690048, 25820096,43025951936, 26081728, 26214208, 26345024, 26476096, 26606656, 26737472,43126869184, 26998208, 27131584, 27262528, 27393728, 27523904, 27655744,43227786688, 27917888, 28049344, 28179904, 28311488, 28441792, 28573504,43328700864, 28835648, 28966208, 29096768, 29228608, 29359808, 29490752,43429621824, 29752256, 29882816, 30014912, 30144448, 30273728, 30406976,43530538432, 30670784, 30799936, 30932672, 31063744, 31195072, 31325248,43631456192, 31588288, 31719232, 31850432, 31981504, 32110784, 32243392,43732372672, 32505664, 32636608, 32767808, 32897344, 33029824, 33160768,43833289664, 33423296, 33554368, 33683648, 33816512, 33947456, 34076992,43934208704, 34340032, 34471744, 34600256, 34734016, 34864576, 34993984,44035127104, 35258176, 35386688, 35518528, 35650624, 35782336, 35910976,44136044608, 36175808, 36305728, 36436672, 36568384, 36699968, 36830656,44236961984, 37093312, 37223488, 37355072, 37486528, 37617472, 37747904,44337879232, 38009792, 38141888, 38272448, 38403392, 38535104, 38660672,44438795584, 38925632, 39059264, 39190336, 39320768, 39452096, 39581632,44539713984, 39844928, 39974848, 40107968, 40238144, 40367168, 40500032,44640631744, 40762816, 40894144, 41023552, 41155904, 41286208, 41418304,44741547712, 41680448, 41811904, 41942848, 42073792, 42204992, 42334912,44842467008, 42597824, 42729152, 42860096, 42991552, 43122368, 43253696,44943382848, 43515712, 43646912, 43777088, 43907648, 44039104, 44170432,45044302144, 44433344, 44564288, 44694976, 44825152, 44956864, 45088448,45145219008, 45350464, 45481024, 45612608, 45744064, 45874496, 46006208,45246136768, 46267712, 46399424, 46529344, 46660672, 46791488, 46923328,45347053504, 47185856, 47316928, 47447872, 47579072, 47710144, 47839936,45447971648, 48103232, 48234176, 48365248, 48496192, 48627136, 48757312,45548889664, 49020736, 49149248, 49283008, 49413824, 49545152, 49675712,45649807168, 49938368, 50069056, 50200256, 50331584, 50462656, 50593472,45750724032, 50853952, 50986048, 51117632, 51248576, 51379904, 51510848,45851641792, 51773248, 51903296, 52035136, 52164032, 52297664, 52427968,45952557376, 52690112, 52821952, 52952896, 53081536, 53213504, 53344576,46053475776, 53608384, 53738816, 53870528, 54000832, 54131776, 54263744,46154394688, 54525248, 54655936, 54787904, 54918592, 55049152, 55181248,46255312064, 55442752, 55574336, 55705024, 55836224, 55967168, 56097856,46356228672, 56358592, 56490176, 56621888, 56753728, 56884928, 57015488,46457146816, 57278272, 57409216, 57540416, 57671104, 57802432, 57933632,46558064576, 58195264, 58326976, 58457408, 58588864, 58720192, 58849984,46658981696, 59113024, 59243456, 59375552, 59506624, 59637568, 59768512,46759897792, 60030016, 60161984, 60293056, 60423872, 60554432, 60683968,46860817216, 60948032, 61079488, 61209664, 61341376, 61471936, 61602752,46961733696, 61865792, 61996736, 62127808, 62259136, 62389568, 62520512,47062651584, 62781632, 62910784, 63045056, 63176128, 63307072, 63438656,47163569216, 63700928, 63831616, 63960896, 64093888, 64225088, 64355392,47264486976, 64617664, 64748608, 64879424, 65009216, 65142464, 65273792,47365402816, 65535424, 65666752, 65797696, 65927744, 66060224, 66191296,47466321344, 66453056, 66584384, 66715328, 66846656, 66977728, 67108672,47567239104, 67370432, 67501888, 67631296, 67763776, 67895104, 68026304,47668157248, 68287936, 68419264, 68548288, 68681408, 68811968, 68942912,47769074624, 69205568, 69337024, 69467584, 69599168, 69729472, 69861184,47869989824, 70122944, 70253888, 70385344, 70515904, 70647232, 70778816,47970907968, 71040832, 71171648, 71303104, 71432512, 71564992, 71695168,48071826368, 71958464, 72089536, 72219712, 72350144, 72482624, 72613568,48172744512, 72875584, 73006144, 73138112, 73268672, 73400128, 73530944,48273662272, 73793344, 73924544, 74055104, 74185792, 74316992, 74448832,48374579392, 74710976, 74841664, 74972864, 75102784, 75233344, 75364544,48475497024, 75627584, 75759296, 75890624, 76021696, 76152256, 76283072,48576414144, 76545856, 76676672, 76806976, 76937792, 77070016, 77200832,48677331392, 77462464, 77593664, 77725376, 77856448, 77987776, 78118336,48778249664, 78380992, 78511424, 78642496, 78773056, 78905152, 79033664,48879166656, 79297472, 79429568, 79560512, 79690816, 79822784, 79953472,48980084672, 80214208, 80346944, 80477632, 80608576, 80740288, 80870848,49081002048, 81133504, 81264448, 81395648, 81525952, 81657536, 81786304,49181919808, 82050112, 82181312, 82311616, 82443968, 82573376, 82705984,49282835776, 82967744, 83096768, 83230528, 83359552, 83491264, 83622464,49383753536, 83886016, 84015296, 84147776, 84277184, 84409792, 84540608,49484672064, 84803008, 84934336, 85065152, 85193792, 85326784, 85458496,49585589312, 85721024, 85851968, 85982656, 86112448, 86244416, 86370112,49686506688, 86637632, 86769344, 86900672, 87031744, 87162304, 87293632,49787424576, 87555392, 87687104, 87816896, 87947968, 88079168, 88211264,49888341824, 88473152, 88603712, 88735424, 88862912, 88996672, 89128384,49989259712, 89390272, 89521984, 89652544, 89783872, 89914816, 90045376,50090177088, 90307904, 90438848, 90569152, 90700096, 90832832, 90963776,50191093696, 91223744, 91356992, 91486784, 91618496, 91749824, 91880384,50292012224, 92143552, 92273344, 92405696, 92536768, 92666432, 92798912,50392926016, 93060544, 93192128, 93322816, 93453632, 93583936, 93715136,50493845056, 93977792, 94109504, 94240448, 94371776, 94501184, 94632896,50594764224, 94895552, 95023424, 95158208, 95287744, 95420224, 95550016,50695681216, 95811904, 95943872, 96075328, 96203584, 96337856, 96468544,50796599744, 96731072, 96860992, 96992576, 97124288, 97254848, 97385536,50897517248, 97647808, 97779392, 97910464, 98041408, 98172608, 98303168,50998434496, 98565568, 98696768, 98827328, 98958784, 99089728, 99220928,51099352384, 99482816, 99614272, 99745472, 99876416, 100007104,511100138048, 100267072, 100401088, 100529984, 100662592, 100791872,512100925248, 101056064, 101187392, 101317952, 101449408, 101580608,513101711296, 101841728, 101973824, 102104896, 102235712, 102366016,514102498112, 102628672, 102760384, 102890432, 103021888, 103153472,515103284032, 103415744, 103545152, 103677248, 103808576, 103939648,516104070976, 104201792, 104332736, 104462528, 104594752, 104725952,517104854592, 104988608, 105118912, 105247808, 105381184, 105511232,518105643072, 105774784, 105903296, 106037056, 106167872, 106298944,519106429504, 106561472, 106691392, 106822592, 106954304, 107085376,520107216576, 107346368, 107478464, 107609792, 107739712, 107872192,521108003136, 108131392, 108265408, 108396224, 108527168, 108657344,522108789568, 108920384, 109049792, 109182272, 109312576, 109444928,523109572928, 109706944, 109837888, 109969088, 110099648, 110230976,524110362432, 110492992, 110624704, 110755264, 110886208, 111017408,525111148864, 111279296, 111410752, 111541952, 111673024, 111803456,526111933632, 112066496, 112196416, 112328512, 112457792, 112590784,527112715968, 112852672, 112983616, 113114944, 113244224, 113376448,528113505472, 113639104, 113770304, 113901376, 114031552, 114163264,529114294592, 114425536, 114556864, 114687424, 114818624, 114948544,530115080512, 115212224, 115343296, 115473472, 115605184, 115736128,531115867072, 115997248, 116128576, 116260288, 116391488, 116522944,532116652992, 116784704, 116915648, 117046208, 117178304, 117308608,533117440192, 117569728, 117701824, 117833024, 117964096, 118094656,534118225984, 118357312, 118489024, 118617536, 118749632, 118882112,535119012416, 119144384, 119275328, 119406016, 119537344, 119668672,536119798464, 119928896, 120061376, 120192832, 120321728, 120454336,537120584512, 120716608, 120848192, 120979136, 121109056, 121241408,538121372352, 121502912, 121634752, 121764416, 121895744, 122027072,539122157632, 122289088, 122421184, 122550592, 122682944, 122813888,540122945344, 123075776, 123207488, 123338048, 123468736, 123600704,541123731264, 123861952, 123993664, 124124608, 124256192, 124386368,542124518208, 124649024, 124778048, 124911296, 125041088, 125173696,543125303744, 125432896, 125566912, 125696576, 125829056, 125958592,544126090304, 126221248, 126352832, 126483776, 126615232, 126746432,545126876608, 127008704, 127139392, 127270336, 127401152, 127532224,546127663552, 127794752, 127925696, 128055232, 128188096, 128319424,547128449856, 128581312, 128712256, 128843584, 128973632, 129103808,548129236288, 129365696, 129498944, 129629888, 129760832, 129892288,549130023104, 130154048, 130283968, 130416448, 130547008, 130678336,550130807616, 130939456, 131071552, 131202112, 131331776, 131464384,551131594048, 131727296, 131858368, 131987392, 132120256, 132250816,552132382528, 132513728, 132644672, 132774976, 132905792, 133038016,553133168832, 133299392, 133429312, 133562048, 133692992, 133823296,554133954624, 134086336, 134217152, 134348608, 134479808, 134607296,555134741056, 134872384, 135002944, 135134144, 135265472, 135396544,556135527872, 135659072, 135787712, 135921472, 136052416, 136182848,557136313792, 136444864, 136576448, 136707904, 136837952, 136970048,558137099584, 137232064, 137363392, 137494208, 137625536, 137755712,559137887424, 138018368, 138149824, 138280256, 138411584, 138539584,560138672832, 138804928, 138936128, 139066688, 139196864, 139328704,561139460032, 139590208, 139721024, 139852864, 139984576, 140115776,562140245696, 140376512, 140508352, 140640064, 140769856, 140902336,563141032768, 141162688, 141294016, 141426496, 141556544, 141687488,564141819584, 141949888, 142080448, 142212544, 142342336, 142474432,565142606144, 142736192, 142868288, 142997824, 143129408, 143258944,566143392448, 143523136, 143653696, 143785024, 143916992, 144045632,567144177856, 144309184, 144440768, 144570688, 144701888, 144832448,568144965056, 145096384, 145227584, 145358656, 145489856, 145620928,569145751488, 145883072, 146011456, 146144704, 146275264, 146407232,570146538176, 146668736, 146800448, 146931392, 147062336, 147193664,571147324224, 147455936, 147586624, 147717056, 147848768, 147979456,572148110784, 148242368, 148373312, 148503232, 148635584, 148766144,573148897088, 149028416, 149159488, 149290688, 149420224, 149551552,574149683136, 149814976, 149943616, 150076352, 150208064, 150338624,575150470464, 150600256, 150732224, 150862784, 150993088, 151125952,576151254976, 151388096, 151519168, 151649728, 151778752, 151911104,577152042944, 152174144, 152304704, 152435648, 152567488, 152698816,578152828992, 152960576, 153091648, 153222976, 153353792, 153484096,579153616192, 153747008, 153878336, 154008256, 154139968, 154270912,580154402624, 154533824, 154663616, 154795712, 154926272, 155057984,581155188928, 155319872, 155450816, 155580608, 155712064, 155843392,582155971136, 156106688, 156237376, 156367424, 156499264, 156630976,583156761536, 156892352, 157024064, 157155008, 157284416, 157415872,584157545536, 157677248, 157810496, 157938112, 158071744, 158203328,585158334656, 158464832, 158596288, 158727616, 158858048, 158988992,586159121216, 159252416, 159381568, 159513152, 159645632, 159776192,587159906496, 160038464, 160169536, 160300352, 160430656, 160563008,588160693952, 160822208, 160956352, 161086784, 161217344, 161349184,589161480512, 161611456, 161742272, 161873216, 162002752, 162135872,590162266432, 162397888, 162529216, 162660032, 162790976, 162922048,591163052096, 163184576, 163314752, 163446592, 163577408, 163707968,592163839296, 163969984, 164100928, 164233024, 164364224, 164494912,593164625856, 164756672, 164887616, 165019072, 165150016, 165280064,594165412672, 165543104, 165674944, 165805888, 165936832, 166067648,595166198336, 166330048, 166461248, 166591552, 166722496, 166854208,596166985408, 167116736, 167246656, 167378368, 167508416, 167641024,597167771584, 167903168, 168034112, 168164032, 168295744, 168427456,598168557632, 168688448, 168819136, 168951616, 169082176, 169213504,599169344832, 169475648, 169605952, 169738048, 169866304, 169999552,600170131264, 170262464, 170393536, 170524352, 170655424, 170782016,601170917696, 171048896, 171179072, 171310784, 171439936, 171573184,602171702976, 171835072, 171966272, 172097216, 172228288, 172359232,603172489664, 172621376, 172747712, 172883264, 173014208, 173144512,604173275072, 173407424, 173539136, 173669696, 173800768, 173931712,605174063424, 174193472, 174325696, 174455744, 174586816, 174718912,606174849728, 174977728, 175109696, 175242688, 175374272, 175504832,607175636288, 175765696, 175898432, 176028992, 176159936, 176291264,608176422592, 176552512, 176684864, 176815424, 176946496, 177076544,609177209152, 177340096, 177470528, 177600704, 177731648, 177864256,610177994816, 178126528, 178257472, 178387648, 178518464, 178650176,611178781888, 178912064, 179044288, 179174848, 179305024, 179436736,612179568448, 179698496, 179830208, 179960512, 180092608, 180223808,613180354752, 180485696, 180617152, 180748096, 180877504, 181009984,614181139264, 181272512, 181402688, 181532608, 181663168, 181795136,615181926592, 182057536, 182190016, 182320192, 182451904, 182582336,616182713792, 182843072, 182976064, 183107264, 183237056, 183368384,617183494848, 183631424, 183762752, 183893824, 184024768, 184154816,618184286656, 184417984, 184548928, 184680128, 184810816, 184941248,619185072704, 185203904, 185335616, 185465408, 185596352, 185727296,620185859904, 185989696, 186121664, 186252992, 186383552, 186514112,621186645952, 186777152, 186907328, 187037504, 187170112, 187301824,622187429184, 187562048, 187693504, 187825472, 187957184, 188087104,623188218304, 188349376, 188481344, 188609728, 188743616, 188874304,624189005248, 189136448, 189265088, 189396544, 189528128, 189660992,625189791936, 189923264, 190054208, 190182848, 190315072, 190447424,626190577984, 190709312, 190840768, 190971328, 191102656, 191233472,627191364032, 191495872, 191626816, 191758016, 191888192, 192020288,628192148928, 192282176, 192413504, 192542528, 192674752, 192805952,629192937792, 193068608, 193198912, 193330496, 193462208, 193592384,630193723456, 193854272, 193985984, 194116672, 194247232, 194379712,631194508352, 194641856, 194772544, 194900672, 195035072, 195166016,632195296704, 195428032, 195558592, 195690304, 195818176, 195952576,633196083392, 196214336, 196345792, 196476736, 196607552, 196739008,634196869952, 197000768, 197130688, 197262784, 197394368, 197523904,635197656384, 197787584, 197916608, 198049472, 198180544, 198310208,636198442432, 198573632, 198705088, 198834368, 198967232, 199097792,637199228352, 199360192, 199491392, 199621696, 199751744, 199883968,638200014016, 200146624, 200276672, 200408128, 200540096, 200671168,639200801984, 200933312, 201062464, 201194944, 201326144, 201457472,640201588544, 201719744, 201850816, 201981632, 202111552, 202244032,641202374464, 202505152, 202636352, 202767808, 202898368, 203030336,642203159872, 203292608, 203423296, 203553472, 203685824, 203816896,643203947712, 204078272, 204208192, 204341056, 204472256, 204603328,644204733888, 204864448, 204996544, 205125568, 205258304, 205388864,645205517632, 205650112, 205782208, 205913536, 206044736, 206176192,646206307008, 206434496, 206569024, 206700224, 206831168, 206961856,647207093056, 207223616, 207355328, 207486784, 207616832, 207749056,648207879104, 208010048, 208141888, 208273216, 208404032, 208534336,649208666048, 208796864, 208927424, 209059264, 209189824, 209321792,650209451584, 209582656, 209715136, 209845568, 209976896, 210106432,651210239296, 210370112, 210501568, 210630976, 210763712, 210894272,652211024832, 211156672, 211287616, 211418176, 211549376, 211679296,653211812032, 211942592, 212074432, 212204864, 212334016, 212467648,654212597824, 212727616, 212860352, 212991424, 213120832, 213253952,655213385024, 213515584, 213645632, 213777728, 213909184, 214040128,656214170688, 214302656, 214433728, 214564544, 214695232, 214826048,657214956992, 215089088, 215219776, 215350592, 215482304, 215613248,658215743552, 215874752, 216005312, 216137024, 216267328, 216399296,659216530752, 216661696, 216790592, 216923968, 217054528, 217183168,660217316672, 217448128, 217579072, 217709504, 217838912, 217972672,661218102848, 218233024, 218364736, 218496832, 218627776, 218759104,662218888896, 219021248, 219151936, 219281728, 219413056, 219545024,663219675968, 219807296, 219938624, 220069312, 220200128, 220331456,664220461632, 220592704, 220725184, 220855744, 220987072, 221117888,665221249216, 221378368, 221510336, 221642048, 221772736, 221904832,666222031808, 222166976, 222297536, 222428992, 222559936, 222690368,667222820672, 222953152, 223083968, 223213376, 223345984, 223476928,668223608512, 223738688, 223869376, 224001472, 224132672, 224262848,669224394944, 224524864, 224657344, 224788288, 224919488, 225050432,670225181504, 225312704, 225443776, 225574592, 225704768, 225834176,671225966784, 226097216, 226229824, 226360384, 226491712, 226623424,672226754368, 226885312, 227015104, 227147456, 227278528, 227409472,673227539904, 227669696, 227802944, 227932352, 228065216, 228196288,674228326464, 228457792, 228588736, 228720064, 228850112, 228981056,675229113152, 229243328, 229375936, 229505344, 229636928, 229769152,676229894976, 230030272, 230162368, 230292416, 230424512, 230553152,677230684864, 230816704, 230948416, 231079616, 231210944, 231342016,678231472448, 231603776, 231733952, 231866176, 231996736, 232127296,679232259392, 232388672, 232521664, 232652608, 232782272, 232914496,680233043904, 233175616, 233306816, 233438528, 233569984, 233699776,681233830592, 233962688, 234092224, 234221888, 234353984, 234485312,682234618304, 234749888, 234880832, 235011776, 235142464, 235274048,683235403456, 235535936, 235667392, 235797568, 235928768, 236057152,684236190272, 236322752, 236453312, 236583616, 236715712, 236846528,685236976448, 237108544, 237239104, 237371072, 237501632, 237630784,686237764416, 237895232, 238026688, 238157632, 238286912, 238419392,687238548032, 238681024, 238812608, 238941632, 239075008, 239206336,688239335232, 239466944, 239599168, 239730496, 239861312, 239992384,689240122816, 240254656, 240385856, 240516928, 240647872, 240779072,690240909632, 241040704, 241171904, 241302848, 241433408, 241565248,691241696192, 241825984, 241958848, 242088256, 242220224, 242352064,692242481856, 242611648, 242744896, 242876224, 243005632, 243138496,693243268672, 243400384, 243531712, 243662656, 243793856, 243924544,694244054592, 244187072, 244316608, 244448704, 244580032, 244710976,695244841536, 244972864, 245104448, 245233984, 245365312, 245497792,696245628736, 245759936, 245889856, 246021056, 246152512, 246284224,697246415168, 246545344, 246675904, 246808384, 246939584, 247070144,698247199552, 247331648, 247463872, 247593536, 247726016, 247857088,699247987648, 248116928, 248249536, 248380736, 248512064, 248643008,700248773312, 248901056, 249036608, 249167552, 249298624, 249429184,701249560512, 249692096, 249822784, 249954112, 250085312, 250215488,702250345792, 250478528, 250608704, 250739264, 250870976, 251002816,703251133632, 251263552, 251395136, 251523904, 251657792, 251789248,704251919424, 252051392, 252182464, 252313408, 252444224, 252575552,705252706624, 252836032, 252968512, 253099712, 253227584, 253361728,706253493056, 253623488, 253754432, 253885504, 254017216, 254148032,707254279488, 254410432, 254541376, 254672576, 254803264, 254933824,708255065792, 255196736, 255326528, 255458752, 255589952, 255721408,709255851072, 255983296, 256114624, 256244416, 256374208, 256507712,710256636096, 256768832, 256900544, 257031616, 257162176, 257294272,711257424448, 257555776, 257686976, 257818432, 257949632, 258079552,712258211136, 258342464, 258473408, 258603712, 258734656, 258867008,713258996544, 259127744, 259260224, 259391296, 259522112, 259651904,714259784384, 259915328, 260045888, 260175424, 260308544, 260438336,715260570944, 260700992, 260832448, 260963776, 261092672, 261226304,716261356864, 261487936, 261619648, 261750592, 261879872, 262011968,717262143424, 262274752, 262404416, 262537024, 262667968, 262799296,718262928704, 263061184, 263191744, 263322944, 263454656, 263585216,719263716672, 263847872, 263978944, 264108608, 264241088, 264371648,720264501184, 264632768, 264764096, 264895936, 265024576, 265158464,721265287488, 265418432, 265550528, 265681216, 265813312, 265943488,722266075968, 266206144, 266337728, 266468032, 266600384, 266731072,723266862272, 266993344, 267124288, 267255616, 267386432, 267516992,724267648704, 267777728, 267910592, 268040512, 268172096, 268302784,725268435264, 268566208, 268696256, 268828096, 268959296, 269090368,726269221312, 269352256, 269482688, 269614784, 269745856, 269876416,727270007616, 270139328, 270270272, 270401216, 270531904, 270663616,728270791744, 270924736, 271056832, 271186112, 271317184, 271449536,729271580992, 271711936, 271843136, 271973056, 272105408, 272236352,730272367296, 272498368, 272629568, 272759488, 272891456, 273022784,731273153856, 273284672, 273415616, 273547072, 273677632, 273808448,732273937088, 274071488, 274200896, 274332992, 274463296, 274595392,733274726208, 274857536, 274988992, 275118656, 275250496, 275382208,734275513024, 275643968, 275775296, 275906368, 276037184, 276167872,735276297664, 276429376, 276560576, 276692672, 276822976, 276955072,736277085632, 277216832, 277347008, 277478848, 277609664, 277740992,737277868608, 278002624, 278134336, 278265536, 278395328, 278526784,738278657728, 278789824, 278921152, 279052096, 279182912, 279313088,739279443776, 279576256, 279706048, 279838528, 279969728, 280099648,740280230976, 280361408, 280493632, 280622528, 280755392, 280887104,741281018176, 281147968, 281278912, 281411392, 281542592, 281673152,742281803712, 281935552, 282066496, 282197312, 282329024, 282458816,743282590272, 282720832, 282853184, 282983744, 283115072, 283246144,744283377344, 283508416, 283639744, 283770304, 283901504, 284032576,745284163136, 284294848, 284426176, 284556992, 284687296, 284819264,746284950208, 285081536]Mostrar todoCopiar