Ethash
Lần chỉnh sửa gần nhất: @minimalsm(opens in a new tab), 6 tháng 3, 2024
Ethash(opens in a new tab) is a modified version of the Dagger-Hashimoto algorithm. Ethash proof-of-work is memory hard(opens in a new tab), which was thought to make the algorithm ASIC resistant. Ethash ASICs were eventually developed but GPU mining was still a viable option until proof-of-work was switched off. Ethash is still used to mine other coins on other non-Ethereum proof-of-work networks.
How does Ethash work?
Memory hardness is achieved with a proof of work algorithm that requires choosing subsets of a fixed resource dependent on the nonce and block header. This resource (a few gigabytes in size) is called a DAG. The DAG is changed every 30000 blocks, a ~125-hour window called an epoch (roughly 5.2 days) and takes a while to generate. Since the DAG only depends on block height, it can be pre-generated, but if it's not the client needs to wait until the end of this process to produce a block. If clients do not pre-generate and cache DAGs ahead of time the network may experience massive block delay on each epoch transition. Note that the DAG does not need to be generated for verifying the proof-of-work essentially allowing for verification with both low CPU and small memory.
The general route that the algorithm takes is as follows:
- There exists a seed which can be computed for each block by scanning through the block headers up until that point.
- From the seed, one can compute a 16 MB pseudorandom cache. Light clients store the cache.
- From the cache, we can generate a 1 GB dataset, with the property that each item in the dataset depends on only a small number of items from the cache. Full clients and miners store the dataset. The dataset grows linearly with time.
- Mining involves grabbing random slices of the dataset and hashing them together. Verification can be done with low memory by using the cache to regenerate the specific pieces of the dataset that you need, so you only need to store the cache.
The large dataset is updated once every 30000 blocks, so the vast majority of a miner's effort will be reading the dataset, not making changes to it.
Definitions
We employ the following definitions:
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 loopHiện tất cả
The use of 'SHA3'
Ethereum's development coincided with the development of the SHA3 standard, and the standards process made a late change in the padding of the finalized hash algorithm, so that Ethereum's "sha3_256" and "sha3_512" hashes are not standard sha3 hashes, but a variant often referred to as "Keccak-256" and "Keccak-512" in other contexts. See discussion, e.g. here(opens in a new tab), here(opens in a new tab), or here(opens in a new tab).
Please keep that in mind as "sha3" hashes are referred to in the description of the algorithm below.
Parameters
The parameters for Ethash's cache and dataset depend on the block number. The cache size and dataset size both grow linearly; however, we always take the highest prime below the linearly growing threshold in order to reduce the risk of accidental regularities leading to cyclic behavior.
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 szHiện tất cảSao chép
Tables of dataset and cache size values are provided in the appendix.
Cache generation
Now, we specify the function for producing a cache:
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 oHiện tất cảSao chép
The cache production process involves first sequentially filling up 32 MB of memory, then performing two passes of Sergio Demian Lerner's RandMemoHash algorithm from Strict Memory Hard Hashing Functions (2014)(opens in a new tab). The output is a set of 524288 64-byte values.
Data aggregation function
We use an algorithm inspired by the FNV hash(opens in a new tab) in some cases as a non-associative substitute for XOR. Note that we multiply the prime with the full 32-bit input, in contrast with the FNV-1 spec which multiplies the prime with one byte (octet) in turn.
1FNV_PRIME = 0x0100019323def fnv(v1, v2):4 return ((v1 * FNV_PRIME) ^ v2) % 2**32Sao chép
Please note, even the yellow paper specifies fnv as v1*(FNV_PRIME ^ v2), all current implementations consistently use the above definition.
Full dataset calculation
Each 64-byte item in the full 1 GB dataset is computed as follows:
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)Hiện tất cảSao chép
Essentially, we combine data from 256 pseudorandomly selected cache nodes, and hash that to compute the dataset node. The entire dataset is then generated by:
1def calc_dataset(full_size, cache):2 return [calc_dataset_item(cache, i) for i in range(full_size // HASH_BYTES)]Sao chép
Main loop
Now, we specify the main "hashimoto"-like loop, where we aggregate data from the full dataset in order to produce our final value for a particular header and nonce. In the code below, header
represents the SHA3-256 hash of the RLP representation of a truncated block header, that is, of a header excluding the fields mixHash and nonce. nonce
is the eight bytes of a 64 bit unsigned integer in big-endian order. So nonce[::-1]
is the eight-byte little-endian representation of that value:
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])Hiện tất cảSao chép
Essentially, we maintain a "mix" 128 bytes wide, and repeatedly sequentially fetch 128 bytes from the full dataset and use the fnv
function to combine it with the mix. 128 bytes of sequential access are used so that each round of the algorithm always fetches a full page from RAM, minimizing translation lookaside buffer misses which ASICs would theoretically be able to avoid.
If the output of this algorithm is below the desired target, then the nonce is valid. Note that the extra application of sha3_256
at the end ensures that there exists an intermediate nonce which can be provided to prove that at least a small amount of work was done; this quick outer PoW verification can be used for anti-DDoS purposes. It also serves to provide statistical assurance that the result is an unbiased, 256-bit number.
Mining
The mining algorithm is defined as follows:
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 nonceSao chép
Defining the seed hash
In order to compute the seed hash that would be used to mine on top of a given block, we use the following algorithm:
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 sSao chép
Note that for smooth mining and verifying, we recommend pre-computing future seedhashes and datasets in a separate thread.
Further reading
Know of a community resource that helped you? Edit this page and add it!
Appendix
The following code should be prepended if you are interested in running the above python spec as code.
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 TrueHiện tất cảSao chép
Data Sizes
The following lookup tables provide approximately 2048 tabulated epochs of data sizes and cache sizes.
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]Hiện tất cảSao chép