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