1pub const TABLE: [u32; 256] = [
2 0, 4067132163, 3778769143, 324072436, 3348797215, 904991772, 648144872,
3 3570033899, 2329499855, 2024987596, 1809983544, 2575936315, 1296289744,
4 3207089363, 2893594407, 1578318884, 274646895, 3795141740, 4049975192,
5 51262619, 3619967088, 632279923, 922689671, 3298075524, 2592579488,
6 1760304291, 2075979607, 2312596564, 1562183871, 2943781820, 3156637768,
7 1313733451, 549293790, 3537243613, 3246849577, 871202090, 3878099393,
8 357341890, 102525238, 4101499445, 2858735121, 1477399826, 1264559846,
9 3107202533, 1845379342, 2677391885, 2361733625, 2125378298, 820201905,
10 3263744690, 3520608582, 598981189, 4151959214, 85089709, 373468761,
11 3827903834, 3124367742, 1213305469, 1526817161, 2842354314, 2107672161,
12 2412447074, 2627466902, 1861252501, 1098587580, 3004210879, 2688576843,
13 1378610760, 2262928035, 1955203488, 1742404180, 2511436119, 3416409459,
14 969524848, 714683780, 3639785095, 205050476, 4266873199, 3976438427,
15 526918040, 1361435347, 2739821008, 2954799652, 1114974503, 2529119692,
16 1691668175, 2005155131, 2247081528, 3690758684, 697762079, 986182379,
17 3366744552, 476452099, 3993867776, 4250756596, 255256311, 1640403810,
18 2477592673, 2164122517, 1922457750, 2791048317, 1412925310, 1197962378,
19 3037525897, 3944729517, 427051182, 170179418, 4165941337, 746937522,
20 3740196785, 3451792453, 1070968646, 1905808397, 2213795598, 2426610938,
21 1657317369, 3053634322, 1147748369, 1463399397, 2773627110, 4215344322,
22 153784257, 444234805, 3893493558, 1021025245, 3467647198, 3722505002,
23 797665321, 2197175160, 1889384571, 1674398607, 2443626636, 1164749927,
24 3070701412, 2757221520, 1446797203, 137323447, 4198817972, 3910406976,
25 461344835, 3484808360, 1037989803, 781091935, 3705997148, 2460548119,
26 1623424788, 1939049696, 2180517859, 1429367560, 2807687179, 3020495871,
27 1180866812, 410100952, 3927582683, 4182430767, 186734380, 3756733383,
28 763408580, 1053836080, 3434856499, 2722870694, 1344288421, 1131464017,
29 2971354706, 1708204729, 2545590714, 2229949006, 1988219213, 680717673,
30 3673779818, 3383336350, 1002577565, 4010310262, 493091189, 238226049,
31 4233660802, 2987750089, 1082061258, 1395524158, 2705686845, 1972364758,
32 2279892693, 2494862625, 1725896226, 952904198, 3399985413, 3656866545,
33 731699698, 4283874585, 222117402, 510512622, 3959836397, 3280807620,
34 837199303, 582374963, 3504198960, 68661723, 4135334616, 3844915500,
35 390545967, 1230274059, 3141532936, 2825850620, 1510247935, 2395924756,
36 2091215383, 1878366691, 2644384480, 3553878443, 565732008, 854102364,
37 3229815391, 340358836, 3861050807, 4117890627, 119113024, 1493875044,
38 2875275879, 3090270611, 1247431312, 2660249211, 1828433272, 2141937292,
39 2378227087, 3811616794, 291187481, 34330861, 4032846830, 615137029,
40 3603020806, 3314634738, 939183345, 1776939221, 2609017814, 2295496738,
41 2058945313, 2926798794, 1545135305, 1330124605, 3173225534, 4084100981,
42 17165430, 307568514, 3762199681, 888469610, 3332340585, 3587147933,
43 665062302, 2042050490, 2346497209, 2559330125, 1793573966, 3190661285,
44 1279665062, 1595330642, 2910671697,
45];
46
47pub const TABLE16: [[u32; 256]; 16] = [
48 [
49 0, 4067132163, 3778769143, 324072436, 3348797215, 904991772,
50 648144872, 3570033899, 2329499855, 2024987596, 1809983544, 2575936315,
51 1296289744, 3207089363, 2893594407, 1578318884, 274646895, 3795141740,
52 4049975192, 51262619, 3619967088, 632279923, 922689671, 3298075524,
53 2592579488, 1760304291, 2075979607, 2312596564, 1562183871,
54 2943781820, 3156637768, 1313733451, 549293790, 3537243613, 3246849577,
55 871202090, 3878099393, 357341890, 102525238, 4101499445, 2858735121,
56 1477399826, 1264559846, 3107202533, 1845379342, 2677391885,
57 2361733625, 2125378298, 820201905, 3263744690, 3520608582, 598981189,
58 4151959214, 85089709, 373468761, 3827903834, 3124367742, 1213305469,
59 1526817161, 2842354314, 2107672161, 2412447074, 2627466902,
60 1861252501, 1098587580, 3004210879, 2688576843, 1378610760,
61 2262928035, 1955203488, 1742404180, 2511436119, 3416409459, 969524848,
62 714683780, 3639785095, 205050476, 4266873199, 3976438427, 526918040,
63 1361435347, 2739821008, 2954799652, 1114974503, 2529119692,
64 1691668175, 2005155131, 2247081528, 3690758684, 697762079, 986182379,
65 3366744552, 476452099, 3993867776, 4250756596, 255256311, 1640403810,
66 2477592673, 2164122517, 1922457750, 2791048317, 1412925310,
67 1197962378, 3037525897, 3944729517, 427051182, 170179418, 4165941337,
68 746937522, 3740196785, 3451792453, 1070968646, 1905808397, 2213795598,
69 2426610938, 1657317369, 3053634322, 1147748369, 1463399397,
70 2773627110, 4215344322, 153784257, 444234805, 3893493558, 1021025245,
71 3467647198, 3722505002, 797665321, 2197175160, 1889384571, 1674398607,
72 2443626636, 1164749927, 3070701412, 2757221520, 1446797203, 137323447,
73 4198817972, 3910406976, 461344835, 3484808360, 1037989803, 781091935,
74 3705997148, 2460548119, 1623424788, 1939049696, 2180517859,
75 1429367560, 2807687179, 3020495871, 1180866812, 410100952, 3927582683,
76 4182430767, 186734380, 3756733383, 763408580, 1053836080, 3434856499,
77 2722870694, 1344288421, 1131464017, 2971354706, 1708204729,
78 2545590714, 2229949006, 1988219213, 680717673, 3673779818, 3383336350,
79 1002577565, 4010310262, 493091189, 238226049, 4233660802, 2987750089,
80 1082061258, 1395524158, 2705686845, 1972364758, 2279892693,
81 2494862625, 1725896226, 952904198, 3399985413, 3656866545, 731699698,
82 4283874585, 222117402, 510512622, 3959836397, 3280807620, 837199303,
83 582374963, 3504198960, 68661723, 4135334616, 3844915500, 390545967,
84 1230274059, 3141532936, 2825850620, 1510247935, 2395924756,
85 2091215383, 1878366691, 2644384480, 3553878443, 565732008, 854102364,
86 3229815391, 340358836, 3861050807, 4117890627, 119113024, 1493875044,
87 2875275879, 3090270611, 1247431312, 2660249211, 1828433272,
88 2141937292, 2378227087, 3811616794, 291187481, 34330861, 4032846830,
89 615137029, 3603020806, 3314634738, 939183345, 1776939221, 2609017814,
90 2295496738, 2058945313, 2926798794, 1545135305, 1330124605,
91 3173225534, 4084100981, 17165430, 307568514, 3762199681, 888469610,
92 3332340585, 3587147933, 665062302, 2042050490, 2346497209, 2559330125,
93 1793573966, 3190661285, 1279665062, 1595330642, 2910671697,
94 ],
95 [
96 0, 329422967, 658845934, 887597209, 1317691868, 1562966443,
97 1775194418, 2054015301, 2635383736, 2394315727, 3125932886,
98 2851302177, 3550388836, 3225172499, 4108030602, 3883469565,
99 1069937025, 744974838, 411091311, 186800408, 1901039709, 1659701290,
100 1443537075, 1168652484, 2731618873, 2977147470, 2241069783,
101 2520160928, 3965408229, 4294560658, 3407766283, 3636263804,
102 2139874050, 1814657909, 1489949676, 1265388443, 822182622, 581114537,
103 373600816, 98970183, 3802079418, 4047354061, 3319402580, 3598223395,
104 2887074150, 3216496913, 2337304968, 2566056447, 1078858371,
105 1408010996, 1728782957, 1957280282, 247755615, 493284136, 696337329,
106 975428550, 3713716539, 3472378188, 4196393429, 3921508770, 2479927527,
107 2154965136, 3029696521, 2805405822, 4279748100, 3971309171,
108 3629315818, 3421531805, 2979899352, 2722054063, 2530776886,
109 2239369025, 1644365244, 1906417099, 1162229074, 1457827109, 747201632,
110 1059847191, 197940366, 409914617, 3235002245, 3547377650, 3885434731,
111 4097154844, 2388153945, 2650459694, 2837276343, 3133144768,
112 1573319741, 1315204170, 2055455955, 1763794084, 323786209, 15601046,
113 873047311, 665533816, 2157716742, 2470362481, 2816021992, 3027996063,
114 3457565914, 3719617709, 3914560564, 4210158659, 495511230, 237665993,
115 986568272, 695160359, 1392674658, 1084235541, 1950857100, 1743073275,
116 3210335367, 2902150384, 2552030313, 2344516638, 4057183579,
117 3799067948, 3600188853, 3308527042, 575477567, 837783368, 84420561,
118 380288934, 1825011427, 2137386644, 1266828813, 1478549114, 4223924985,
119 3898696334, 3699821079, 3475264096, 3041499941, 2800419666,
120 2450303947, 2175677372, 1725380929, 1970643254, 1100089775,
121 1378914776, 677206173, 1006616810, 253257843, 482013188, 3288730488,
122 3617886991, 3812834198, 4041319393, 2324458148, 2569990867,
123 2915654218, 3194733117, 1494403264, 1253068983, 2119694382,
124 1844797529, 395880732, 70922603, 819829234, 595526021, 2219317755,
125 2548728204, 2735548693, 2964304226, 3401742375, 3647004752,
126 3985066185, 4263891134, 425515587, 184435252, 1041885869, 767259354,
127 1473690527, 1148462056, 1888717681, 1664160518, 3146639482,
128 2821681165, 2630408340, 2406105315, 4110911910, 3869577681,
129 3527588168, 3252691263, 647572418, 893105077, 31202092, 310281051,
130 1746094622, 2075251305, 1331067632, 1559552647, 81018109, 393651338,
131 596708371, 808686692, 1247698209, 1509737814, 1830514127, 2126116280,
132 2579562309, 2321704754, 3196440491, 2905036764, 3611991705,
133 3303540462, 4027559543, 3819779584, 991022460, 682841355, 475331986,
134 267806181, 1973136544, 1715025111, 1390320718, 1098646585, 2785349316,
135 3047659187, 2168471082, 2464327261, 3901714200, 4214093679,
136 3486146550, 3697854337, 2069880831, 1761429384, 1545269009,
137 1337489254, 903200291, 645342804, 311463629, 20059834, 3863682119,
138 4125721648, 3238931625, 3534533854, 2831252891, 3143886316,
139 2407812469, 2619790594, 1150955134, 1463334409, 1675566736,
140 1887274727, 168841122, 431151061, 760577868, 1056433979, 3650022854,
141 3391911345, 4274773288, 3983099231, 2533657626, 2225476717,
142 2957098228, 2749572227,
143 ],
144 [
145 0, 2772537982, 1332695565, 3928932467, 2665391130, 1000289892,
146 3518101015, 1961911401, 944848581, 2635115707, 2000579784, 3531603638,
147 2794429151, 63834273, 3923822802, 1285642924, 1889697162, 3588485108,
148 1070411655, 2592914937, 4001159568, 1262308334, 2702412701, 72489443,
149 1223902031, 3987919153, 127668546, 2732426044, 3593332565, 1936487723,
150 2571285848, 1006839590, 3779394324, 1141205354, 2922096921, 191511399,
151 2140823310, 3671838064, 821366019, 2511642493, 3642082769, 2085902255,
152 2524616668, 859506082, 1204511179, 3800757173, 144978886, 2917507512,
153 2447804062, 883365088, 3733574803, 2076722925, 255337092, 2860101882,
154 1079472265, 3843482359, 2847389787, 217459237, 3872975446, 1134131240,
155 929635393, 2452131391, 2013679180, 3712474162, 3345318105, 1646531239,
156 2282410708, 759906474, 1505436867, 4244289213, 383022798, 3012945072,
157 4281646620, 1517628514, 2958814225, 354057839, 1642732038, 3299575928,
158 780486667, 2344934005, 3083337043, 310800173, 4171804510, 1575566624,
159 689527113, 2354629431, 1719012164, 3275200826, 2409022358, 718754280,
160 3237581211, 1706558437, 289957772, 3020551666, 1579627905, 4217808895,
161 639728589, 2204166579, 1766730176, 3423583166, 3103776727, 499010985,
162 4153445850, 1389436836, 510674184, 3140605814, 1360992005, 4099835259,
163 2158944530, 636449644, 3485578015, 1786782049, 1451427399, 4089615417,
164 434918474, 3165505076, 3361579613, 1830563875, 2268262480, 577987118,
165 1859270786, 3415452412, 566061711, 2231171313, 4027358360, 1431113446,
166 3210989205, 438459627, 2334619459, 778495293, 3293062478, 1628026672,
167 368694105, 2964865319, 1519812948, 4292285226, 3010873734, 372759544,
168 4229503883, 1498974709, 766045596, 2297004002, 1657257873, 3347459567,
169 4219800265, 1589942455, 3035257028, 296471226, 1700507347, 3222944941,
170 708115678, 2406837920, 3285464076, 1721083506, 2361091585, 704312447,
171 1560973334, 4165665384, 308658715, 3072610405, 1784908887, 3475119657,
172 621600346, 2152549412, 4106037325, 1375517235, 3151133248, 513009726,
173 1379054226, 4151517420, 492691615, 3088872161, 3438024328, 1772979446,
174 2206418053, 650303227, 448917981, 3212862371, 1437508560, 4042207662,
175 2216646087, 559859641, 3413116874, 1848743348, 579915544, 2278645094,
176 1845468437, 3367898987, 3159255810, 420477308, 4079040783, 1449175921,
177 1279457178, 3909314020, 53323159, 2792110057, 3533460352, 2011021822,
178 2649948557, 951227379, 1947453791, 3511835425, 998021970, 2654800172,
179 3939331397, 1334640443, 2778873672, 14921014, 1021348368, 2577471598,
180 1938806813, 3603843683, 2721984010, 125811828, 3981540359, 1209069177,
181 78755029, 2716870315, 1272899288, 4003427494, 2590970063, 1060012721,
182 3573564098, 1883361468, 2902854798, 138911472, 3798556291, 1193856253,
183 869836948, 2526624490, 2092432025, 3656804583, 2505519691, 806789173,
184 3661127750, 2138698296, 193566289, 2932343855, 1155974236, 3785840162,
185 3718541572, 2028331898, 2462786313, 931836279, 1132123422, 3862644576,
186 202737427, 2840860013, 3858059201, 1085595071, 2862226892, 266047410,
187 2066475995, 3731519909, 876919254, 2433035176,
188 ],
189 [
190 0, 3712330424, 3211207553, 1646430521, 2065838579, 2791807819,
191 3292861042, 419477706, 4131677158, 721537374, 1227047015, 2489772767,
192 2372293141, 1344534701, 838955412, 4014267180, 3915690301, 874584965,
193 1443074748, 2336634884, 2454094030, 1325607542, 757179215, 4033087991,
194 522244827, 3261429859, 2689069402, 2097306594, 1677910824, 3108456848,
195 3680878761, 102787601, 3609531531, 174112307, 1749169930, 3037175218,
196 2886149496, 1900187584, 325060345, 3458575425, 560035693, 4230274517,
197 2651215084, 1128529492, 1514358430, 2265377830, 3844367647, 945934247,
198 1044489654, 3808694030, 2166785591, 1550003343, 1164153925,
199 2552643325, 4194613188, 658578812, 3355821648, 356543720, 2002970065,
200 2854702953, 3005740963, 1851940123, 205575202, 3506798234, 2879807463,
201 1994650975, 348224614, 3380926174, 3498339860, 230802604, 1877167509,
202 2997282605, 1575107585, 2158466745, 3800375168, 1069593912, 650120690,
203 4219840330, 2577870451, 1155695819, 1120071386, 2676442210,
204 4255501659, 551577571, 971038505, 3836048785, 2257058984, 1539462672,
205 3028716860, 1774397316, 199339709, 3601073157, 3483679951, 316741239,
206 1891868494, 2911254006, 2088979308, 2714165716, 3286526189, 513917525,
207 128023199, 3672428583, 3100006686, 1703146406, 2328307850, 1468170802,
208 899681035, 3907363251, 4058323321, 748729281, 1317157624, 2479329344,
209 2515008081, 1218597097, 713087440, 4156912488, 4005940130, 864051482,
210 1369630755, 2363966107, 1671666103, 3202757391, 3703880246, 25235598,
211 411150404, 3317957372, 2816904133, 2057511293, 1386268991, 2414175111,
212 3989301950, 813842438, 696449228, 4106703476, 2531646285, 1268806133,
213 2766449369, 2040594529, 461605208, 3334874080, 3754335018, 42152338,
214 1621211307, 3185840659, 3150215170, 1719784122, 77814659, 3655790907,
215 3236317681, 497279817, 2139187824, 2730803400, 1300241380, 2428875100,
216 4075239525, 799183581, 916597271, 3957817519, 2311391638, 1417716526,
217 2240142772, 1489008396, 987954741, 3886503053, 4272417863, 602031871,
218 1103155142, 2625987966, 1942077010, 2927891690, 3433471443, 300103531,
219 149131169, 3584435481, 3078925344, 1791035032, 1826712713, 2980365873,
220 3548794632, 247719344, 398679418, 3397842882, 2829352699, 1977734211,
221 2594508655, 1205904855, 633482478, 4169631318, 3783736988, 1019384868,
222 1591745821, 2208675749, 4177958616, 608386144, 1180808537, 2602835937,
223 2183440171, 1600195987, 1027835050, 3758501394, 256046398, 3523698566,
224 2955269823, 1835039751, 1952498893, 2837802613, 3406292812, 373444084,
225 274868197, 3441921373, 2936341604, 1916841692, 1799362070, 3053829294,
226 3559339415, 157458223, 3861267459, 996404923, 1497458562, 2214907194,
227 2634315248, 1078058824, 576935537, 4280745161, 774079059, 4083558635,
228 2437194194, 1275136874, 1426174880, 2286164248, 3932590113, 925055641,
229 3630686645, 86133517, 1728102964, 3125110924, 2739261510, 2113960702,
230 472052679, 3244775807, 3343332206, 436378070, 2015367407, 2774907479,
231 3160736413, 1629530149, 50471196, 3729230756, 822300808, 3964074544,
232 2388947721, 1394727345, 1243701627, 2539965379, 4115022586, 671344706,
233 ],
234 [
235 0, 940666796, 1881333592, 1211347188, 3762667184, 3629437212,
236 2422694376, 2826309188, 3311864721, 4252394557, 3041252553,
237 2371140453, 623031585, 489937549, 1426090617, 1829832149, 2401395155,
238 3073576575, 4278238859, 3339833639, 1869078371, 1467396303, 524615739,
239 659845015, 1246063170, 1918109166, 979875098, 41343670, 2852181234,
240 2450635614, 3659664298, 3795018758, 464041303, 599382779, 1804233231,
241 1402668451, 4226616295, 3288097867, 2345653439, 3017718547,
242 3738156742, 3873362282, 2934792606, 2533101106, 1049231478, 110850010,
243 1319690030, 1991880834, 2492126340, 2895887144, 3836218332,
244 3703137392, 1959750196, 1289618840, 82687340, 1023204032, 1374543637,
245 1778167993, 567214157, 434008033, 2980602277, 2310606345, 3247095549,
246 4187738449, 928082606, 255853826, 1198765558, 2137184858, 3608466462,
247 4010130354, 2805336902, 2670159082, 4063650111, 3391557267,
248 2182397543, 3120943563, 309583759, 711110691, 1649475799, 1514172283,
249 3094547325, 2153931985, 3360805925, 4030774153, 1479980493,
250 1613224545, 672426645, 268764473, 2098462956, 1157984064, 221700020,
251 891793432, 2639380060, 2772488688, 3983761668, 3579973288, 754573305,
252 350793813, 1557856417, 1690988301, 3434897737, 4104982245, 3164519953,
253 2224017853, 3919500392, 3515857860, 2579237680, 2712495260, 165374680,
254 835323252, 2046408064, 1105779244, 2749087274, 2613760390, 3556335986,
255 3957853918, 1134428314, 2072997686, 868016066, 195932270, 1723643323,
256 1588451863, 379480803, 781124943, 2264468235, 3202901159, 4141601875,
257 3469392895, 1856165212, 1454619376, 511707652, 647062952, 2397531116,
258 3069576256, 4274369716, 3335838488, 2881871565, 2480189793,
259 3689349525, 3824578105, 1266704509, 1938886609, 1000521509, 62115977,
260 3783308431, 3650214691, 2443340759, 2847081595, 29690431, 970220947,
261 1911018855, 1240906443, 619167518, 485937330, 1422221382, 1825837034,
262 3298951598, 4239617538, 3028344566, 2358358362, 1963614219,
263 1293619111, 86556499, 1027199231, 2505039547, 2908664087, 3849126371,
264 3715919439, 2959960986, 2289828918, 3226449090, 4166966126,
265 1344853290, 1748613766, 537528946, 404448734, 4196925912, 3258543732,
266 2315968128, 2988159276, 443400040, 578605252, 1783586864, 1381896092,
267 1062144585, 123626981, 1332598033, 2004662973, 3742020857, 3877362517,
268 2938661793, 2537096205, 1509146610, 1642254430, 701587626, 297799430,
269 3115712834, 2175233774, 3381976602, 4052070838, 2626991203,
270 2760235983, 3971377979, 3567715479, 2094074579, 1153459583, 217306507,
271 887274023, 3604078113, 4005605773, 2800943481, 2665639637, 915693713,
272 243601213, 1186381769, 2124927077, 330749360, 732412444, 1670646504,
273 1535468868, 4092816128, 3420587180, 2211558488, 3149978612,
274 1113262757, 2051695881, 846845437, 174635601, 2719921173, 2584730553,
275 3527174989, 3928818913, 2268856628, 3207425688, 4145995372,
276 3473912256, 1736032132, 1600704552, 391864540, 793382768, 3447286646,
277 4117234906, 3176903726, 2236275586, 758961606, 355318378, 1562249886,
278 1695507762, 136208615, 806293323, 2017247167, 1076744211, 3898334807,
279 3494556155, 2558066959, 2691198627,
280 ],
281 [
282 0, 4012927769, 3683426499, 884788186, 3002414967, 1573215342,
283 1769576372, 2252995757, 1611012127, 2402710278, 3146430684,
284 1421530053, 3539152744, 1036207217, 159354795, 3863995570, 3222024254,
285 792484647, 461410557, 4105239524, 1928922953, 2647223376, 2843060106,
286 1178979475, 2685020193, 1329218360, 2072414434, 2495013883, 318709590,
287 4258231375, 3379806101, 641979532, 2247366285, 1791262100, 1584969294,
288 2974342487, 922821114, 3627109091, 3968696633, 62777888, 3857845906,
289 180512139, 1048489553, 3511600456, 1460091365, 3090633468, 2357958950,
290 1673261631, 1173890739, 2865253802, 2658436720, 1900342633,
291 4144828868, 406682333, 746696967, 3283212830, 637419180, 3402519989,
292 4268924527, 289600886, 2534083035, 2017157826, 1283959064, 2746728961,
293 235166699, 3778294002, 3582524200, 985174065, 3169938588, 1405159301,
294 1736297567, 2286790470, 1845642228, 2167548141, 3046040375,
295 1522436142, 3707204739, 868687770, 125555776, 3897278297, 3456658389,
296 557318348, 361024278, 4206141455, 2096979106, 2479699899, 2809265249,
297 1212258168, 2920182730, 1094588627, 1971507977, 2595403792, 486229181,
298 4090179492, 3346523262, 675778407, 2347781478, 1690314367, 1350364581,
299 3209463484, 956660241, 3593801992, 3800685266, 230273483, 3958789497,
300 80100960, 813364666, 3746209443, 1493393934, 3056797975, 2190459597,
301 1841277396, 1274838360, 2764838465, 2423315867, 2134947458,
302 4178135599, 372842806, 579201772, 3451224565, 737830215, 3301576286,
303 4034315652, 524725917, 2567918128, 1983854889, 1115943667, 2914228714,
304 470333398, 4080590031, 3347322645, 682916876, 2935849121, 1104014264,
305 1970348130, 2587970427, 2081337289, 2470364368, 2810318602,
306 1219650579, 3472595134, 567014311, 360134781, 4198978404, 3691284456,
307 859106545, 126363435, 3904392242, 1861333151, 2176965510, 3044872284,
308 1515027269, 3154288631, 1395848430, 1737375540, 2294174765, 251111552,
309 3787965337, 3581610051, 978019162, 2583470427, 1993132610, 1114636696,
310 2906679937, 722048556, 3292134709, 4035262191, 531979766, 4193958212,
311 382390877, 578165127, 3443946142, 1259310643, 2755650858, 2424516336,
312 2142455273, 1508938085, 3066100348, 2189177254, 1833720511,
313 3943015954, 70634763, 814286545, 3753471432, 972458362, 3603358307,
314 3799656889, 222970528, 2332278285, 1681118484, 1351556814, 3216995799,
315 302836797, 4248602404, 3380628734, 649078759, 2700729162, 1338617939,
316 2071296905, 2487554192, 1913320482, 2637864763, 2844153057,
317 1186349048, 3237987157, 802138188, 460546966, 4098033807, 3523271683,
318 1026602778, 160201920, 3871086553, 1626729332, 2412085357, 3145288631,
319 1414078638, 2986787868, 1563864837, 1770677471, 2260340678, 15987563,
320 4022573170, 3682554792, 877607089, 2549676720, 2026410409, 1282693747,
321 2739155306, 621661639, 3393038046, 4269894916, 296814109, 4160676527,
322 416188854, 745685612, 3275893109, 1158403544, 2856042177, 2659677467,
323 1907826178, 1475660430, 3099894167, 2356701773, 1665663316,
324 3842113017, 171022048, 1049451834, 3518838307, 938660497, 3636640136,
325 3967709778, 55449931, 2231887334, 1782025983, 1586185509, 2981834300,
326 ],
327 [
328 0, 1745038536, 3490077072, 3087365464, 2782971345, 3454265625,
329 1978047553, 501592201, 1311636819, 640602523, 2653660355, 4129851403,
330 3956095106, 2211320906, 1003184402, 1405636058, 2623273638,
331 4099462766, 1281205046, 610177022, 968572791, 1371018175, 3921503975,
332 2176731695, 3530950645, 3128240957, 40918629, 1785950893, 2006368804,
333 529919724, 2811272116, 3482564476, 1029407677, 1431875445, 3982350893,
334 2237593317, 2562410092, 4038617764, 1220354044, 549335860, 1937145582,
335 460673574, 2742036350, 3413314486, 3600202559, 3197474807, 110158511,
336 1855180391, 2701162779, 3372438995, 1896226955, 419761219, 81837258,
337 1826852866, 3571901786, 3169175954, 4012737608, 2267981952,
338 1059839448, 1462300944, 1254965657, 583953745, 2597001225, 4073206977,
339 2058815354, 313797554, 2863750890, 3266474530, 3747070635, 3075796579,
340 257006395, 1733474291, 882571817, 1553585889, 3835470777, 2359267185,
341 2440708088, 4185461552, 1098671720, 696208032, 3874291164, 2398081300,
342 921347148, 1592363140, 1124874253, 722408645, 2466931101, 4211690837,
343 2831220879, 3233950791, 2026330399, 281310679, 220317022, 1696786838,
344 3710360782, 3039080454, 1206682823, 804235279, 2548751703, 4293521823,
345 3792453910, 2316266974, 839522438, 1510552654, 163674516, 1640125788,
346 3653705732, 2982415564, 2887892037, 3290599565, 2082989525, 337955101,
347 3686235745, 3014939305, 196159473, 1672612665, 2119678896, 374642552,
348 2924601888, 3327315688, 2509931314, 4254707706, 1167907490, 765458026,
349 813319907, 1484352043, 3766230899, 2290037691, 4117630708, 2641175100,
350 627595108, 1298889644, 1351535397, 948824045, 2156434101, 3901472381,
351 3141792679, 3544244079, 1799727671, 54953727, 514012790, 1990204094,
352 3466948582, 2795914030, 1765143634, 20371610, 3107171778, 3509616906,
353 3436523907, 2765495627, 483616787, 1959806171, 655886593, 1327179209,
354 4145959057, 2669509721, 2197343440, 3942375448, 1392416064, 989706632,
355 3358952777, 2687934849, 406050009, 1882257425, 1842694296, 97936464,
356 3184726280, 3587194304, 2249748506, 3994770642, 1444817290,
357 1042089282, 603502027, 1274779907, 4093570139, 2617098387, 1416525807,
358 1013799719, 2221420159, 3966436023, 4052660798, 2576195318, 562621358,
359 1233897318, 440634044, 1916839540, 3393573676, 2722562020, 3215150957,
360 3617612709, 1873090301, 128334389, 2413365646, 3889833286, 1608470558,
361 937196758, 708430943, 1111154839, 4198471119, 2453453063, 3254056157,
362 2851592213, 301116749, 2045870469, 1679044876, 202841540, 3021105308,
363 3692119124, 327349032, 2072109024, 3280251576, 2877785712, 3059889913,
364 3730905649, 1717858153, 241648545, 1571753595, 900473523, 2376685547,
365 3853155107, 4165979050, 2420959074, 675910202, 1078640370, 2994899507,
366 3665929979, 1652872099, 176684907, 392318946, 2137088810, 3345225330,
367 2942778042, 4239357792, 2494323624, 749285104, 1151992376, 1498395313,
368 827104889, 2303322913, 3779774441, 786002069, 1188715613, 4276037893,
369 2531001805, 2335814980, 3812268428, 1530916052, 859619356, 1626639814,
370 150446350, 2968704086, 3639736478, 3306440727, 2903991519, 353505671,
371 2098281807,
372 ],
373 [
374 0, 1228700967, 2457401934, 3678701417, 555582061, 1747058506,
375 3009771555, 4200137988, 1111164122, 185039357, 3494117012, 2575270835,
376 1663469239, 706411408, 4049501433, 3093430750, 2222328244, 3444208787,
377 370078714, 1597148893, 2775288793, 3965187838, 924021143, 2117012656,
378 3326938478, 2406576201, 1412822816, 487164423, 3880816387, 2926375460,
379 1965585741, 1007945834, 218129817, 1144789182, 2675482583, 3594838768,
380 740157428, 1696701139, 3194297786, 4149829789, 1329291587, 101129316,
381 3712195341, 2491409962, 1848042286, 656055817, 4234025312, 3043124295,
382 2306239533, 3226079498, 453940835, 1379068740, 2825645632, 3780612967,
383 974328846, 1932486953, 3410847991, 2188449232, 1496683193, 269086622,
384 3931171482, 2741802941, 2015891668, 823422451, 436259634, 1396487701,
385 2289578364, 3242478683, 991775071, 1914778744, 2842014481, 3763981878,
386 1480314856, 285717199, 3393402278, 2206156929, 2032553349, 807022754,
387 3948853195, 2724383468, 2658583174, 3612000161, 202258632, 1160922607,
388 3211477227, 4132912588, 756267685, 1680852866, 3696084572, 2507258747,
389 1312111634, 118047029, 4249895985, 3026991382, 1864941183, 638894936,
390 385920683, 1581044620, 2239255781, 3427019202, 907881670, 2132890081,
391 2758137480, 3982076847, 1429973617, 470275926, 3343077439, 2390699288,
392 1948657692, 1025135931, 3864973906, 2942480245, 2474026783,
393 3662338616, 17718609, 1211244662, 2993366386, 4216805461, 538173244,
394 1764729371, 3511526341, 2557599458, 1127569803, 168371372, 4031783336,
395 3110886543, 1646844902, 722773697, 872519268, 2101209923, 2792975402,
396 4014280973, 354161673, 1545627950, 2271538759, 3461911392, 1983550142,
397 1057419161, 3829557488, 2910721495, 1462178003, 505114100, 3311397533,
398 2355337146, 2960629712, 4182500087, 571434398, 1798510777, 2439650749,
399 3629539482, 51570675, 1244568276, 4065106698, 3144738349, 1614045508,
400 688397411, 3545307495, 2590860352, 1093264169, 135634446, 956429309,
401 1883082458, 2876836275, 3796202644, 404517264, 1361054903, 2321845214,
402 3277387513, 2067461927, 839289344, 3913420137, 2692640846, 1512535370,
403 320538733, 3361705732, 2170810915, 3178756681, 4098590574, 789512199,
404 1714650400, 2624223268, 3579184387, 236094058, 1194262349, 4283235987,
405 3060827060, 1832125661, 604535290, 3729882366, 2540503513, 1277789872,
406 85326743, 771841366, 1732059249, 3162089240, 4114995775, 253550395,
407 1176543772, 2640586101, 3562559570, 1815763340, 621159595, 4265780162,
408 3078545125, 1294457825, 68921030, 3747553711, 2523094152, 2859947234,
409 3813353925, 940551852, 1899221899, 2339034767, 3260459944, 420621505,
410 1345212902, 3897315384, 2708483359, 2050271862, 856217425, 3377582677,
411 2154671986, 1529423899, 303387964, 587282639, 1782400488, 2977546881,
412 4165320614, 35437218, 1260439429, 2422489324, 3646438859, 1631206421,
413 671498546, 4081239643, 3128867708, 1076346488, 152814431, 3529458742,
414 2606971153, 2809606523, 3997912156, 890227509, 2083763730, 2255139606,
415 3478572593, 336742744, 1563309183, 3846976929, 2893039750, 1999949807,
416 1040757448, 3293689804, 2372782827, 1445547394, 521482405,
417 ],
418 [
419 0, 4097758792, 3985758817, 430902313, 3738157619, 720442491,
420 861804626, 3345010202, 3094606487, 1280124127, 1440884982, 2715614910,
421 1723609252, 2458052332, 2335042245, 2131967117, 1963693023,
422 2167752087, 2560248254, 1822728182, 2881769964, 1610254244,
423 1180011405, 2993380805, 3447218504, 960935680, 552188713, 3570888033,
424 330802043, 3884545331, 4263934234, 169389906, 3927386046, 506065398,
425 126287327, 4088933271, 886629773, 3236312005, 3645456364, 762833316,
426 1382339881, 2790916961, 3220508488, 1271650560, 2360022810,
427 2023080274, 1631243643, 2500074291, 2669458529, 1797415465,
428 1921871360, 2259925064, 1104377426, 3052249114, 2890050611,
429 1484552827, 661604086, 3545338046, 3405683863, 1052789471, 4188046533,
430 228479629, 338779812, 3759114476, 3519166861, 637333445, 1012130796,
431 3362600356, 252574654, 4214435318, 3801883103, 379778967, 1773259546,
432 2643402066, 2216694139, 1881065267, 3078490409, 1128324961,
433 1525666632, 2932933888, 2764679762, 1358396442, 1230532659,
434 3177621115, 2047240289, 2386083369, 2543301120, 1672045640, 481974469,
435 3901001357, 4046160548, 85284076, 3262487286, 910904510, 803487895,
436 3688535775, 1003822643, 3488335995, 3594830930, 578425370, 3843742720,
437 287574600, 143328865, 4239773737, 2208754852, 2006465260, 1849112261,
438 2584338573, 1567174295, 2841114847, 2969105654, 1153835710,
439 1323208172, 3135265700, 2739885965, 1467056581, 2417053663,
440 1680841111, 2105578942, 2310947830, 4138565499, 43231539, 456959258,
441 4009915218, 677559624, 3697044224, 3321063209, 835563873, 2791835115,
442 1381421987, 1274666890, 3217492418, 2024261592, 2358841744,
443 2503351737, 1627966449, 505149308, 3928301876, 4085919005, 129301333,
444 3235132751, 887808775, 759557934, 3648731494, 3546519092, 660422780,
445 1056066645, 3402406429, 229397511, 4187128399, 3762130534, 335763502,
446 1796236451, 2670637803, 2256649922, 1925146762, 3051333264,
447 1105293528, 1481538801, 2893064889, 1283400277, 3091330077,
448 2716792884, 1439706748, 2461065318, 1720596014, 2132883975,
449 2334125135, 4094480578, 3278474, 429722275, 3986939115, 717427441,
450 3741172921, 3344091280, 862723800, 963948938, 3444205506, 3571805163,
451 551271843, 3887821753, 327525873, 170568152, 4262756240, 2164736797,
452 1966708053, 1821809020, 2561167156, 1606975790, 2885048166,
453 2992200527, 1181191431, 2007645286, 2207574574, 2587616775,
454 1845833807, 2842033749, 1566255133, 1156850740, 2966090364,
455 3487158001, 1005000889, 575149200, 3598107352, 286657730, 3844659850,
456 4236760739, 146342123, 44150713, 4137646577, 4012930520, 453944208,
457 3698224522, 676379586, 838842347, 3317784995, 3134348590, 1324125030,
458 1464043343, 2742898951, 1679662877, 2418231637, 2307671420,
459 2108855092, 2646416344, 1770245520, 1881981369, 2215778289,
460 1131600363, 3075215267, 2934113162, 1524487618, 634317135, 3522182919,
461 3361682222, 1013048678, 4211157884, 255851828, 378597661, 3803064149,
462 3904276487, 478699087, 86463078, 4044981294, 913918516, 3259473020,
463 3689451605, 802571805, 1355119248, 2767957208, 3176440049, 1231713977,
464 2383067299, 2050256619, 1671127746, 2544219274,
465 ],
466 [
467 0, 3411442597, 2470478267, 1477900830, 594376071, 3896184354,
468 2955801660, 2071695257, 1188752142, 2374799531, 3583666869, 516690192,
469 1706532489, 2934039852, 4143390514, 1033987223, 2377504284,
470 1189326265, 519395239, 3584240642, 2933433243, 1703860286, 1033380384,
471 4140718469, 3413064978, 3753655, 1479523497, 2474231564, 3892463765,
472 592720688, 2067974446, 2954146443, 512219849, 3587285356, 2378652530,
473 1183916247, 1038790478, 4139570411, 2930388725, 1711035728,
474 1482502599, 2466990690, 3407720572, 4967385, 2066760768, 2959491045,
475 3899704827, 589741662, 2469530837, 1482979184, 7507310, 3408197323,
476 2959046994, 2064188151, 589297897, 3897131852, 3588810715, 515808382,
477 1185441376, 2382241221, 4135948892, 1037298169, 1707414503,
478 2928896066, 1024439698, 4133080631, 2924426281, 1696157580, 509788181,
479 3577002928, 2367832494, 1182022155, 2077580956, 2961384761,
480 3902136103, 600024194, 1488464667, 2481868990, 3422071456, 11456773,
481 2965005198, 2079070251, 603644469, 3903625616, 2480346633, 1484877228,
482 9934770, 3418483735, 4133521536, 1027011365, 1696598331, 2926998174,
483 3574463751, 509314722, 1179483324, 2367358745, 596143963, 3906868478,
484 2965958368, 2073990469, 15014620, 3417530745, 2477103975, 1492377794,
485 1699906645, 2919563248, 4128376302, 1027898955, 1178595794,
486 2372504183, 3581898857, 506006476, 2923280711, 1701561058, 1031616764,
487 4130030425, 2370882752, 1174845285, 504384891, 3578148574, 3907473993,
488 598813164, 2074596338, 2968627287, 3414829006, 14441579, 1489675893,
489 2476531152, 2048879396, 2974355585, 3915377311, 571052346, 1500651171,
490 2451858694, 3392315160, 23389373, 1019576362, 4153670543, 2944729489,
491 1691580980, 531166637, 3573452296, 2364044310, 1203638195, 4155161912,
492 1023198877, 1693072515, 2948351782, 3569862847, 529642266, 1200048388,
493 2362520225, 2976929334, 2049322387, 573626253, 3915820072, 2451383217,
494 1498109972, 22913546, 3389774255, 1687728621, 2949565000, 4158140502,
495 1015958515, 1207288938, 2359541711, 3568649681, 534986356, 574773987,
496 3910410566, 2969754456, 2052366589, 19869540, 3396949185, 2456792799,
497 1496962426, 3912067057, 578493524, 2054022730, 2973474287, 3393196662,
498 18246099, 1493210061, 2455169128, 2952236287, 1688336218, 1018629444,
499 4158748385, 2358966648, 1204585181, 534411459, 3565945702, 1192287926,
500 2353440019, 3562037005, 520496296, 1685957425, 2938884244, 4147980938,
501 1013666095, 30029240, 3399241245, 2458563587, 1507643302, 581386303,
502 3924900762, 2984755588, 2058467873, 3399813290, 32731919, 1508215057,
503 2461266612, 3922230573, 580781704, 2055797910, 2984150835, 2357191588,
504 1193908225, 524247583, 3563657658, 2937230883, 1682238854, 1012012952,
505 4144262205, 1503069311, 2462154714, 3403122116, 25296481, 2063233528,
506 2980842077, 3921342531, 585927654, 525201265, 3558577364, 2349690570,
507 1197151599, 1008769782, 4151763283, 2942311245, 1681285352,
508 3559051875, 527739334, 1197626328, 2352228477, 4149192676, 1008327745,
509 1678714463, 2941869562, 2465741165, 1504592584, 28883158, 3404645235,
510 2979351786, 2059614031, 584437073, 3917723380,
511 ],
512 [
513 0, 2540828609, 722442611, 3162402482, 1444885222, 3245262119,
514 2098244501, 3932249172, 2889770444, 995070477, 2268200127, 272632702,
515 4196489002, 1834000619, 3509505625, 1180645784, 1569766761,
516 3403762344, 1990140954, 3790525403, 193957775, 2633922638, 545265404,
517 3086082365, 4054767781, 1725902692, 3668001238, 1305523735,
518 2813454915, 817896834, 2361291568, 466584817, 3139533522, 743476499,
519 2418992033, 123671648, 3980281908, 2052046837, 3325153607, 1363158662,
520 387915550, 2154752223, 1007715949, 2875290028, 1090530808, 3597785657,
521 1779414155, 4252910410, 3870410683, 1908420730, 3451805384,
522 1523558665, 2964256093, 668926620, 2611047470, 214997999, 1250927223,
523 3724432822, 1635793668, 4143041733, 479236241, 2346805072, 933169634,
524 2700017187, 1940816725, 3839849620, 1486952998, 3486576103, 632402355,
525 2998945394, 247343296, 2580537089, 3750815385, 1222709592, 4104093674,
526 1676576811, 2307904639, 519971774, 2726317324, 905034445, 775831100,
527 3109014013, 87140175, 2453688462, 2015431898, 4015061787, 1395561897,
528 3294585448, 2181061616, 359771185, 2836382339, 1048458562, 3558828310,
529 1131323095, 4279300197, 1751189412, 3364878727, 1610485318,
530 3816841460, 1961989941, 2660289377, 165756064, 3047117330, 586065363,
531 1689361483, 4089473930, 1337853240, 3637506809, 850308781, 2782878060,
532 429995998, 2396045343, 2501854446, 40809263, 3188776349, 694233692,
533 3271587336, 1416724937, 3893358459, 2138970298, 958472482, 2924533475,
534 305051729, 2237616016, 1866339268, 4165985285, 1144097463, 3544218998,
535 3881633450, 1881993579, 3427966937, 1529047064, 2973905996, 640926605,
536 2588781887, 222059262, 1264804710, 3692205223, 1617754645, 4145876436,
537 494686592, 2316150337, 913557747, 2701279026, 3134045123, 767314946,
538 2445419184, 112448881, 3973220645, 2074312420, 3353153622, 1353508759,
539 385080847, 2172791246, 1039943548, 2861412541, 1089268969, 3617397544,
540 1810068890, 4237460059, 1551662200, 3406662585, 2004083979,
541 3758232266, 174280350, 2635250015, 560781293, 3055362092, 4030863796,
542 1731456629, 3679289543, 1279031046, 2791123794, 825023635, 2371007009,
543 438519264, 32293137, 2526885584, 719542370, 3180507043, 1475605495,
544 3229746230, 2096917124, 3951926597, 2916263133, 983782172, 2262646190,
545 296536687, 4224554555, 1824285178, 3502378824, 1202976905, 2498987519,
546 58880574, 3220970636, 680389453, 3270293273, 1436369112, 3923979882,
547 2123553195, 953016371, 2948339698, 331512128, 2226359937, 1859310293,
548 4188218644, 1172130726, 3534535783, 3378722966, 1578291031,
549 3798770149, 1964856868, 2675706480, 135134641, 3027473155, 587359426,
550 1700617562, 4063013531, 1314047017, 3642962920, 859991996, 2754844797,
551 407762639, 2403074318, 802357037, 3097692396, 81618526, 2477560223,
552 2043530699, 4005313034, 1388467384, 3316884345, 2213321441, 345861408,
553 2833449874, 1066595411, 3589515271, 1115840454, 4277940596,
554 1770899125, 1916944964, 3845371269, 1498274615, 3460050166, 610103458,
555 3006039907, 257092049, 2552438288, 3732678536, 1225642057, 4118003451,
556 1644316986, 2288194926, 521331375, 2741799965, 874347484,
557 ],
558 [
559 0, 829543472, 1659086944, 1402109008, 3318173888, 4105602288,
560 2804218016, 2522164368, 2388842353, 3205694273, 3967909649,
561 3723537185, 1269139377, 2060735361, 692465617, 406322145, 422172691,
562 676858915, 2076864627, 1253811267, 3706620115, 3986644195, 3188531379,
563 2407330947, 2538278754, 2788875090, 4121470722, 3302585138,
564 1384931234, 1677560722, 812644290, 18752498, 844345382, 52585494,
565 1353717830, 1640090742, 4153729254, 3336910038, 2507622534,
566 2751896758, 3157354327, 2369827687, 3738357559, 4020443911,
567 2046179223, 1216865191, 454402039, 711216071, 729442357, 436976645,
568 1234813013, 2028475493, 4005378293, 3754749125, 2355007637,
569 3173991589, 2769862468, 2489936756, 3355121444, 4136289044,
570 1625288580, 1370373044, 37504996, 860722132, 1688690764, 1440134268,
571 105170988, 926227484, 2707435660, 2417091772, 3280181484, 4075965660,
572 3938826045, 3686032141, 2284199773, 3109538669, 788719613, 510866381,
573 1306611613, 2089851821, 2106505311, 1291807855, 527241279, 773637135,
574 3091851423, 2302164143, 3668590847, 3957036239, 4092358446,
575 3265116958, 2433730382, 2692617086, 908804078, 123399134, 1422432142,
576 1706640318, 1458884714, 1736770650, 873953290, 90614842, 2469626026,
577 2722256026, 4056950986, 3231841530, 3633710875, 3924284203,
578 3128274811, 2332326731, 491870171, 740328427, 2142437307, 1321413515,
579 1339885689, 2125257801, 759078937, 474969129, 2316982457, 3144387721,
580 3908694233, 3649578217, 3250577160, 4040035128, 2740746088,
581 2452464472, 75009992, 889805816, 1721444264, 1475015576, 3377381528,
582 4164883624, 2880268536, 2598157512, 210341976, 1039680616, 1852454968,
583 1595665416, 1194072041, 1985856473, 634371977, 348023737, 2196457257,
584 3013251865, 3758681929, 3514383225, 3496417419, 3776367803,
585 2995040491, 2213897435, 362825803, 617716859, 2000937003, 1177695259,
586 1577439226, 1869880266, 1021732762, 228045738, 2613223226, 2863876874,
587 4179703642, 3360744298, 4213010622, 3396117646, 2583615710,
588 2827947246, 1054482558, 262927438, 1547274270, 1833458734, 1971300303,
589 1141797887, 396103599, 653122463, 2964911887, 2177442623, 3529203567,
590 3811216223, 3795101869, 3544546461, 2161574093, 2980500733, 670300269,
591 377629789, 1158696973, 1952547901, 1817608156, 1562881004, 246798268,
592 1069810572, 2844864284, 2564881196, 3413280636, 4194521932,
593 2917769428, 2627237092, 3473541300, 4269530244, 1747906580,
594 1499407396, 181229684, 1002212420, 596342693, 318415765, 1097392069,
595 1880689653, 3863750501, 3611161429, 2226097925, 3051248437,
596 3032512711, 2243013879, 3592671399, 3880912023, 1896294407,
597 1081539639, 333742183, 580211799, 983740342, 198409094, 1480656854,
598 1764807654, 4284874614, 3457428294, 2642827030, 2901902118,
599 2679771378, 2932589762, 4250515602, 3425201314, 1518157874,
600 1795986434, 949938258, 166673506, 299419523, 547951539, 1933275107,
601 1112194003, 3558840131, 3849208691, 3069984547, 2274224915,
602 2257832161, 3085049041, 3832569985, 3573658801, 1129617441,
603 1915046929, 565653569, 281470065, 150019984, 964742048, 1779611632,
604 1533240256, 3442888528, 4232551264, 2950031152, 2661561088,
605 ],
606 [
607 0, 819083365, 1638166730, 1366706351, 3276333460, 4087011825,
608 2733412702, 2453580091, 2206053849, 3014626748, 3805922579,
609 3524001142, 1077236813, 1894214696, 563160199, 289610978, 51846467,
610 868558118, 1655926153, 1382110700, 3227516119, 4035822770, 2717617181,
611 2435429496, 2154473626, 2964885759, 3788429392, 3508330549,
612 1126320398, 1945137515, 579221956, 307495329, 103692934, 922485475,
613 1737116236, 1465414185, 3311852306, 4122272631, 2764221400,
614 2484114365, 2236845919, 3045177146, 3841458069, 3559245808,
615 1176202955, 1992906414, 666836481, 393029220, 87631813, 904601504,
616 1688033039, 1414492010, 3329345105, 4137942580, 2815800987,
617 2533854974, 2252640796, 3063327353, 3890275030, 3610434227,
618 1158443912, 1977502701, 614990658, 343554855, 207385868, 1015958889,
619 1844970950, 1563049379, 3474232472, 4291210493, 2930828370,
620 2657279031, 2401353941, 3220437168, 4001738783, 3730278522,
621 1281958209, 2092636452, 768430475, 488597998, 256600143, 1067012138,
622 1861163141, 1581064416, 3422783963, 4241600958, 2913466641,
623 2641740148, 2352405910, 3169117683, 3985812828, 3711997241,
624 1333672962, 2141979751, 786058440, 503870637, 175263626, 983594991,
625 1809203008, 1526990629, 3376066078, 4192769659, 2828984020,
626 2555176625, 2299525715, 3118318134, 3903556249, 3631854332,
627 1246174151, 2056594338, 736324365, 456217448, 157635273, 968321708,
628 1757487619, 1477646950, 3391992669, 4211051320, 2877932439,
629 2606496754, 2316887824, 3133857653, 3955005402, 3681464255,
630 1229981316, 2038578913, 687109710, 405163563, 414771736, 678089341,
631 2031917778, 1238278839, 3689941900, 3944887273, 3126098758,
632 2324054819, 2613403585, 2870437796, 4200673035, 3400734574,
633 1485684309, 1751090736, 959041183, 167507706, 464516955, 729665342,
634 2047575953, 1255784436, 3639023311, 3895799466, 3108201989,
635 2308005472, 2563916418, 2818603751, 4185272904, 3382970925,
636 1536860950, 1799920499, 977195996, 183299001, 513200286, 776268027,
637 2134024276, 1340119089, 3722326282, 3976989039, 3162128832,
638 2359851429, 2649449799, 2906217762, 4233041293, 3432852968,
639 1587774675, 1852947638, 1057485849, 265669756, 495046109, 760477112,
640 2082848023, 1291289970, 3737726025, 3994752044, 3211615363,
641 2411685094, 2667345924, 2922266721, 4283959502, 3481940139,
642 1572116880, 1835442677, 1007741274, 214094143, 350527252, 607561585,
643 1967189982, 1167251387, 3618406016, 3883812581, 3053981258,
644 2262447663, 2543397581, 2806715048, 4131215879, 3337577058,
645 1423035225, 1677980476, 896908179, 94864374, 401834583, 656521778,
646 1985475229, 1183173368, 3569050563, 3832109990, 3038712585,
647 2244815724, 2492348302, 2757496811, 4113188676, 3321397025,
648 1472648730, 1729425023, 912434896, 112238261, 315270546, 572038647,
649 1936643416, 1136454973, 3514975238, 3780148323, 2955293900,
650 2163477673, 2444693579, 2707761198, 4027801729, 3233896676,
651 1392505311, 1647167930, 861634837, 59357552, 299743441, 554664116,
652 1887029275, 1085010046, 3533003077, 3796328736, 3006343567,
653 2212696554, 2459962632, 2725393773, 4077157826, 3285599655,
654 1374219420, 1631245561, 810327126, 10396723,
655 ],
656 [
657 0, 1409766726, 2819533452, 4228513738, 1441866729, 32929455,
658 4261382501, 2851658787, 2883733458, 4293202580, 65858910, 1475065880,
659 4262683707, 2853450109, 1444794039, 35298289, 1378416981, 103787539,
660 4196815833, 2921399967, 131717820, 1407094778, 2950131760, 4224722294,
661 4190813831, 2915953601, 1371804683, 96682317, 2889588078, 4164732968,
662 70596578, 1345479332, 2756833962, 4032210924, 207575078, 1482165600,
663 4053848387, 2779218949, 1504607183, 229191305, 263435640, 1538580542,
664 2814189556, 4089072306, 1514313361, 239453143, 4065082397, 2789960027,
665 4135128063, 2726190777, 1584898419, 175174709, 2743609366, 4153376080,
666 193364634, 1602344924, 1570458669, 161225067, 4120241825, 2710746087,
667 141193156, 1550662274, 2690958664, 4100165646, 1297060773, 424199907,
668 3846256937, 2974182511, 415150156, 1287251210, 2964331200, 3837218694,
669 3870151799, 2997518641, 1319337723, 446966717, 3009214366, 3881542360,
670 458382610, 1330972756, 526871280, 1264598966, 3077161084, 3815675194,
671 1251363097, 512826463, 3801670549, 3063920339, 3028626722, 3766646884,
672 478906286, 1217188584, 3782479563, 3044236173, 1232774215, 494792961,
673 3911082255, 3172545609, 1091619715, 353869509, 3169796838, 3907524512,
674 350349418, 1088863532, 1123821277, 385577883, 3941764177, 3203782935,
675 386729268, 1124749426, 3204689848, 3942972158, 3140917338, 4013018396,
676 322450134, 1195337616, 4006067123, 3133206261, 1187582271, 315507833,
677 282386312, 1154714318, 3101324548, 3973914690, 1160117345, 287484199,
678 3979040493, 3106669483, 2594121546, 3466097164, 848399814, 1721161856,
679 3480093859, 2607370725, 1734389295, 862452585, 830300312, 1702507998,
680 2574502420, 3446972242, 1686913905, 814421559, 3431131645, 2558901435,
681 3367493151, 2628815705, 1622766739, 884875733, 2638675446, 3376523440,
682 893933434, 1632567868, 1666554317, 928173195, 3411751745, 2673632775,
683 916765220, 1654910818, 2661945512, 3400353262, 1053742560, 1791590566,
684 2529197932, 3267832362, 1799353865, 1060676431, 3274792069,
685 2536901059, 2502726194, 3240871796, 1025652926, 1764060664,
686 3235754459, 2497373341, 1758665559, 1020546577, 1827024053, 954300915,
687 3303573049, 2431636351, 957812572, 1829788186, 2434377168, 3307139222,
688 3338955623, 2466463265, 1862975979, 990745773, 2465548430, 3337756104,
689 989585922, 1862055748, 3620779247, 2211963305, 2145263203, 735660837,
690 2183239430, 3592864320, 707739018, 2116577484, 2083713853, 674604667,
691 3560724913, 2151353591, 700698836, 2110031250, 2177727064, 3586797342,
692 2247642554, 3523156220, 771155766, 2045882992, 3490278995, 2215525141,
693 2013775071, 738234777, 773458536, 2048745262, 2249498852, 3524523426,
694 2079009153, 804027591, 3555033869, 2279790155, 1937851973, 663098115,
695 3683642569, 2408102287, 644900268, 1920413930, 2390675232, 3665402470,
696 3630367127, 2355385553, 1886235419, 610991709, 2375164542, 3650451256,
697 631015666, 1906040244, 564772624, 1974397526, 2309428636, 3718267098,
698 1951964409, 543148479, 3696637557, 2287035187, 2320234690, 3729567108,
699 574968398, 1984038664, 3753564971, 2344455789, 2008314279, 598942945,
700 ],
701 [
702 0, 1737424129, 3474848258, 2828207875, 2614592245, 4233723892,
703 1422555383, 860128758, 843281179, 1439534618, 4250831129, 2597352472,
704 2845110766, 3457813743, 1720257516, 17299181, 1686562358, 50862903,
705 2879069236, 3423985973, 4283524291, 2564790722, 810327745, 1472357312,
706 1455789357, 827025452, 2581098287, 4267086382, 3440515032, 2862410457,
707 34598362, 1702957275, 3373124716, 2927833453, 101725806, 1637796719,
708 1390038681, 894743448, 2647110811, 4199106970, 4216242039, 2629845622,
709 877872501, 1407039604, 1620655490, 118997123, 2944714624, 3356113537,
710 2911578714, 3389380443, 1654050904, 85470553, 912042159, 1372738990,
711 4181807789, 2664411052, 2680707393, 4165379136, 1356178243, 928734786,
712 69196724, 1670457013, 3405914550, 2894912695, 2549607977, 4034466600,
713 1491735595, 1063577898, 203451612, 1806602717, 3275593438, 2763221983,
714 2780077362, 3258605619, 1789486896, 220699185, 1046683591, 1508762310,
715 4051625413, 2532317380, 4084271135, 2499802398, 1013772829,
716 1541541660, 1755745002, 254310379, 2814079208, 3224735209, 3241310980,
717 2797372933, 237994246, 1772190727, 1525021169, 1030423792, 2516059123,
718 4067884786, 1593451077, 963960644, 2447890503, 4134085958, 3308101808,
719 2728615345, 170941106, 1841211315, 1824084318, 188197983, 2745477980,
720 3291108957, 4151235499, 2430611114, 947071401, 1610470568, 981255283,
721 1576155506, 4116790897, 2465186672, 2712356486, 3324361607,
722 1857469572, 154681733, 138393448, 1873889897, 3340914026, 2695671915,
723 2481468829, 4100376732, 1559613343, 997929630, 704883363, 1301108642,
724 3843969185, 2190519712, 2983471190, 3596277079, 2127155796, 424095573,
725 406903224, 2144216249, 3613205434, 2966675131, 2207734605, 3826886220,
726 1284153679, 721706062, 1317358741, 688632212, 2174269079, 3860220822,
727 3578973792, 3000775521, 441398370, 2109852003, 2093367182, 457753231,
728 3017524620, 3562354829, 3876699515, 2157920378, 671893369, 1333967480,
729 3809371855, 2223021006, 739482829, 1268605388, 2027545658, 525801787,
730 3083083320, 3494568761, 3511490004, 3066292437, 508620758, 2044596951,
731 1251645217, 756312608, 2240245027, 3792277538, 2273870073, 3758521848,
732 1217755899, 790333434, 475988492, 2077359885, 3544381454, 3033269519,
733 3050042338, 3527741155, 2060847584, 492369121, 773615895, 1234340886,
734 3774974741, 2257548820, 3186902154, 3665475979, 1927921288, 359089033,
735 639878783, 1101871998, 3913170045, 2393948540, 2411149201, 3896101520,
736 1084935571, 656683154, 341882212, 1944995941, 3682422630, 3170087527,
737 3648168636, 3204210621, 376395966, 1910613439, 1118117961, 623631688,
738 2377701963, 3929417546, 3945910695, 2361339046, 606874533, 1134745252,
739 1894142802, 392736339, 3220941136, 3631567953, 1962510566, 326596071,
740 3152311012, 3697971173, 4012771859, 2292250386, 540274705, 1203571984,
741 1186659325, 557057788, 2309423615, 3995729150, 3714939144, 3135472649,
742 309363466, 1979612683, 276786896, 2012320721, 3747779794, 3102501331,
743 2343103525, 3961917732, 1152718375, 591129382, 574365131, 1169350858,
744 3978422217, 2326731464, 3119226686, 3731186239, 1995859260, 293115965,
745 ],
746 [
747 0, 4060876286, 3790892301, 335044851, 3322195179, 872980757,
748 670089702, 3590114328, 2313498407, 2078876377, 1745961514, 2585612244,
749 1340179404, 3186462258, 2920672961, 1545200447, 371599551, 3827967297,
750 4157752754, 98453580, 3491923028, 573475242, 836168025, 3285902503,
751 2680358808, 1842285158, 2117560981, 2352703339, 1506257779,
752 2882250381, 3090400894, 1245694848, 743199102, 3728759936, 3451403379,
753 1068773773, 3930652053, 407171179, 196907160, 4189101414, 2779348569,
754 1470460839, 1146950484, 3058769578, 1672336050, 2443304780,
755 2186919871, 1884664385, 980056513, 3362157631, 3684570316, 697440562,
756 4235121962, 241359060, 496678951, 4019631577, 3012515558, 1099127576,
757 1383807979, 2692167189, 1972107789, 2273834995, 2491389696,
758 1718852350, 1486398204, 2861870850, 3110916081, 1264632335,
759 2661027351, 1821377513, 2137547546, 2372169444, 3514666459, 594640933,
760 814342358, 3263556904, 393814320, 3849661646, 4136455229, 75579843,
761 1321110083, 3165816765, 2940921678, 1564928688, 2293900968,
762 2058758998, 1766738853, 2604811867, 3344672100, 894937242, 649054313,
763 3567502743, 23005583, 4082304113, 3769328770, 312961404, 1960113026,
764 2262367868, 2501942927, 1730974577, 3000000361, 1088180887,
765 1394881124, 2703769498, 4247903397, 255709531, 482718120, 4006198358,
766 993357902, 3375988144, 3670089027, 684527805, 1660083005, 2432620227,
767 2198255152, 1896528846, 2767615958, 1459255848, 1157765851,
768 3071153957, 3944215578, 421263844, 182688023, 4176450793, 756242673,
769 3743372559, 3437704700, 1055602690, 2972796408, 1128089606,
770 1355098357, 2731091211, 2000021779, 2235163885, 2529264670,
771 1691191776, 953445087, 3403179809, 3642755026, 724306476, 4275095092,
772 215796682, 522496825, 3978864327, 2803330375, 1427857593, 1189281866,
773 3035565492, 1628684716, 2468334674, 2162666657, 1928044895, 787628640,
774 3707654046, 3473289069, 1024074387, 3908497035, 452649845, 151159686,
775 4212035192, 2642220166, 1869683064, 2089384331, 2391110773,
776 1534703725, 2843063699, 3129857376, 1216469150, 345521057, 3868472927,
777 4117517996, 123755346, 3533477706, 546347700, 862517831, 3244619705,
778 2338012217, 2035757511, 1789874484, 2560842954, 1298108626,
779 3209927980, 2896952799, 1588064289, 46011166, 4038205152, 3813309971,
780 289829869, 3300573173, 917942795, 625922808, 3611483910, 3920226052,
781 463858426, 140347913, 4199647223, 799886319, 3718333969, 3461949154,
782 1012214556, 1615644707, 2453718493, 2176361774, 1941219536,
783 2789762248, 1413769526, 1203505605, 3048211515, 4287614907, 226738757,
784 511419062, 3967266632, 965436240, 3414650542, 3632205405, 712180643,
785 1986715804, 2221337954, 2543750545, 1704099951, 2960018551,
786 1113735561, 1369055610, 2744528004, 3320166010, 938064772, 605150071,
787 3592279689, 65084049, 4058847087, 3793057692, 270105186, 1275107677,
788 3188495523, 2918511696, 1610152366, 2315531702, 2013804616,
789 1810913467, 2583450949, 3552812741, 567251771, 842527688, 3225157174,
790 365376046, 3888857040, 4097007395, 104813277, 1512485346, 2821372956,
791 3151158511, 1239339281, 2619481353, 1848512759, 2111205380,
792 2413460986,
793 ],
794];