Module:CRC 32 ISO HDLC LOOKUP

Documentation for this module may be created at Module:CRC 32 ISO HDLC LOOKUP/doc

-- CRC_32_ISO_HDLC lookup table
-- This CRC32 is used by FrooxEngine to derive an unknown type's displayed color in ProtoFlux.

-- Generated using the following C# code:

-- var lookup = GenerateSlicingLookupTable(3988292384u, isReversed: true);
-- var str = "";
-- foreach (var item in lookup)
-- {
--     str += item.ToString() + ",";
-- }
-- Console.WriteLine($"local lookup = {{[0]={str}}}");
-- 
-- uint[] GenerateSlicingLookupTable(uint polynomial, bool isReversed)
-- {
--     uint[] array = new uint[4096];
--     uint num = (isReversed ? 1u : 2147483648u);
--     for (int i = 0; i < 256; i++)
--     {
--         uint num2 = (uint)(isReversed ? i : (i << 24));
--         for (int j = 0; j < 16; j++)
--         {
--             for (int k = 0; k < 8; k++)
--             {
--                 num2 = ((!isReversed) ? (((num2 & num) != 0) ? (polynomial ^ (num2 << 1)) : (num2 << 1)) : (((num2 & num) == 1) ? (polynomial ^ (num2 >> 1)) : (num2 >> 1)));
--             }
--             array[256 * j + i] = num2;
--         }
--     }
--     return array;
-- }

local lookup = {[0]=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,0,393942083,787884166,965557445,1575768332,1251427663,1931114890,1684106697,3151536664,2896410203,2502855326,2186649309,3862229780,4048545623,3368213394,3753496529,2898281073,3149616690,2184604407,2504883892,4046197629,3864463166,3755621371,3366006712,387506281,6550570,971950319,781573292,1257550181,1569695014,1677892067,1937345952,2196865699,2508887776,2886183461,3145514598,3743273903,3362179052,4058774313,3868258154,958996667,777139448,400492605,10755198,1690661303,1941857780,1244879153,1565019506,775012562,961205393,13101140,398261271,1943900638,1688634781,1563146584,1246801179,2515100362,2190636681,3139390028,2892258831,3355784134,3749586821,3874691904,4052225795,3734110983,3387496260,4033096577,3877584834,2206093835,2483373640,2911402637,3136515790,1699389727,1915860316,1270647193,1556585946,950464531,803071056,374397077,19647702,1917993334,1697207605,1554278896,1272937907,800985210,952435769,21510396,372452543,3381322606,3740399405,3883715560,4027047851,2489758306,2199758369,3130039012,2917895847,1550025124,1259902439,1922410786,1710144865,26202280,385139947,796522542,939715693,3887801276,4039129087,3377269562,3728088953,3126293168,2905368307,2493602358,2212122229,4037264341,3889747862,3730172755,3375300368,2907673305,3124004506,2209987167,2495786524,1266377165,1543533966,1703758155,1928748296,379007169,32253058,945887303,790236164,1716846671,1898845196,1218652361,1608006794,1002000707,750929152,357530053,36990342,3717046871,3405166100,4084959953,3825245842,2153902939,2535122712,2929187805,3119304606,3398779454,3723384445,3831720632,4078468859,2541294386,2147616625,3113171892,2935238647,1900929062,1714877541,1606142112,1220599011,748794154,1004184937,39295404,355241455,3835986668,4091516591,3394415210,3710500393,3108557792,2922629027,2545875814,2160455461,1601970420,1208431799,1904871538,1727077425,43020792,367748539,744905086,991776061,1214562461,1595921630,1720903707,1911159896,361271697,49513938,998160663,738569556,4089209477,3838277318,3712633347,3392233024,2924491657,3106613194,2158369551,2547846988,3100050248,2948339467,2519804878,2169126797,3844821572,4065347079,3420289730,3701894785,52404560,342144275,770279894,982687125,1593045084,1233708063,1879431386,1736363161,336019769,58479994,988899775,764050940,1240141877,1586496630,1729968307,1885744368,2950685473,3097818978,2166999975,2522013668,4063474221,3846743662,3703937707,3418263272,976650731,760059304,348170605,62635310,1742393575,1889649828,1227683937,1582820386,2179867635,2526361520,2937588597,3093503798,3691148031,3413731004,4076100217,3851374138,2532754330,2173556697,3087067932,2944139103,3407516310,3697379029,3857496592,4070026835,758014338,978679233,64506116,346250567,1891774606,1740186829,1580472328,1229917259,0,4022496062,83218493,3946298115,166436986,3861498692,220098631,3806075769,332873972,4229245898,388141257,4175494135,440197262,4127099824,516501683,4044053389,665747944,3362581206,593187285,3432594155,776282514,3246869164,716239279,3312622225,880394524,3686509090,814485793,3746462239,1033003366,3528460888,963096923,3601193573,1331495888,2694801646,1269355501,2758457555,1186374570,2843003028,1111716759,2910918825,1552565028,3007850522,1484755737,3082680359,1432478558,3131279456,1368666979,3193329757,1760789048,2268195078,1812353541,2210675003,1628971586,2396670332,1710092927,2318375233,2066006732,2498144754,2144408305,2417195471,1926193846,2634877320,1983558283,2583222709,2662991776,1903717534,2588923805,1972223139,2538711002,2022952164,2477029351,2087066841,2372749140,1655647338,2308478825,1717238871,2223433518,1799654416,2155034387,1873894445,3105130056,1456926070,3185661557,1378041163,2969511474,1597852940,3020617231,1539874097,2864957116,1157737858,2922780289,1106542015,2737333958,1290407416,2816325371,1210047941,3521578096,1042640718,3574781005,986759027,3624707082,936300340,3707335735,859512585,3257943172,770846650,3334837433,688390023,3420185854,605654976,3475911875,552361981,4132013464,428600998,4072428965,494812827,4288816610,274747100,4216845791,345349857,3852387692,173846098,3781891409,245988975,3967116566,62328360,3900749099,121822741,3859089665,164061759,3807435068,221426178,4025395579,2933317,3944446278,81334904,4124199413,437265099,4045904328,518386422,4231653775,335250097,4174133682,386814604,3249244393,778691543,3311294676,714879978,3359647891,662848429,3434477742,595039120,3531393053,1035903779,3599308832,961245982,3684132967,877986649,3747788890,815846244,2841119441,1184522735,2913852140,1114616274,2696129195,1332855189,2756082326,1266946472,3129952805,1431118107,3195705880,1371074854,3009735263,1554415969,3079748194,1481855324,2398522169,1630855175,2315475716,1707159610,2266835779,1759461501,2213084030,1814728768,2636237773,1927520499,2580814832,1981182158,2496293815,2064121993,2420095882,2147340468,2025787041,2541577631,2085281436,2475210146,1901375195,2660681189,1973518054,2590184920,1801997909,2225743211,1872600680,2153772374,1652813359,2369881361,1719025170,2310296876,1594986313,2966676599,1541693300,3022402634,1459236659,3107472397,1376780046,3184366640,1288097725,2734990467,1211309952,2817619134,1160605639,2867791097,1104723962,2920993988,937561457,3626001999,857201996,3704993394,1040821515,3519792693,989625654,3577615880,607473029,3421972155,549494200,3473077894,769584639,3256649409,690699714,3337180924,273452185,4287555495,347692196,4219156378,430386403,4133832669,491977950,4069562336,60542061,3965298515,124656720,3903616878,175139863,3853649705,243645482,3779581716,0,3247366080,1483520449,2581751297,2967040898,1901571138,3904227907,691737987,3133399365,2068659845,3803142276,589399876,169513671,3415493895,1383475974,2482566342,2935407819,1870142219,4137319690,924099274,506443593,3751897225,1178799752,2278412616,339027342,3585866318,1280941135,2379694991,2766951948,1700956620,4236308429,1024339981,2258407383,1192382487,3740284438,528411094,910556245,4157285269,1848198548,2946996820,1012887186,4258378066,1681119059,2780629139,2357599504,1292419792,3572147409,358906641,678054684,3924071644,1879503581,2978491677,2561882270,1497229150,3235873119,22109855,2460592729,1395094937,3401913240,189516888,577821147,3825075739,2048679962,3146956762,3595049455,398902831,2384764974,1336573934,1720805997,2803873197,1056822188,4285729900,1821112490,2902796138,887570795,4117339819,3696397096,500978920,2218668777,1169222953,2025774372,3106931428,550659301,3780950821,3362238118,166293862,2416645991,1367722151,3262987361,66315169,2584839584,1537170016,1923370979,3005911075,717813282,3947244002,1356109368,2438613496,146288633,3375820857,3759007162,562248314,3093388411,2045739963,3927406461,731490493,2994458300,1945440636,1523451135,2604718911,44219710,3274466046,4263662323,1068272947,2790189874,1740649714,1325080945,2406874801,379033776,3608758128,1155642294,2238671990,479005303,3708016055,4097359924,901128180,2891217397,1843045941,2011248031,3060787807,797805662,3993195422,3342353949,112630237,2673147868,1591353372,3441611994,212601626,2504944923,1421914843,2113644376,3161815192,630660761,3826893145,3642224980,412692116,2172340373,1089836885,1775141590,2822790422,832715543,4029474007,1674842129,2723860433,1001957840,4197873168,3540870035,310623315,2338445906,1257178514,4051548744,821257608,2836464521,1755307081,1101318602,2150241802,432566283,3628511179,1270766349,2318435533,332587724,3529260300,4217841807,988411727,2735444302,1652903566,1602977411,2651169091,132630338,3328776322,4015131905,786223809,3074340032,1991273216,3846741958,616972294,3173262855,2091579847,1435626564,2485072772,234706309,3430124101,2712218736,1613231024,4190475697,944458353,292577266,3506339890,1226630707,2291284467,459984181,3672380149,1124496628,2189994804,2880683703,1782407543,4091479926,844224694,257943739,3469817723,1462980986,2529005242,3213269817,2114471161,3890881272,644152632,3046902270,1947391550,3991973951,746483711,88439420,3301680572,1563018173,2628197501,657826727,3871046759,2136545894,3201811878,2548879397,1449267173,3481299428,235845156,2650161890,1551408418,3315268387,68429027,758067552,3970035360,1967360161,3033356129,2311284588,1213053100,3517963949,270598509,958010606,4170500910,1635167535,2700636911,855672361,4069415401,1802256360,2866995240,2212099499,1113008747,3686091882,440112042,0,2611301487,3963330207,2006897392,50740095,2560849680,4013794784,1956178319,101480190,2645113489,3929532513,1905435662,84561281,2662269422,3912356638,1922342769,202960380,2545787283,3760419683,2072395532,253679235,2495322860,3810871324,2021655667,169122562,2444351341,3861841309,2106214898,152215677,2461527058,3844685538,2123133581,405920760,2207553431,4094313831,1873742088,456646791,2157096168,4144791064,1823027831,507358470,2241388905,4060492697,1772322806,490444409,2258557462,4043311334,1789215881,338245124,2408348267,4161972379,1672996084,388959611,2357870868,4212429796,1622269835,304431354,2306870421,4263435877,1706791434,287538053,2324051946,4246267162,1723705717,811841520,2881944479,3696765295,1207788800,862293135,2831204576,3747484176,1157324415,913293582,2915732833,3662962577,1106318334,896137841,2932651550,3646055662,1123494017,1014716940,2816349795,3493905555,1273334012,1065181555,2765630748,3544645612,1222882179,980888818,2714919069,3595350637,1307180546,963712909,2731826146,3578431762,1324336509,676490248,3019317351,3295277719,1607253752,726947703,2968591128,3345992168,1556776327,777919222,3053147801,3261432937,1505806342,760750473,3070062054,3244539670,1522987897,608862708,3220163995,3362856811,1406423812,659339915,3169449700,3413582868,1355966587,575076106,3118709605,3464325525,1440228858,557894773,3135602714,3447411434,1457397381,1623683040,4217512847,2365387135,391757072,1673614495,4167309552,2415577600,341804655,1724586270,4251866481,2331019137,290835438,1707942497,4268256782,2314648830,307490961,1826587164,4152020595,2162433155,457265388,1876539747,4101829900,2212636668,407333779,1792275682,4051089549,2263378557,491595282,1775619997,4067460082,2246988034,508239213,2029433880,3813931127,2496473735,258500328,2079362919,3763716872,2546668024,208559511,2130363110,3848244873,2462145657,157552662,2113730969,3864638966,2445764358,174205801,1961777636,4014675339,2564147067,57707284,2011718299,3964481268,2614361092,7778411,1927425818,3913769845,2665066885,92077546,1910772837,3930150922,2648673018,108709525,1352980496,3405878399,3164554895,658115296,1403183983,3355946752,3214507504,607924639,1453895406,3440239233,3130208369,557218846,1437504913,3456883198,3113552654,573589345,1555838444,3340335491,2961681267,723707676,1606028947,3290383100,3011612684,673504355,1521500946,3239382909,3062619533,758026722,1505130605,3256038402,3045975794,774417053,1217725416,3543158663,2762906999,1057739032,1267939479,3493229816,2812847624,1007544935,1318679830,3577493881,2728586121,956803046,1302285929,3594125830,2711933174,973184153,1150152212,3743982203,2830528651,856898788,1200346475,3694041348,2880457716,806684571,1115789546,3643069573,2931426933,891243034,1099408277,3659722746,2914794762,907637093,0,3717650821,1616688459,3184159950,3233376918,489665299,2699419613,2104690264,1510200173,2274691816,979330598,3888758691,2595928571,1194090622,4209380528,661706037,3020400346,1771143007,3562738577,164481556,1958661196,2837976521,350386439,3379863682,3993269687,865250354,2388181244,1406015865,784146209,4079732388,1323412074,2474079215,3011398645,1860735600,3542286014,246687547,1942430051,2924607718,328963112,3456978349,3917322392,887832861,2300653011,1421341782,700772878,4099025803,1234716485,2483986112,125431087,3673109674,1730500708,3132326369,3351283641,441867836,2812031730,2047535991,1568292418,2163009479,1025936137,3769651852,2646824148,1079348561,4255113631,537475098,3180171691,1612400686,3721471200,4717925,2100624189,2694980280,493375094,3237910515,3884860102,974691139,2278750093,1514417672,657926224,4204917205,1198234907,2600289438,160053105,3558665972,1775665722,3024116671,3375586791,346391650,2842683564,1962488105,1401545756,2384412057,869618007,3997403346,2469432970,1319524111,4083956673,788193860,250862174,3546612699,1856990997,3006903952,3461001416,333211981,2920678787,1937824774,1425017139,2305216694,883735672,3912918525,2487837605,1239398944,4095071982,696455019,3136584836,1734518017,3668494799,121507914,2051872274,2816200599,437363545,3347544796,3774328809,1029797484,2158697122,1564328743,542033279,4258798842,1074950196,2642717105,2691310871,2113731730,3224801372,497043929,1624461185,3175454212,9435850,3709412175,4201248378,671035391,2587181873,1201904308,986750188,3880142185,1519135143,2266689570,342721485,3388693064,1949382278,2846355203,3570723163,155332830,3028835344,1763607957,1315852448,2482538789,775087595,4087626862,2396469814,1396827059,4002123645,857560824,320106210,3464673127,1934154665,2933785132,3551331444,238804465,3018961215,1852270778,1226292623,2491507722,692783300,4108177729,2309936921,1412959900,3924976210,879016919,2803091512,2055541181,3343875443,450471158,1739236014,3124525867,133568485,3663777376,4245691221,545702608,2639048222,1088059291,1034514883,3762268230,1576387720,2153979149,501724348,3228659001,2109407735,2687359090,3713981994,13109167,3171052385,1620357860,1206151121,2591211092,666423962,4197321503,2271022407,1523307714,3875649548,982999433,2850034278,1953942499,3384583981,338329256,1767471344,3033506165,151375291,3566408766,4091789579,779425934,2478797888,1311354309,861580189,4006375960,1392910038,2391852883,2929327945,1930372812,3469036034,324244359,1847629279,3015068762,243015828,3555391761,4103744548,688715169,2496043375,1229996266,874727090,3920994103,1417671673,2313759356,446585235,3339223062,2059594968,2807313757,3660002053,129100416,3128657486,1743609803,1084066558,2634765179,549535669,4250396208,2149900392,1571961325,3765982499,1039043750,0,2635063670,3782132909,2086741467,430739227,2225303149,4173482934,1707977408,861478454,2924937024,3526875803,1329085421,720736557,3086643291,3415954816,1452586230,1722956908,4223524122,2279405761,450042295,2132718455,3792785921,2658170842,58693292,1441473114,3370435372,3028674295,696911745,1279765825,3511176247,2905172460,807831706,3445913816,1349228974,738901109,2969918723,3569940419,1237784245,900084590,2829701656,4265436910,1664255896,525574723,2187084597,3885099509,2057177219,117386584,2616249390,2882946228,920233410,1253605401,3619119471,2994391983,796207833,1393823490,3457937012,2559531650,92322804,2044829231,3840835417,2166609305,472659183,1615663412,4249022530,1102706673,3702920839,2698457948,1037619754,1477802218,3306854812,3111894087,611605809,1927342535,4025419953,2475568490,243387420,1800169180,4131620778,2317525617,388842247,655084445,3120835307,3328511792,1533734470,1051149446,2745738736,3754524715,1120297309,340972971,2304586973,4114354438,1748234352,234773168,2431761350,3968900637,1906278251,2363330345,299003487,1840466820,4038896370,2507210802,142532932,1948239007,3910149609,3213136159,579563625,1592415666,3286611140,2787646980,992477042,1195825833,3662232543,3933188933,2002801203,184645608,2517538462,4089658462,1858919720,313391347,2409765253,3644239219,1144605701,945318366,2773977256,3231326824,1570095902,569697989,3170568115,2205413346,511446676,1646078799,4279421497,2598330617,131105167,2075239508,3871229218,2955604436,757403810,1363424633,3427521551,2844163791,881434553,1223211618,3588709140,3854685070,2026779384,78583587,2577462869,4235025557,1633861091,486774840,2148301134,3600338360,1268198606,938871061,2868504675,3476308643,1379640277,777684494,3008718712,1310168890,3541595724,2943964055,846639841,1471879201,3400857943,3067468940,735723002,2102298892,3762382970,2619362721,19901655,1692534295,4193118049,2240594618,411247564,681945942,3047836192,3385552891,1422167693,822682701,2886124859,3496468704,1298661782,469546336,2264093718,4203901389,1738379451,38812283,2673859341,3812556502,2117148576,3268024339,1606809957,598006974,3198893512,3680933640,1181316734,973624229,2802299603,4052944421,1822222163,285065864,2381456382,3896478014,1966106696,156323219,2489232613,2759337087,964150537,1159127250,3625517476,3184831332,551242258,1555722185,3249901247,2535537225,170842943,1984954084,3946848146,2391651666,327308324,1877176831,4075589769,263086283,2460058045,4005602406,1942963472,369291216,2332888742,4151061373,1784924683,1022852861,2717425547,3717839440,1083595558,626782694,3092517008,3291821387,1497027645,1763466407,4094934481,2289211402,360544636,1890636732,3988730570,2447251217,215086695,1514488465,3343557607,3140191804,639919946,1139395978,3739626748,2726758695,1065936977,0,3120290792,2827399569,293431929,2323408227,864534155,586863858,2600537882,3481914503,1987188591,1729068310,3740575486,1173727716,4228805132,3983743093,1418249117,1147313999,4254680231,3974377182,1428157750,3458136620,2011505092,1721256893,3747844181,2347455432,839944224,594403929,2593536433,26687147,3094146371,2836498234,283794642,2294627998,826205558,541298447,2578994407,45702141,3141697557,2856315500,331624836,1196225049,4273416689,4023010184,1446090848,3442513786,1959480466,1706436331,3696098563,3433538001,1968994873,1679888448,3722103720,1188807858,4280295258,3999102243,1470541515,53374294,3134568126,2879970503,307431215,2303854645,816436189,567589284,2553242188,3405478781,1929420949,1652411116,3682996484,1082596894,4185703926,3892424591,1375368295,91404282,3163122706,2918450795,336584067,2400113305,922028401,663249672,2658384096,2392450098,929185754,639587747,2682555979,82149713,3172883129,2892181696,362343208,1091578037,4176212829,3918960932,1349337804,3412872662,1922537022,1676344391,3658557359,1111377379,4224032267,3937989746,1396912026,3359776896,1908013928,1623494929,3644803833,2377615716,877417100,623982837,2630542109,130804743,3190831087,2941083030,381060734,106748588,3215393092,2933549885,388083925,2350956495,903570471,614862430,2640172470,3386185259,1882115523,1632872378,3634920530,1135178568,4199721120,3945775833,1389631793,1317531835,4152109907,3858841898,1610259138,3304822232,2097172016,1820140617,3582394273,2165193788,955639764,696815021,2423477829,192043359,2995356343,2750736590,437203750,182808564,3005133852,2724453989,462947725,2157513367,962777471,673168134,2447663342,3312231283,2090301595,1844056802,3557935370,1326499344,4142603768,3885397889,1584245865,3326266917,2142836173,1858371508,3611272284,1279175494,4123357358,3837270743,1564721471,164299426,2955991370,2706223923,414607579,2209834945,978107433,724686416,2462715320,2183156074,1004243586,715579643,2472360723,140260361,2980573153,2698675608,421617264,1302961645,4099032581,3845074044,1557460884,3352688782,2116952934,1867729183,3601371895,2222754758,1032278062,754596439,2499928511,234942117,3086693709,2793824052,528319708,1274365761,4061043881,3816027856,1518873912,3246989858,2020800970,1762628531,3505670235,3223196809,2045103969,1754834200,3512958704,1247965674,4086934018,3806642299,1528765331,261609486,3060532198,2802936223,518697591,2246819181,1007707781,762121468,2492913428,213497176,3041029808,2755593417,499441441,2261110843,1061030867,776167850,2545465922,3274734047,2060165687,1807140942,3528266662,1229724860,4038575956,3788156205,1479636677,1222322711,4045468159,3764231046,1504067694,3265744756,2069664924,1780612837,3554288909,2270357136,1051278712,802445057,2519698665,221152243,3033880603,2779263586,475261322,0,2926088593,2275419491,701019378,3560000647,2052709654,1402038756,4261017717,1930665807,3715829470,4105419308,1524313021,2804077512,155861593,545453739,2397726522,3861331614,1213181711,1636244477,3488582252,840331801,2625561480,3048626042,467584747,2503254481,995897408,311723186,3170637091,1090907478,4016929991,3332753461,1758288292,390036349,3109546732,2426363422,1056427919,3272488954,1835443819,1152258713,3938878216,1680663602,3393484195,3817652561,1306808512,2954733749,510998820,935169494,2580880455,4044899811,1601229938,1991794816,3637571857,623446372,2336332021,2726898695,216120726,2181814956,744704829,95158223,2881711710,1446680107,4166125498,3516576584,2146575065,780072698,2148951915,2849952665,129384968,4199529085,1411853292,2112855838,3548843663,1567451573,4077254692,3670887638,1957027143,2304517426,657765539,251396177,2694091200,3361327204,1714510325,1341779207,3784408214,476611811,2986349938,2613617024,899690513,3142211371,354600634,1021997640,2458051545,1870338988,3239283261,3906682575,1186180958,960597383,2536053782,3202459876,277428597,3983589632,1125666961,1792074851,3300423154,1246892744,3829039961,3455203243,1671079482,2657312335,806080478,432241452,3081497277,3748049689,1896751752,1489409658,4138600427,190316446,2772397583,2365053693,580864876,2893360214,35503559,735381813,2243795108,2017747153,3593269568,4293150130,1368183843,1560145396,4069882981,3680356503,1966430470,2295112051,648294626,258769936,2701399425,804156091,2173100842,2823706584,103204425,4225711676,1438101421,2088704863,3524758222,3134903146,347226875,1031468553,2467456920,1860935661,3229814396,3914054286,1193487135,3385412645,1738661300,1315531078,3758225623,502792354,3012596019,2589468097,875607120,1271043721,3853125400,3429020650,1644831355,2683558414,832261023,408158061,3057348348,953223622,2528745559,3211865253,286899508,3974120769,1116263632,1799381026,3307794867,2917509143,59586950,709201268,2217549029,2043995280,3619452161,4269064691,1344032866,3740677976,1889445577,1498812987,4148069290,180845535,2762992206,2372361916,588238637,1921194766,3706423967,4112727661,1531686908,2796705673,148555288,554857194,2407195515,26248257,2952271312,2251333922,676868275,3584149702,2076793175,1375858085,4234771508,2493785488,986493953,319029491,3178008930,1083533591,4009621638,3342158964,1767759333,3887577823,1239362382,1612160956,3464433197,864482904,2649647049,3022443323,441336490,1706844275,3419730402,3793503504,1282724993,2978819316,535149925,908921239,2554697734,380632892,3100077741,2433735263,1063734222,3265180603,1828069930,1161729752,3948283721,2207997677,770953084,71007118,2857626143,1470763626,4190274555,3490330377,2120394392,4035494306,1591758899,1999168705,3644880208,616140069,2328960180,2736367686,225524183}
return lookup