Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-compress

Source of release 0.9.1

0.9.1 / src / flate / module.lucb

#==============================================================================================
#
#   flate - Fast DEFLATE for image codecs: table-driven inflate, level 0..9 deflate
#           in independent segments, CRC-32 and Adler-32
#
#   DESCRIPTION:
#       Whole-buffer primitives for callers that know their sizes and do their own
#       framing, as PNG, TIFF and OpenEXR do. Inflate decodes a raw DEFLATE stream into
#       an exact-size buffer through 11-bit lookup tables and a 64-bit bit buffer.
#       Deflate compresses one segment with a fresh 32 KiB window (hash buckets at
#       level 1, greedy hash chains at 2..9; dynamic, fixed or stored blocks, whichever
#       is smallest) and ends it with a sync flush, or a final block for the last one.
#       Segments are independent, so a caller can compress them on many threads and
#       concatenate them into one valid stream, as pigz does; `adler32_combine` then
#       gives the zlib checksum of the whole.
#
#       Fragments, in ORDER:
#
#       module.lucb    the API, CRC-32 (slicing by eight) and Adler-32
#       inflate.lucb   the decoder
#       deflate.lucb   the matcher and segment compressor
#       fastest.lucb   level 1's chainless parser
#       codes.lucb     Huffman code lengths and block writing
#       tests.lucb     the module's tests
#
#==============================================================================================
import memory
from binary import corrupt, invalid, limit

## Reports progress while inflating: the context, and bytes of output complete.
pub type Progress = func(void*?, usize) -> unit

## The zlib header for a stream compressed at `level` with a 32 KiB window.
pub func zlib_header(level: i32) -> u8[2]:
    let flag: u8 = 0x01 if level <= 1 else 0x5E if level <= 5 else 0x9C if level == 6 else 0xDA
    return [0x78, flag]

## CRC-32 (ISO 3309, as PNG and gzip use) of `data`, continuing from `crc`.
pub func crc32(data: const u8[], crc: u32 = 0) -> u32:
    var c = ~crc
    let p = data.data
    let n = data.length
    var i: usize = 0
    let t = &crc_table[0]
    while i + 8 <= n:
        let low = c ^ ((u32)p[i] | ((u32)p[i + 1] << 8) | ((u32)p[i + 2] << 16) | ((u32)p[i + 3] << 24))
        let high = (u32)p[i + 4] | ((u32)p[i + 5] << 8) | ((u32)p[i + 6] << 16) | ((u32)p[i + 7] << 24)
        c = t[1792 + (usize)(low & 255)] ^ t[1536 + (usize)((low >> 8) & 255)] ^ t[1280 + (usize)((low >> 16) & 255)] ^ t[1024 + (usize)(low >> 24)] ^ t[768 + (usize)(high & 255)] ^ t[512 + (usize)((high >> 8) & 255)] ^ t[256 + (usize)((high >> 16) & 255)] ^ t[(usize)(high >> 24)]
        i += 8
    while i < n:
        c = (c >> 8) ^ t[(usize)((c ^ (u32)p[i]) & 255)]
        i += 1
    return ~c

## Adler-32 of `data`, continuing from `adler` (1 to start).
pub func adler32(data: const u8[], adler: u32 = 1) -> u32:
    var a = adler & 65535
    var b = adler >> 16
    let p = data.data
    var i: usize = 0
    let n = data.length
    while i < n:
        # 5552 bytes keep both sums inside 32 bits before the modulus.
        let end = i + 5552 if i + 5552 < n else n
        while i + 8 <= end:
            # Eight bytes at once: their sum, and their sum weighted 8..1, from 16-bit
            # lanes multiplied so one lane gathers the total (no lane overflows).
            let v = memory.read[u64](p + i)
            let even = v & 0x00FF00FF00FF00FF
            let odd = (v >> 8) & 0x00FF00FF00FF00FF
            let sum = (u32)(((even + odd) *% 0x0001000100010001) >> 48)
            let weighted = (u32)(((even *% 0x0008000600040002) >> 48) & 65535) + (u32)(((odd *% 0x0007000500030001) >> 48) & 65535)
            b += 8 * a + weighted
            a += sum
            i += 8
        while i < end:
            a += (u32)p[i]
            b += a
            i += 1
        a %= 65521
        b %= 65521
    return (b << 16) | a

## The Adler-32 of two pieces joined, from each piece's and the second's length.
pub func adler32_combine(first: u32, second: u32, length: usize) -> u32:
    let base: u64 = 65521
    let rem = (u64)length % base
    var sum1 = (u64)first & 65535
    var sum2 = (rem * sum1) % base
    sum1 += ((u64)second & 65535) + base - 1
    sum2 += (((u64)first >> 16) & 65535) + (((u64)second >> 16) & 65535) + base - rem
    if sum1 >= base:
        sum1 -= base
    if sum1 >= base:
        sum1 -= base
    if sum2 >= base * 2:
        sum2 -= base * 2
    if sum2 >= base:
        sum2 -= base
    return (u32)(sum1 | (sum2 << 16))

## Slicing-by-eight tables: [k * 256 + byte].
let crc_table: u32[2048] = [0, 1996959894, 3993919788, 2567524794, 124634137, 1886057615, 3915621685, 2657392035, 249268274, 2044508324, 3772115230, 2547177864, 162941995, 2125561021, 3887607047, 2428444049, 498536548, 1789927666, 4089016648, 2227061214, 450548861, 1843258603, 4107580753, 2211677639, 325883990, 1684777152, 4251122042, 2321926636, 335633487, 1661365465, 4195302755, 2366115317, 997073096, 1281953886, 3579855332, 2724688242, 1006888145, 1258607687, 3524101629, 2768942443, 901097722, 1119000684, 3686517206, 2898065728, 853044451, 1172266101, 3705015759, 2882616665, 651767980, 1373503546, 3369554304, 3218104598, 565507253, 1454621731, 3485111705, 3099436303, 671266974, 1594198024, 3322730930, 2970347812, 795835527, 1483230225, 3244367275, 3060149565, 1994146192, 31158534, 2563907772, 4023717930, 1907459465, 112637215, 2680153253, 3904427059, 2013776290, 251722036, 2517215374, 3775830040, 2137656763, 141376813, 2439277719, 3865271297, 1802195444, 476864866, 2238001368, 4066508878, 1812370925, 453092731, 2181625025, 4111451223, 1706088902, 314042704, 2344532202, 4240017532, 1658658271, 366619977, 2362670323, 4224994405, 1303535960, 984961486, 2747007092, 3569037538, 1256170817, 1037604311, 2765210733, 3554079995, 1131014506, 879679996, 2909243462, 3663771856, 1141124467, 855842277, 2852801631, 3708648649, 1342533948, 654459306, 3188396048, 3373015174, 1466479909, 544179635, 3110523913, 3462522015, 1591671054, 702138776, 2966460450, 3352799412, 1504918807, 783551873, 3082640443, 3233442989, 3988292384, 2596254646, 62317068, 1957810842, 3939845945, 2647816111, 81470997, 1943803523, 3814918930, 2489596804, 225274430, 2053790376, 3826175755, 2466906013, 167816743, 2097651377, 4027552580, 2265490386, 503444072, 1762050814, 4150417245, 2154129355, 426522225, 1852507879, 4275313526, 2312317920, 282753626, 1742555852, 4189708143, 2394877945, 397917763, 1622183637, 3604390888, 2714866558, 953729732, 1340076626, 3518719985, 2797360999, 1068828381, 1219638859, 3624741850, 2936675148, 906185462, 1090812512, 3747672003, 2825379669, 829329135, 1181335161, 3412177804, 3160834842, 628085408, 1382605366, 3423369109, 3138078467, 570562233, 1426400815, 3317316542, 2998733608, 733239954, 1555261956, 3268935591, 3050360625, 752459403, 1541320221, 2607071920, 3965973030, 1969922972, 40735498, 2617837225, 3943577151, 1913087877, 83908371, 2512341634, 3803740692, 2075208622, 213261112, 2463272603, 3855990285, 2094854071, 198958881, 2262029012, 4057260610, 1759359992, 534414190, 2176718541, 4139329115, 1873836001, 414664567, 2282248934, 4279200368, 1711684554, 285281116, 2405801727, 4167216745, 1634467795, 376229701, 2685067896, 3608007406, 1308918612, 956543938, 2808555105, 3495958263, 1231636301, 1047427035, 2932959818, 3654703836, 1088359270, 936918000, 2847714899, 3736837829, 1202900863, 817233897, 3183342108, 3401237130, 1404277552, 615818150, 3134207493, 3453421203, 1423857449, 601450431, 3009837614, 3294710456, 1567103746, 711928724, 3020668471, 3272380065, 1510334235, 755167117, 0, 421212481, 842424962, 724390851, 1684849924, 2105013317, 1448781702, 1329698503, 3369699848, 3519200073, 4210026634, 3824474571, 2897563404, 3048111693, 2659397006, 2274893007, 1254232657, 1406739216, 2029285587, 1643069842, 783210325, 934667796, 479770071, 92505238, 2182846553, 2600511768, 2955803355, 2838940570, 3866582365, 4285295644, 3561045983, 3445231262, 2508465314, 2359236067, 2813478432, 3198777185, 4058571174, 3908292839, 3286139684, 3670389349, 1566420650, 1145479147, 1869335592, 1987116393, 959540142, 539646703, 185010476, 303839341, 3745920755, 3327985586, 3983561841, 4100678960, 3140154359, 2721170102, 2300350837, 2416418868, 396344571, 243568058, 631889529, 1018359608, 1945336319, 1793607870, 1103436669, 1490954812, 4034481925, 3915546180, 3259968903, 3679722694, 2484439553, 2366552896, 2787371139, 3208174018, 950060301, 565965900, 177645455, 328046286, 1556873225, 1171730760, 1861902987, 2011255754, 3132841300, 2745199637, 2290958294, 2442530455, 3738671184, 3352078609, 3974232786, 4126854035, 1919080284, 1803150877, 1079293406, 1498383519, 370020952, 253043481, 607678682, 1025720731, 1711106983, 2095471334, 1472923941, 1322268772, 26324643, 411738082, 866634785, 717028704, 2904875439, 3024081134, 2668790573, 2248782444, 3376948395, 3495106026, 4219356713, 3798300520, 792689142, 908347575, 487136116, 68299317, 1263779058, 1380486579, 2036719216, 1618931505, 3890672638, 4278043327, 3587215740, 3435896893, 2206873338, 2593195963, 2981909624, 2829542713, 998479947, 580430090, 162921161, 279890824, 1609522511, 1190423566, 1842954189, 1958874764, 4082766403, 3930137346, 3245109441, 3631694208, 2536953671, 2385372678, 2768287173, 3155920004, 1900120602, 1750776667, 1131931800, 1517083097, 355290910, 204897887, 656092572, 1040194781, 3113746450, 2692952403, 2343461520, 2461357009, 3723805974, 3304059991, 4022511508, 4141455061, 2919742697, 3072101800, 2620513899, 2234183466, 3396041197, 3547351212, 4166851439, 3779471918, 1725839073, 2143618976, 1424512099, 1307796770, 45282277, 464110244, 813994343, 698327078, 3838160568, 4259225593, 3606301754, 3488152955, 2158586812, 2578602749, 2996767038, 2877569151, 740041904, 889656817, 506086962, 120682355, 1215357364, 1366020341, 2051441462, 1667084919, 3422213966, 3538019855, 4190942668, 3772220557, 2945847882, 3062702859, 2644537544, 2226864521, 52649286, 439905287, 823476164, 672009861, 1733269570, 2119477507, 1434057408, 1281543041, 2167981343, 2552493150, 3004082077, 2853541596, 3847487515, 4233048410, 3613549209, 3464057816, 1239502615, 1358593622, 2077699477, 1657543892, 764250643, 882293586, 532408465, 111204816, 1585378284, 1197851309, 1816695150, 1968414767, 974272232, 587794345, 136598634, 289367339, 2527558116, 2411481253, 2760973158, 3179948583, 4073438432, 3956313505, 3237863010, 3655790371, 347922877, 229101820, 646611775, 1066513022, 1892689081, 1774917112, 1122387515, 1543337850, 3697634229, 3313392372, 3998419255, 4148705398, 3087642289, 2702352368, 2319436851, 2468674930, 0, 29518391, 59036782, 38190681, 118073564, 114017003, 76381362, 89069189, 236147128, 265370511, 228034006, 206958561, 152762724, 148411219, 178138378, 190596925, 472294256, 501532999, 530741022, 509615401, 456068012, 451764635, 413917122, 426358261, 305525448, 334993663, 296822438, 275991697, 356276756, 352202787, 381193850, 393929805, 944588512, 965684439, 1003065998, 973863097, 1061482044, 1049003019, 1019230802, 1023561829, 912136024, 933002607, 903529270, 874031361, 827834244, 815125939, 852716522, 856752605, 611050896, 631869351, 669987326, 640506825, 593644876, 580921211, 551983394, 556069653, 712553512, 733666847, 704405574, 675154545, 762387700, 749958851, 787859610, 792175277, 1889177024, 1901651959, 1931368878, 1927033753, 2006131996, 1985040171, 1947726194, 1976933189, 2122964088, 2135668303, 2098006038, 2093965857, 2038461604, 2017599123, 2047123658, 2076625661, 1824272048, 1836991623, 1866005214, 1861914857, 1807058540, 1786244187, 1748062722, 1777547317, 1655668488, 1668093247, 1630251878, 1625932113, 1705433044, 1684323811, 1713505210, 1742760333, 1222101792, 1226154263, 1263738702, 1251046777, 1339974652, 1310460363, 1281013650, 1301863845, 1187289752, 1191637167, 1161842422, 1149379777, 1103966788, 1074747507, 1112139306, 1133218845, 1425107024, 1429406311, 1467333694, 1454888457, 1408811148, 1379576507, 1350309090, 1371438805, 1524775400, 1528845279, 1499917702, 1487177649, 1575719220, 1546255107, 1584350554, 1605185389, 3778354048, 3774312887, 3803303918, 3816007129, 3862737756, 3892238699, 3854067506, 3833203973, 4012263992, 4007927823, 3970080342, 3982554209, 3895452388, 3924658387, 3953866378, 3932773565, 4245928176, 4241609415, 4271336606, 4283762345, 4196012076, 4225268251, 4187931714, 4166823541, 4076923208, 4072833919, 4035198246, 4047918865, 4094247316, 4123732899, 4153251322, 4132437965, 3648544096, 3636082519, 3673983246, 3678331705, 3732010428, 3753090955, 3723829714, 3694611429, 3614117080, 3601426159, 3572488374, 3576541825, 3496125444, 3516976691, 3555094634, 3525581405, 3311336976, 3298595879, 3336186494, 3340255305, 3260503756, 3281337595, 3251864226, 3222399125, 3410866088, 3398419871, 3368647622, 3372945905, 3427010420, 3448139075, 3485520666, 3456284973, 2444203584, 2423127159, 2452308526, 2481530905, 2527477404, 2539934891, 2502093554, 2497740997, 2679949304, 2659102159, 2620920726, 2650438049, 2562027300, 2574714131, 2603727690, 2599670141, 2374579504, 2353749767, 2383274334, 2412743529, 2323684844, 2336421851, 2298759554, 2294686645, 2207933576, 2186809023, 2149495014, 2178734801, 2224278612, 2236720739, 2266437690, 2262135309, 2850214048, 2820717207, 2858812622, 2879680249, 2934667388, 2938704459, 2909776914, 2897069605, 2817622296, 2788420399, 2759153014, 2780249921, 2700618180, 2704950259, 2742877610, 2730399645, 3049550800, 3020298727, 3057690558, 3078802825, 2999835404, 3004150075, 2974355298, 2961925461, 3151438440, 3121956959, 3092510214, 3113327665, 3168701108, 3172786307, 3210370778, 3197646061, 0, 3099354981, 2852767883, 313896942, 2405603159, 937357362, 627793884, 2648127673, 3316918511, 2097696650, 1874714724, 3607201537, 1255587768, 4067088605, 3772741427, 1482887254, 1343838111, 3903140090, 4195393300, 1118632049, 3749429448, 1741137837, 1970407491, 3452858150, 2511175536, 756094997, 1067759611, 2266550430, 449832999, 2725482306, 2965774508, 142231497, 2687676222, 412010587, 171665333, 2995192016, 793786473, 2548850444, 2237264098, 1038456711, 1703315409, 3711623348, 3482275674, 1999841343, 3940814982, 1381529571, 1089329165, 4166106984, 4029413537, 1217896388, 1512189994, 3802027855, 2135519222, 3354724499, 3577784189, 1845280792, 899665998, 2367928107, 2677414085, 657096608, 3137160985, 37822588, 284462994, 2823350519, 2601801789, 598228824, 824021174, 2309093331, 343330666, 2898962447, 3195996129, 113467524, 1587572946, 3860600759, 4104763481, 1276501820, 3519211397, 1769898208, 2076913422, 3279374443, 3406630818, 1941006535, 1627703081, 3652755532, 1148164341, 4241751952, 3999682686, 1457141531, 247015245, 3053797416, 2763059142, 470583459, 2178658330, 963106687, 735213713, 2473467892, 992409347, 2207944806, 2435792776, 697522413, 3024379988, 217581361, 508405983, 2800865210, 4271038444, 1177467017, 1419450215, 3962007554, 1911572667, 3377213406, 3690561584, 1665525589, 1799331996, 3548628985, 3241568279, 2039091058, 3831314379, 1558270126, 1314193216, 4142438437, 2928380019, 372764438, 75645176, 3158189981, 568925988, 2572515393, 2346768303, 861712586, 3982079547, 1441124702, 1196457648, 4293663189, 1648042348, 3666298377, 3358779879, 1888390786, 686661332, 2421291441, 2196002399, 978858298, 2811169155, 523464422, 226935048, 3040519789, 3175145892, 100435649, 390670639, 2952089162, 841119475, 2325614998, 2553003640, 546822429, 2029308235, 3225988654, 3539796416, 1782671013, 4153826844, 1328167289, 1570739863, 3844338162, 1298864389, 4124540512, 3882013070, 1608431339, 3255406162, 2058742071, 1744848601, 3501990332, 2296328682, 811816591, 584513889, 2590678532, 129869501, 3204563416, 2914283062, 352848211, 494030490, 2781751807, 3078325777, 264757620, 2450577869, 715964072, 941166918, 2158327331, 3636881013, 1618608400, 1926213374, 3396585883, 1470427426, 4011365959, 4255988137, 1158766284, 1984818694, 3471935843, 3695453837, 1693991400, 4180638033, 1100160564, 1395044826, 3952793279, 3019491049, 189112716, 435162722, 2706139399, 1016811966, 2217162459, 2526189877, 774831696, 643086745, 2666061564, 2354934034, 887166583, 2838900430, 294275499, 54519365, 3145957664, 3823145334, 1532818963, 1240029693, 4048895640, 1820460577, 3560857924, 3331051178, 2117577167, 3598663992, 1858283101, 2088143283, 3301633750, 1495127663, 3785470218, 4078182116, 1269332353, 332098007, 2876706482, 3116540252, 25085497, 2628386432, 605395429, 916469259, 2384220526, 2254837415, 1054503362, 745528876, 2496903497, 151290352, 2981684885, 2735556987, 464596510, 1137851976, 4218313005, 3923506883, 1365741990, 3434129695, 1946996346, 1723425172, 3724871409, 0, 1029712304, 2059424608, 1201699536, 4118849216, 3370159984, 2403399072, 2988497936, 812665793, 219177585, 1253054625, 2010132753, 3320900865, 4170237105, 3207642721, 2186319825, 1625331586, 1568718386, 438355170, 658566482, 2506109250, 2818578674, 4020265506, 3535817618, 1351670851, 1844508147, 709922595, 389064339, 2769320579, 2557498163, 3754961379, 3803185235, 3250663172, 4238411444, 3137436772, 2254525908, 876710340, 153198708, 1317132964, 1944187668, 4054934725, 3436268917, 2339452837, 3054575125, 70369797, 961670069, 2129760613, 1133623509, 2703341702, 2621542710, 3689016294, 3867263574, 1419845190, 1774270454, 778128678, 318858390, 2438067015, 2888948471, 3952189479, 3606153623, 1691440519, 1504803895, 504432359, 594620247, 1492342857, 1704161785, 573770537, 525542041, 2910060169, 2417219385, 3618876905, 3939730521, 1753420680, 1440954936, 306397416, 790849880, 2634265928, 2690882808, 3888375336, 3668168600, 940822475, 91481723, 1121164459, 2142483739, 3448989963, 4042473659, 3075684971, 2318603227, 140739594, 889433530, 1923340138, 1338244826, 4259521226, 3229813626, 2267247018, 3124975642, 2570221389, 2756861693, 3824297005, 3734113693, 1823658381, 1372780605, 376603373, 722643805, 2839690380, 2485261628, 3548540908, 4007806556, 1556257356, 1638052860, 637716780, 459464860, 4191346895, 3300051327, 2199040943, 3195181599, 206718479, 825388991, 1989285231, 1274166495, 3382881038, 4106388158, 3009607790, 2382549470, 1008864718, 21111934, 1189240494, 2072147742, 2984685714, 2357631266, 3408323570, 4131834434, 1147541074, 2030452706, 1051084082, 63335554, 2174155603, 3170292451, 4216760371, 3325460867, 1947622803, 1232499747, 248909555, 867575619, 3506841360, 3966111392, 2881909872, 2527485376, 612794832, 434546784, 1581699760, 1663499008, 3782634705, 3692447073, 2612412337, 2799048193, 351717905, 697754529, 1849071985, 1398190273, 1881644950, 1296545318, 182963446, 931652934, 2242328918, 3100053734, 4284967478, 3255255942, 1079497815, 2100821479, 983009079, 133672583, 3050795671, 2293717799, 3474399735, 4067887175, 281479188, 765927844, 1778867060, 1466397380, 3846680276, 3626469220, 2676489652, 2733102084, 548881365, 500656741, 1517752501, 1729575173, 3577210133, 3898068133, 2952246901, 2459410373, 3910527195, 3564487019, 2480257979, 2931134987, 479546907, 569730987, 1716854139, 1530213579, 3647316762, 3825568426, 2745561210, 2663766474, 753206746, 293940330, 1445287610, 1799716618, 2314567513, 3029685993, 4080348217, 3461678473, 2088098201, 1091956777, 112560889, 1003856713, 3112514712, 2229607720, 3276105720, 4263857736, 1275433560, 1902492648, 918929720, 195422344, 685033439, 364179055, 1377080511, 1869921551, 3713294623, 3761522863, 2811507327, 2599689167, 413436958, 633644462, 1650777982, 1594160846, 3978570462, 3494118254, 2548332990, 2860797966, 1211387997, 1968470509, 854852413, 261368461, 3182753437, 2161434413, 3346310653, 4195650637, 2017729436, 1160000044, 42223868, 1071931724, 2378480988, 2963576044, 4144295484, 3395602316, 0, 3411858341, 1304994059, 2257875630, 2609988118, 1355649459, 3596215069, 486879416, 3964895853, 655315400, 2711298918, 1791488195, 2009251963, 3164476382, 973758832, 4048990933, 64357019, 3364540734, 1310630800, 2235723829, 2554806413, 1394316072, 3582976390, 517157411, 4018503926, 618222419, 2722963965, 1762783832, 1947517664, 3209171269, 970744811, 4068520014, 128714038, 3438335635, 1248109629, 2167961496, 2621261600, 1466012805, 3522553387, 447296910, 3959392091, 547575038, 2788632144, 1835791861, 1886307661, 3140622056, 1034314822, 4143626211, 75106221, 3475428360, 1236444838, 2196665603, 2682996155, 1421317662, 3525567664, 427767573, 3895035328, 594892389, 2782995659, 1857943406, 1941489622, 3101955187, 1047553757, 4113347960, 257428076, 3288652233, 1116777319, 2311878850, 2496219258, 1603640287, 3640781169, 308099796, 3809183745, 676813732, 2932025610, 1704983215, 2023410199, 3016104370, 894593820, 4262377657, 210634999, 3352484690, 1095150076, 2316991065, 2535410401, 1547934020, 3671583722, 294336591, 3772615322, 729897279, 2903845777, 1716123700, 2068629644, 2953845545, 914647431, 4258839074, 150212442, 3282623743, 1161604689, 2388688372, 2472889676, 1480171241, 3735940167, 368132066, 3836185911, 805002898, 2842635324, 1647574937, 2134298401, 3026852996, 855535146, 4188192143, 186781121, 3229539940, 1189784778, 2377547631, 2427670487, 1542429810, 3715886812, 371670393, 3882979244, 741170185, 2864262823, 1642462466, 2095107514, 3082559007, 824732849, 4201955092, 514856152, 3589064573, 1400419795, 2552522358, 2233554638, 1316849003, 3370776517, 62202976, 4075001525, 968836368, 3207280574, 1954014235, 1769133219, 2720925446, 616199592, 4024870413, 493229635, 3594175974, 1353627464, 2616354029, 2264355925, 1303087088, 3409966430, 6498043, 4046820398, 979978123, 3170710821, 2007099008, 1789187640, 2717386141, 661419827, 3962610838, 421269998, 3527459403, 1423225061, 2676515648, 2190300152, 1238466653, 3477467891, 68755798, 4115633027, 1041448998, 3095868040, 1943789869, 1860096405, 2776760880, 588673182, 3897205563, 449450869, 3516317904, 1459794558, 2623431131, 2170245475, 1242006214, 3432247400, 131015629, 4137259288, 1036337853, 3142660115, 1879958454, 1829294862, 2790523051, 549483013, 3952910752, 300424884, 3669282065, 1545650111, 2541513754, 2323209378, 1092980487, 3350330793, 216870412, 4256931033, 921128828, 2960342482, 2066738807, 1714085583, 2910195050, 736264132, 3770592353, 306060335, 3647131530, 1610005796, 2494197377, 2309971513, 1123257756, 3295149874, 255536279, 4268596802, 892423655, 3013951305, 2029645036, 1711070292, 2929725425, 674528607, 3815288570, 373562242, 3709388839, 1535949449, 2429577516, 2379569556, 1183418929, 3223189663, 188820282, 4195850735, 827017802, 3084859620, 2089020225, 1636228089, 2866415708, 743340786, 3876759895, 361896217, 3738094268, 1482340370, 2466671543, 2382584591, 1163888810, 3284924932, 144124321, 4190215028, 849168593, 3020503679, 2136336858, 1649465698, 2836138695, 798521449, 3838094284, 0, 2792819636, 2543784233, 837294749, 4098827283, 1379413927, 1674589498, 3316072078, 871321191, 2509784531, 2758827854, 34034938, 3349178996, 1641505216, 1346337629, 4131942633, 1742642382, 3249117050, 4030828007, 1446413907, 2475800797, 904311657, 68069876, 2725880384, 1412551337, 4064729373, 3283010432, 1708771380, 2692675258, 101317902, 937551763, 2442587175, 3485284764, 1774858792, 1478633653, 4266992385, 1005723023, 2642744891, 2892827814, 169477906, 4233263099, 1512406095, 1808623314, 3451546982, 136139752, 2926205020, 2676114113, 972376437, 2825102674, 236236518, 1073525883, 2576072655, 1546420545, 4200303349, 3417542760, 1841601500, 2609703733, 1039917185, 202635804, 2858742184, 1875103526, 3384067218, 4166835727, 1579931067, 1141601657, 3799809741, 3549717584, 1977839588, 2957267306, 372464350, 668680259, 2175552503, 2011446046, 3516084394, 3766168119, 1175200131, 2209029901, 635180217, 338955812, 2990736784, 601221559, 2242044419, 3024812190, 306049834, 3617246628, 1911408144, 1074125965, 3866285881, 272279504, 3058543716, 2275784441, 567459149, 3832906691, 1107462263, 1944752874, 3583875422, 2343980261, 767641425, 472473036, 3126744696, 2147051766, 3649987394, 3899029983, 1309766251, 3092841090, 506333494, 801510315, 2310084639, 1276520081, 3932237093, 3683203000, 2113813516, 3966292011, 1243601823, 2079834370, 3716205238, 405271608, 3192979340, 2411259153, 701492901, 3750207052, 2045810168, 1209569125, 4000285905, 734575199, 2378150379, 3159862134, 438345922, 2283203314, 778166598, 529136603, 3120492655, 2086260449, 3660498261, 3955679176, 1303499900, 3153699989, 495890209, 744928700, 2316418568, 1337360518, 3921775410, 3626602927, 2120129051, 4022892092, 1237286280, 2018993941, 3726666913, 461853231, 3186645403, 2350400262, 711936178, 3693557851, 2052076527, 1270360434, 3989775046, 677911624, 2384402428, 3220639073, 427820757, 1202443118, 3789347034, 3493118535, 1984154099, 3018127229, 362020041, 612099668, 2181885408, 1950653705, 3526596285, 3822816288, 1168934804, 2148251930, 645706414, 395618355, 2984485767, 544559008, 2248295444, 3085590153, 295523645, 3560598451, 1917673479, 1134918298, 3855773998, 328860103, 3052210803, 2214924526, 577903450, 3889505748, 1101147744, 1883911421, 3594338121, 3424493451, 1785369663, 1535282850, 4260726038, 944946072, 2653270060, 2949491377, 163225861, 4294103532, 1501944408, 1752023237, 3457862513, 196998655, 2915761739, 2619532502, 978710370, 2881684293, 229902577, 1012666988, 2586515928, 1603020630, 4193987810, 3356702335, 1852063179, 2553040162, 1046169238, 263412747, 2848217023, 1818454321, 3390333573, 4227627032, 1569420204, 60859927, 2782375331, 2487203646, 843627658, 4159668740, 1368951216, 1617990445, 3322386585, 810543216, 2520310724, 2815490393, 27783917, 3288386659, 1652017111, 1402985802, 4125677310, 1685994201, 3255382381, 4091620336, 1435902020, 2419138250, 910562686, 128847843, 2715354199, 1469150398, 4058414858, 3222168983, 1719234083, 2749255853, 94984985, 876691844, 2453031472, 0, 3433693342, 1109723005, 2391738339, 2219446010, 1222643300, 3329165703, 180685081, 3555007413, 525277995, 2445286600, 1567235158, 1471092047, 2600801745, 361370162, 3642757804, 2092642603, 2953916853, 1050555990, 4063508168, 4176560081, 878395215, 3134470316, 1987983410, 2942184094, 1676945920, 3984272867, 567356797, 722740324, 3887998202, 1764827929, 2778407815, 4185285206, 903635656, 3142804779, 2012833205, 2101111980, 2979425330, 1058630609, 4088621903, 714308067, 3862526333, 1756790430, 2753330688, 2933487385, 1651734407, 3975966820, 542535930, 2244825981, 1231508451, 3353891840, 188896414, 25648519, 3442302233, 1134713594, 2399689316, 1445480648, 2592229462, 336416693, 3634843435, 3529655858, 516441772, 2420588879, 1559052753, 698204909, 3845636723, 1807271312, 2803025166, 2916600855, 1635634313, 4025666410, 593021940, 4202223960, 919787974, 3093159461, 1962401467, 2117261218, 2996361020, 1008193759, 4038971457, 1428616134, 2576151384, 386135227, 3685348389, 3513580860, 499580322, 2471098945, 1608776415, 2260985971, 1248454893, 3303468814, 139259792, 42591881, 3458459159, 1085071860, 2349261162, 3505103035, 474062885, 2463016902, 1583654744, 1419882049, 2550902495, 377792828, 3660491170, 51297038, 3483679632, 1093385331, 2374089965, 2269427188, 1273935210, 3311514249, 164344343, 2890961296, 1627033870, 4000683757, 585078387, 672833386, 3836780532, 1782552599, 2794821769, 2142603813, 3005188795, 1032883544, 4047146438, 4227826911, 928351297, 3118105506, 1970307900, 1396409818, 2677114180, 287212199, 3719594553, 3614542624, 467372990, 2505346141, 1509854403, 2162073199, 1282711281, 3271268626, 240228748, 76845205, 3359543307, 1186043880, 2317064054, 796964081, 3811226735, 1839575948, 2702160658, 2882189835, 1734392469, 3924802934, 625327592, 4234522436, 818917338, 3191908409, 1927981223, 2016387518, 3028656416, 973776579, 4137723485, 2857232268, 1726474002, 3899187441, 616751215, 772270454, 3803048424, 1814228491, 2693328533, 2041117753, 3036871847, 999160644, 4146592730, 4259508931, 826864221, 3217552830, 1936586016, 3606501031, 442291769, 2496909786, 1484378436, 1388107869, 2652297411, 278519584, 3694387134, 85183762, 3384397196, 1194773103, 2342308593, 2170143720, 1307820918, 3279733909, 265733131, 2057717559, 3054258089, 948125770, 4096344276, 4276898253, 843467091, 3167309488, 1885556270, 2839764098, 1709792284, 3949353983, 667704161, 755585656, 3785577190, 1865176325, 2743489947, 102594076, 3401021058, 1144549729, 2291298815, 2186770662, 1325234296, 3228729243, 215514885, 3589828009, 424832311, 2547870420, 1534552650, 1370645331, 2635621325, 328688686, 3745342640, 2211456353, 1333405183, 3254067740, 224338562, 127544219, 3408931589, 1170156774, 2299866232, 1345666772, 2627681866, 303053225, 3736746295, 3565105198, 416624816, 2522494803, 1525692365, 4285207626, 868291796, 3176010551, 1910772649, 2065767088, 3079346734, 956571085, 4121828691, 747507711, 3760459617, 1856702594, 2717976604, 2831417605, 1684930971, 3940615800, 642451174]