Ethash

Ethash був алгоритмом майнінгу Ethereum на основі підтвердження роботи. Наразі підтвердження роботи повністю вимкнено, а Ethereum захищено за допомогою доказу частки. Дізнайтеся більше про The Merge, доказ частки та стейкінг. Ця сторінка лише для історичного інтересу!

Ethash — це модифікована версія алгоритму Dagger-Hashimoto. Підтвердження роботи Ethash є вимогливим до пам’ятіopens in a new tab, що, як вважалося, робить алгоритм стійким до ASIC. Зрештою були розроблені ASIC для Ethash, але майнінг на графічних процесорах (GPU) залишався життєздатним варіантом, доки не було вимкнено підтвердження роботи. Ethash все ще використовується для майнінгу інших монет в інших мережах із підтвердженням роботи, не пов’язаних з Ethereum.

Як працює Ethash?

Потужність пам'яті досягається за допомогою алгоритму підтвердження роботи, який вимагає вибору підмножин фіксованого ресурсу залежно від одноразового заголовка і блоку. Цей ресурс (розміром у кілька гігабайт) називається DAG. DAG змінюється кожні 30 000 блоків — вікно тривалістю ~125 годин, яке називається епохою (приблизно 5,2 дня), і генерується протягом певного часу. Оскільки DAG залежить лише від висоти блоку, його можна попередньо згенерувати, але якщо ні, клієнту потрібно дочекатися завершення цього процесу, щоб створити блок. Якщо клієнти не генерують і не кешують DAG заздалегідь, мережа може відчувати велику затримку блоку під час кожної зміни епохи. Зауважте, що DAG не потрібно створювати для перевірки підтвердження роботи, що, по суті, дозволяє проводити перевірку як із низьким рівнем ЦП, так і з невеликою пам’яттю.

Загальний маршрут, який використовує алгоритм, такий:

Існує початкове значення, яке можна обчислити для кожного блоку шляхом сканування заголовків блоків до цього моменту.
З початкового значення можна обчислити псевдовипадковий кеш розміром 16 МБ. Легкі клієнти зберігають кеш.
З кешу ми можемо згенерувати набір даних розміром 1 ГБ з тією властивістю, що кожен елемент у наборі даних залежить лише від невеликої кількості елементів із кешу. Повні клієнти та майнери зберігають набір даних. Набір даних лінійно зростає з часом.
Майнінг включає захоплення випадкових фрагментів набору даних і їх хешування разом. Перевірку можна виконати при малому обсязі пам’яті, використовуючи кеш для регенерації певних частин набору даних, які вам потрібні, тому вам потрібно лише зберігати кеш.

Великий набір даних оновлюється раз на кожні 30 000 блоків, тому переважна більшість зусиль майнера буде направлена на зчитування набору даних, а не на внесення в нього зміни.

Визначення

Ми використовуємо такі визначення:

1WORD_BYTES = 4                    # bytes in word
2DATASET_BYTES_INIT = 2**30        # bytes in dataset at genesis
3DATASET_BYTES_GROWTH = 2**23      # dataset growth per epoch
4CACHE_BYTES_INIT = 2**24          # bytes in cache at genesis
5CACHE_BYTES_GROWTH = 2**17        # cache growth per epoch
6CACHE_MULTIPLIER=1024             # Size of the DAG relative to the cache
7EPOCH_LENGTH = 30000              # blocks per epoch
8MIX_BYTES = 128                   # width of mix
9HASH_BYTES = 64                   # hash length in bytes
10DATASET_PARENTS = 256             # number of parents of each dataset element
11CACHE_ROUNDS = 3                  # number of rounds in cache production
12ACCESSES = 64                     # number of accesses in hashimoto loop
Показати все

Використання SHA3

Розробка Ethereum збіглася в часі з розробкою стандарту SHA3, і в процесі стандартизації було внесено пізню зміну в доповнення фіналізованого хеш-алгоритму, тому хеші Ethereum "sha3_256" і "sha3_512" не є стандартними хешами sha3, а варіантом, який в інших контекстах часто називають "Keccak-256" і "Keccak-512". Див. обговорення, напр., тутopens in a new tab, тутopens in a new tab або тутopens in a new tab.

Будь ласка, майте це на увазі, оскільки хеші "sha3" згадуються в описі алгоритму нижче.

Параметри

Параметри кешу та набору даних Ethash залежать від номера блоку. Розмір кешу та розмір набору даних зростають лінійно; однак ми завжди беремо найбільше просте число, що є меншим за лінійно зростаючий поріг, щоб зменшити ризик випадкових закономірностей, що призводять до циклічної поведінки.

1def get_cache_size(block_number):
2    sz = CACHE_BYTES_INIT + CACHE_BYTES_GROWTH * (block_number // EPOCH_LENGTH)
3    sz -= HASH_BYTES
4    while not isprime(sz / HASH_BYTES):
5        sz -= 2 * HASH_BYTES
6    return sz
7
8def get_full_size(block_number):
9    sz = DATASET_BYTES_INIT + DATASET_BYTES_GROWTH * (block_number // EPOCH_LENGTH)
10    sz -= MIX_BYTES
11    while not isprime(sz / MIX_BYTES):
12        sz -= 2 * MIX_BYTES
13    return sz
Показати все

Таблиці значень розміру набору даних і розміру кешу наведено в додатку.

Генерація кешу

Тепер ми визначимо функцію для створення кешу:

1def mkcache(cache_size, seed):
2    n = cache_size // HASH_BYTES
3
4    # Sequentially produce the initial dataset
5    o = [sha3_512(seed)]
6    for i in range(1, n):
7        o.append(sha3_512(o[-1]))
8
9    # Use a low-round version of randmemohash
10    for _ in range(CACHE_ROUNDS):
11        for i in range(n):
12            v = o[i][0] % n
13            o[i] = sha3_512(map(xor, o[(i-1+n) % n], o[v]))
14
15    return o
Показати все

Процес створення кешу передбачає спочатку послідовне заповнення 32 МБ пам’яті, а потім виконання двох проходів алгоритму RandMemoHash Серхіо Деміана Лернера з Strict Memory Hard Hashing Functions (2014)opens in a new tab. Результатом є набір з 524 288 64-байтних значень.

Функція агрегації даних

У деяких випадках ми використовуємо алгоритм, натхненний FNV-хешемopens in a new tab, як неасоціативний замінник XOR. Зауважте, що ми множимо просте число на повне 32-бітне вхідне значення, на відміну від специфікації FNV-1, яка по черзі множить просте число на один байт (октет).

1FNV_PRIME = 0x01000193
2
3def fnv(v1, v2):
4    return ((v1 * FNV_PRIME) ^ v2) % 2**32

Зверніть увагу, що, хоча в Жовтій книзі fnv вказано як v1*(FNV_PRIME ^ v2), усі поточні реалізації послідовно використовують наведене вище визначення.

Розрахунок повного набору даних

Кожен 64-байтний елемент у повному наборі даних об'ємом 1 ГБ обчислюється таким чином:

1def calc_dataset_item(cache, i):
2    n = len(cache)
3    r = HASH_BYTES // WORD_BYTES
4    # initialize the mix
5    mix = copy.copy(cache[i % n])
6    mix[0] ^= i
7    mix = sha3_512(mix)
8    # fnv it with a lot of random cache nodes based on i
9    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)
Показати все

По суті, ми об'єднуємо дані з 256 псевдовипадково вибраних вузлів кешу та хешуємо їх, щоб обчислити вузол набору даних. Потім увесь набір даних генерується за допомогою:

1def calc_dataset(full_size, cache):
2    return [calc_dataset_item(cache, i) for i in range(full_size // HASH_BYTES)]

Основний цикл

Тепер ми визначимо основний цикл, подібний до "hashimoto", у якому ми агрегуємо дані з повного набору даних, щоб отримати наше кінцеве значення для певного заголовка та nonce. У наведеному нижче коді header представляє хеш SHA3-256 RLP-представлення скороченого заголовка блоку, тобто заголовка, що не містить полів mixHash і nonce. nonce — це вісім байтів 64-бітного беззнакового цілого числа в порядку від старшого до молодшого. Отже, nonce[::-1] — це восьмибайтове представлення цього значення в порядку від молодшого до старшого:

1def hashimoto(header, nonce, full_size, dataset_lookup):
2    n = full_size / HASH_BYTES
3    w = MIX_BYTES // WORD_BYTES
4    mixhashes = MIX_BYTES / HASH_BYTES
5    # combine header+nonce into a 64 byte seed
6    s = sha3_512(header + nonce[::-1])
7    # start the mix with replicated s
8    mix = []
9    for _ in range(MIX_BYTES / HASH_BYTES):
10        mix.extend(s)
11    # mix in random dataset nodes
12    for i in range(ACCESSES):
13        p = fnv(i ^ s[0], mix[i % w]) % (n // mixhashes) * mixhashes
14        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 mix
19    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    }
26
27def hashimoto_light(full_size, cache, header, nonce):
28    return hashimoto(header, nonce, full_size, lambda x: calc_dataset_item(cache, x))
29
30def hashimoto_full(full_size, dataset, header, nonce):
31    return hashimoto(header, nonce, full_size, lambda x: dataset[x])
Показати все

По суті, ми підтримуємо "суміш" шириною 128 байтів і багаторазово послідовно вибираємо 128 байтів із повного набору даних та використовуємо функцію fnv для їхнього об'єднання із сумішшю. Використовується 128 байтів послідовного доступу, щоб кожен раунд алгоритму завжди отримував повну сторінку з ОЗП, мінімізуючи промахи буфера асоціативної трансляції, яких теоретично могли б уникнути ASIC.

Якщо результат цього алгоритму нижчий за бажану ціль, то nonce є дійсним. Зауважте, що додаткове застосування sha3_256 наприкінці гарантує, що існує проміжний nonce, який може бути наданий для доказу того, що було виконано принаймні невеликий обсяг роботи; ця швидка зовнішня PoW-перевірка може використовуватися для цілей захисту від DDoS. Це також служить для надання статистичної гарантії того, що результат є незміщеним 256-бітним числом.

Майнінг

Алгоритм майнінгу визначається таким чином:

1def mine(full_size, dataset, header, difficulty):
2    # zero-pad target to compare with hash on the same digit
3    target = zpad(encode_int(2**256 // difficulty), 64)[::-1]
4    from random import randint
5    nonce = randint(0, 2**64)
6    while hashimoto_full(full_size, dataset, header, nonce) > target:
7        nonce = (nonce + 1) % 2**64
8    return nonce

Визначення хешу початкового значення

Щоб обчислити хеш початкового значення, який буде використовуватися для майнінгу поверх заданого блоку, ми використовуємо такий алгоритм:

1 def get_seedhash(block):
2     s = '\x00' * 32
3     for i in range(block.number // EPOCH_LENGTH):
4         s = serialize_hash(sha3_256(s))
5     return s

Зауважте, що для безперебійного майнінгу та перевірки ми рекомендуємо попередньо обчислювати майбутні хеші початкових значень і набори даних в окремому потоці.

Для подальшого читання

Знайшли ресурс, який допоміг з цією темою? Відредагуйте цю сторінку і додайте його!

Додаток

Наведений нижче код слід додати на початку, якщо ви зацікавлені в запуску наведеної вище специфікації python як коду.

1import sha3, copy
2
3# Assumes little endian bit ordering (same as Intel architectures)
4def decode_int(s):
5    return int(s[::-1].encode('hex'), 16) if s else 0
6
7def encode_int(s):
8    a = "%x" % s
9    return '' if s == 0 else ('0' * (len(a) % 2) + a).decode('hex')[::-1]
10
11def zpad(s, length):
12    return s + '\x00' * max(0, length - len(s))
13
14def serialize_hash(h):
15    return ''.join([zpad(encode_int(x), 4) for x in h])
16
17def deserialize_hash(h):
18    return [decode_int(h[i:i+WORD_BYTES]) for i in range(0, len(h), WORD_BYTES)]
19
20def hash_words(h, sz, x):
21    if isinstance(x, list):
22        x = serialize_hash(x)
23    y = h(x)
24    return deserialize_hash(y)
25
26def serialize_cache(ds):
27    return ''.join([serialize_hash(h) for h in ds])
28
29serialize_dataset = serialize_cache
30
31# sha3 hash function, outputs 64 bytes
32def sha3_512(x):
33    return hash_words(lambda v: sha3.sha3_512(v).digest(), 64, x)
34
35def sha3_256(x):
36    return hash_words(lambda v: sha3.sha3_256(v).digest(), 32, x)
37
38def xor(a, b):
39    return a ^ b
40
41def isprime(x):
42    for i in range(2, int(x**0.5)):
43         if x % i == 0:
44             return False
45    return True
Показати все

Розміри даних

Наведені нижче таблиці пошуку містять приблизно 2048 табульованих епох розмірів даних і розмірів кешу.

1def get_datasize(block_number):
2    return data_sizes[block_number // EPOCH_LENGTH]
3
4def get_cachesize(block_number):
5    return cache_sizes[block_number // EPOCH_LENGTH]
6
7data_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]
418
419cache_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]
Показати все