Ethash
Page last update: 6 Márta 2024
Ba é Ethash algartam mianadóireachta cruthúnas-oibre Ethereum. Tá cruthúnas-de-oibre múchta go hiomlán anois agus tá Ethereum daingnithe anois ag baint úsáide as cruthúnas-de-gealláil ina ionad sin. Léigh tuilleadh ar An Cumasc, cruthúnas-gill agus geallchur. Leathanach le spéis stairiúil é seo!
Is leagan modhnaithe é Ethash den algartam Dagger-Hashimoto. Tá cruthú cuimhne ar cruthúnas-oibre Ethash, rud a measadh a fhágann go bhfuil an algartam frithsheasmhach in ASIC. Forbraíodh ASICanna Ethash sa deireadh ach bhí mianadóireacht GPU fós ina rogha inmharthana go dtí gur múchadh cruthúnas-oibre. Úsáidtear Ethash fós do mhianadóireacht bonn ar líonraí eile nach bhfuil ar chruthúnas-oibre Ethereum.
Conas a oibríonn Ethash?
Baintear cruas cuimhne amach le algartam cruthúnas oibre a éilíonn fo-thacair d'acmhainn sheasta a roghnú ag brath ar an gceannteideal nonce agus bloc. Tugtar DAG ar an acmhainn seo (cúpla gigibheart i méid). Athraítear an DAG gach 30000 bloc, fuinneog ~125 uair ar a dtugtar ré (thart ar 5.2 lá) agus tógann sé tamall le giniúint. Ós rud é nach mbraitheann an DAG ach ar airde an bhloic, is féidir é a réamhghiniúint, ach más rud é nach bhfuil sé ní mór don chliant fanacht go dtí deireadh an phróisis seo chun bloc a tháirgeadh. Mura ndéanann cliaint DAGanna a réamhghiniúint agus a thaisceadh roimh am d'fhéadfadh moill ollmhór bloc a bheith ag an líonra ar gach trasdul aga. Tabhair faoi deara nach gá an DAG a ghiniúint chun an cruthúnas-oibre a fhíorú rud a cheadaíonn fíorú go bunúsach le LAP íseal agus cuimhne beag.
Is é seo a leanas an bealach ginearálta a ghlacann an algartam:
- Tá síol ann ar féidir a ríomh do gach bloc ach scanadh a dhéanamh trí na ceanntásca bloc suas go dtí an pointe sin.
- Ón síol, is féidir taisce bréagrandamach 16 MB a ríomh. Stórálann cliant éadrom an taisce.
- Ón taisce, is féidir linn ** tacar sonraí 1 GB** a ghiniúint, leis an airí go mbraitheann gach mír sa tacar sonraí ar líon beag míreanna ón taisce. Stórálann cliaint iomlána agus mianadóirí an tacar sonraí. Fásann an tacar sonraí go líneach le himeacht ama.
- Is éard atá i gceist le mianadóireacht ná slisní randamacha den tacar sonraí a ghabháil agus iad a chur le chéile. Is féidir fíorú a dhéanamh le cuimhne íseal tríd an taisce a úsáid chun na píosaí sonracha den tacar sonraí a theastaíonn uait a athghiniúint, mar sin ní gá duit ach an taisce a stóráil.
Nuashonraítear an tacar sonraí mór uair amháin gach 30000 bloc, mar sin beidh formhór mór iarracht mianadóra ag léamh an tacar sonraí, gan athruithe a dhéanamh air.
Sainmhínithe
Bainimid úsáid as na sainmhínithe seo a leanas:
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 loopTaispeáin gach rudÚsáid 'SHA3'
Tharla forbairt Ethereum ag an am céanna le forbairt an chaighdeáin SHA3, agus rinne an próiseas caighdeáin athrú déanach i stuáil an algartam haise críochnaithe, ionas nach haiseanna Ethereum caighdeánacha sha3 iad "sha3_256" agus "sha3_512", ach malairt ar a dtugtar "Keccak-256" agus "Keccak-512" go minic i gcomhthéacsanna eile. Féach plé, e.g. anseo, anseo, nó anseo.
Meabhraigh le do thoil go dtagraítear do haiseanna mar "sha3" san algartam thíos.
Paraiméadair
Braitheann na paraiméadair taisce agus tacar sonraí Ethash ar uimhir an bhloic. Fásann méid an taisce agus méid an tacair sonraí go líneach; Mar sin féin, glacaimid an príomhphíobán is airde faoi bhun na tairsí fáis líneach i gcónaí chun an riosca a bhaineann le rialtachtaí trí thimpiste as a dtagann iompar timthriallach a laghdú.
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 szTaispeáin gach rudTá táblaí tacair sonraí agus luachanna méid an taisce curtha ar fáil san aguisín.
Giniúint taisce
Anois, sonraímid an fheidhm chun taisce a tháirgeadh:
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 oTaispeáin gach rudIs éard atá i gceist leis an bpróiseas táirgthe taisce ná 32 MB de chuimhne a líonadh go seicheamhach ar dtús, ansin dhá phas d'algartam RandMemoHash Sergio Demian Lerner a dhéanamh ó [Feidhmeanna Haiseála Crua Cuimhne (2014)](http://www. hashcash.org/papers/memohash.pdf). Is tacar de 524288 luachanna 64-beart é an t-aschur.
Feidhm chomhiomlánaithe sonraí
Úsáidimid algartam spreagtha ag an hais FNV i gcásanna áirithe mar ionadach neamh-chomhthiomsaitheach do XOR. Tabhair faoi deara go n-iolraímid an príomhshuim leis an ionchur iomlán 32-giotán, i gcodarsnacht leis an sonraíocht FNV-1 a iolraíonn an príomhshuim le beart amháin (ochtréad) ar a seal.
1FNV_PRIME = 0x0100019323def fnv(v1, v2):4 return ((v1 * FNV_PRIME) ^ v2) % 2**32Tabhair faoi deara, fiú sa pháipéar buí sonraítear fnv mar v1*(FNV_PRIME ^ v2), úsáideann gach feidhmiú reatha an sainmhíniú thuas go comhsheasmhach.
Ríomh tacar sonraí iomlán
Ríomhtar gach mír 64-beart sa tacar sonraí iomlán 1 GB mar seo a leanas:
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)Taispeáin gach rudGo bunúsach, cuirimid le chéile sonraí ó 256 nód taisce roghnaithe go bréagrandamach, agus haiseáltar é sin chun an nód tacair a ríomh. Gintear an tacar sonraí iomlán ansin ag:
1def calc_dataset(full_size, cache):2 return [calc_dataset_item(cache, i) for i in range(full_size // HASH_BYTES)]Príomhlúb
Anois, sonraímid an príomh-lúb cosúil le "hashimoto", áit a ndéanaimid sonraí a chomhiomlánú ón tacar sonraí iomlán chun ár luach deiridh a tháirgeadh le haghaidh ceannteidil agus nonce ar leith. Sa chód thíos, seasann ceanntásc don SHA3-256 hais den léiriú RLP de _teasctha ceanntásc bloc _, is é sin, ceanntásc nach bhfuil na réimsí mixHash agus nonce san áireamh. Is é nonce na hocht mbeart de shlánuimhir 64 ghiotán gan síniú in ord mórchinn. Mar sin is é nonce[::-1] an léiriú ocht mbeart beag-chinn den luach sin:
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])Taispeáin gach rudGo bunúsach, cothabháilimid "meascán" 128 beart ar leithead, agus faighimid 128 beart ón tacar sonraí iomlán arís agus arís eile go seicheamhach agus úsáidimid an fheidhm fnv chun é a chomhcheangal leis an meascán. Baintear úsáid as 128 beart de rochtain sheicheamhach ionas go bhfaigheann gach babhta den algartam leathanach iomlán ó RAM i gcónaí, rud a laghdóidh aon chaillteanais maoláin amharc-aistriúcháin a d'fhéadfadh ASICs a sheachaint go teoiriciúil.
Má tá aschur an algartam seo faoi bhun na sprice inmhianaithe, tá an nonce bailí. Tabhair faoi deara go gcinntíonn feidhmchlár breise sha3_256 ag an deireadh go bhfuil nonce idirmheánach ann is féidir a sholáthar chun a chruthú go ndearnadh méid beag oibre ar a laghad; is féidir an fíorú POW seachtrach tapa seo a úsáid chun críocha frith-DDoS. Soláthraíonn sé dearbhú staitistiúil freisin gur uimhir neamhchlaonta 256-giotán an toradh.
Mianadóireacht
Sainmhínítear an algartam mianadóireachta mar seo a leanas:
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 nonceAn hais síl a shainiú
D’fhonn an hais síl a d’úsáidfí chun mianadóireacht a dhéanamh ar bharr bloic áirithe a ríomh, bainimid úsáid as an algartam seo a leanas:
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 sTabhair faoi deara, le haghaidh mianadóireacht réidh agus fíorú, molaimid síológa agus tacair sonraí sa todhchaí a réamh-ríomh i snáithe ar leith.
Tuilleadh léitheoireachta
Ar eolas agat ar acmhainn pobail a chabhraigh leat? Cuir an leathanach seo in eagar agus cuir leis!
Aguisín
Ba cheart an cód seo a leanas a réamhshocrú má tá suim agat an sonra python thuas a rith mar chód.
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 TrueTaispeáin gach rudMéideanna Sonraí
Soláthraíonn na táblaí cuardaigh seo a leanas thart ar 2048 ré táblaithe de mhéideanna sonraí agus de mhéideanna taisce.
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]Taispeáin gach rud