import numpy as np
import itertools

# This file contains a dictionary that maps an integer n to the
# distribution of the Wilcoxon signed rank test statistic.
# The dictionary can be generated by the functions
# _generate_wilcoxon_exact_table and _generate_wilcoxon_exact_table_fast.
# The second function is about 20% faster.


def _generate_wilcoxon_exact_table(N):
    """
    Generate counts of the Wilcoxon ranksum statistic r_plus (sum of
    ranks of positive differences). For fixed n, simulate all possible states
    {0, 1}**n and compute the sum of the ranks over the indices that are equal
    to one (positive differences).
    Return a dictionary that maps n=3,...N to the corresponding list of counts
    """
    res_dict = {}
    for n in range(1, N+1):
        res = []
        ranks = np.arange(n) + 1
        M = n*(n + 1)/2
        for x in itertools.product((0, 1), repeat=n):
            # note that by symmetry, given a state x, we can directly compute
            # the positive ranksum of the inverted state (i.e. ~x or 1 - x),
            # therefore, it is enough to consider sequences starting with a one
            if x[0] == 1:
                rank_sum = np.sum(x * ranks)
                res.append(rank_sum)
                res.append(M - rank_sum)
        _, cnt = np.unique(res, return_counts=True)
        res_dict[n] = list(cnt)
    return res_dict


def _generate_wilcoxon_exact_table_fast(N):
    """
    Same functionality as _generate_wilcoxon_exact_table, but about 20% faster,
    but harder to follow.
    """
    res_dict = {}
    for n in range(1, N+1):
        ranks = np.arange(n) + 1
        M = int(n*(n + 1)/2)
        res = np.zeros(M + 1, dtype=int)
        for x in itertools.product((0, 1), repeat=n):
            if x[0] == 1:
                rank_sum = int(np.sum(x * ranks))
                res[rank_sum] += 1
        # flip array to get counts of symmetric sequences starting with 0
        res_dict[n] = list(res + np.flip(res))
    return res_dict


COUNTS = {
    1: [1, 1],
    2: [1, 1, 1, 1],
    3: [1, 1, 1, 2, 1, 1, 1],
    4: [1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1],
    5: [1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1],
    6: [1, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5, 5, 5, 4, 4, 4, 3, 2, 2, 1, 1, 1],
    7: [1, 1, 1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 8, 8, 8, 8, 8, 7, 7, 6, 5, 5, 4,
        3, 2, 2, 1, 1, 1],
    8: [1, 1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 13, 13, 14, 13,
        13, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 2, 1, 1, 1],
    9: [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 15, 17, 18, 19, 21, 21,
        22, 23, 23, 23, 23, 22, 21, 21, 19, 18, 17, 15, 13, 12, 10, 9, 8, 6,
        5, 4, 3, 2, 2, 1, 1, 1],
    10: [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 11, 13, 15, 17, 20, 22, 24, 27, 29,
         31, 33, 35, 36, 38, 39, 39, 40, 40, 39, 39, 38, 36, 35, 33, 31, 29,
         27, 24, 22, 20, 17, 15, 13, 11, 10, 8, 6, 5, 4, 3, 2, 2, 1, 1, 1],
    11: [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 14, 16, 19, 22, 25, 28, 32, 35,
         39, 43, 46, 49, 53, 56, 59, 62, 64, 66, 68, 69, 69, 70, 69, 69, 68,
         66, 64, 62, 59, 56, 53, 49, 46, 43, 39, 35, 32, 28, 25, 22, 19, 16,
         14, 12, 10, 8, 6, 5, 4, 3, 2, 2, 1, 1, 1],
    12: [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 17, 20, 24, 27, 31, 36, 40,
         45, 51, 56, 61, 67, 72, 78, 84, 89, 94, 100, 104, 108, 113, 115, 118,
         121, 122, 123, 124, 123, 122, 121, 118, 115, 113, 108, 104, 100, 94,
         89, 84, 78, 72, 67, 61, 56, 51, 45, 40, 36, 31, 27, 24, 20, 17, 15,
         12, 10, 8, 6, 5, 4, 3, 2, 2, 1, 1, 1],
    13: [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 21, 25, 29, 33, 39, 44,
         50, 57, 64, 71, 79, 87, 95, 104, 113, 121, 131, 140, 148, 158, 166,
         174, 182, 189, 195, 202, 207, 211, 215, 218, 219, 221, 221, 219, 218,
         215, 211, 207, 202, 195, 189, 182, 174, 166, 158, 148, 140, 131, 121,
         113, 104, 95, 87, 79, 71, 64, 57, 50, 44, 39, 33, 29, 25, 21, 18, 15,
         12, 10, 8, 6, 5, 4, 3, 2, 2, 1, 1, 1],
    14: [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 26, 30, 35, 41, 47,
         54, 62, 70, 79, 89, 99, 110, 122, 134, 146, 160, 173, 187, 202, 216,
         231, 246, 260, 274, 289, 302, 315, 328, 339, 350, 361, 369, 377, 384,
         389, 393, 396, 397, 397, 396, 393, 389, 384, 377, 369, 361, 350, 339,
         328, 315, 302, 289, 274, 260, 246, 231, 216, 202, 187, 173, 160, 146,
         134, 122, 110, 99, 89, 79, 70, 62, 54, 47, 41, 35, 30, 26, 22, 18,
         15, 12, 10, 8, 6, 5, 4, 3, 2, 2, 1, 1, 1],
    15: [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 31, 36, 43, 49,
         57, 66, 75, 85, 97, 109, 122, 137, 152, 168, 186, 203, 222, 243, 263,
         285, 308, 330, 353, 378, 401, 425, 450, 473, 496, 521, 542, 564, 586,
         605, 624, 642, 657, 671, 685, 695, 704, 712, 716, 719, 722, 719, 716,
         712, 704, 695, 685, 671, 657, 642, 624, 605, 586, 564, 542, 521, 496,
         473, 450, 425, 401, 378, 353, 330, 308, 285, 263, 243, 222, 203, 186,
         168, 152, 137, 122, 109, 97, 85, 75, 66, 57, 49, 43, 36, 31, 27, 22,
         18, 15, 12, 10, 8, 6, 5, 4, 3, 2, 2, 1, 1, 1],
    16: [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 37, 44, 51,
         59, 69, 79, 90, 103, 117, 132, 149, 167, 186, 208, 230, 253, 279,
         306, 334, 365, 396, 428, 463, 498, 534, 572, 610, 648, 689, 728, 767,
         808, 848, 887, 927, 965, 1001, 1038, 1073, 1105, 1137, 1166, 1192,
         1218, 1240, 1258, 1276, 1290, 1300, 1309, 1313, 1314, 1313, 1309,
         1300, 1290, 1276, 1258, 1240, 1218, 1192, 1166, 1137, 1105, 1073,
         1038, 1001, 965, 927, 887, 848, 808, 767, 728, 689, 648, 610, 572,
         534, 498, 463, 428, 396, 365, 334, 306, 279, 253, 230, 208, 186, 167,
         149, 132, 117, 103, 90, 79, 69, 59, 51, 44, 37, 32, 27, 22, 18, 15,
         12, 10, 8, 6, 5, 4, 3, 2, 2, 1, 1, 1],
    17: [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 45, 52,
         61, 71, 82, 94, 108, 123, 140, 159, 179, 201, 226, 252, 280, 311,
         343, 378, 416, 455, 497, 542, 588, 637, 689, 742, 797, 856, 914, 975,
         1038, 1101, 1166, 1233, 1299, 1366, 1434, 1501, 1568, 1635, 1700,
         1764, 1828, 1888, 1947, 2004, 2057, 2108, 2157, 2200, 2241, 2278,
         2310, 2338, 2363, 2381, 2395, 2406, 2410, 2410, 2406, 2395, 2381,
         2363, 2338, 2310, 2278, 2241, 2200, 2157, 2108, 2057, 2004, 1947,
         1888, 1828, 1764, 1700, 1635, 1568, 1501, 1434, 1366, 1299, 1233,
         1166, 1101, 1038, 975, 914, 856, 797, 742, 689, 637, 588, 542, 497,
         455, 416, 378, 343, 311, 280, 252, 226, 201, 179, 159, 140, 123, 108,
         94, 82, 71, 61, 52, 45, 38, 32, 27, 22, 18, 15, 12, 10, 8, 6, 5, 4,
         3, 2, 2, 1, 1, 1],
    18: [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 53,
         62, 73, 84, 97, 112, 128, 146, 167, 189, 213, 241, 270, 302, 338,
         375, 416, 461, 507, 558, 613, 670, 731, 797, 865, 937, 1015, 1093,
         1176, 1264, 1353, 1446, 1544, 1642, 1744, 1850, 1956, 2065, 2177,
         2288, 2401, 2517, 2630, 2744, 2860, 2971, 3083, 3195, 3301, 3407,
         3511, 3609, 3704, 3797, 3882, 3963, 4041, 4110, 4174, 4234, 4283,
         4328, 4367, 4395, 4418, 4435, 4441, 4441, 4435, 4418, 4395, 4367,
         4328, 4283, 4234, 4174, 4110, 4041, 3963, 3882, 3797, 3704, 3609,
         3511, 3407, 3301, 3195, 3083, 2971, 2860, 2744, 2630, 2517, 2401,
         2288, 2177, 2065, 1956, 1850, 1744, 1642, 1544, 1446, 1353, 1264,
         1176, 1093, 1015, 937, 865, 797, 731, 670, 613, 558, 507, 461, 416,
         375, 338, 302, 270, 241, 213, 189, 167, 146, 128, 112, 97, 84, 73,
         62, 53, 46, 38, 32, 27, 22, 18, 15, 12, 10, 8, 6, 5, 4, 3, 2, 2, 1,
         1, 1],
    19: [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54,
         63, 74, 86, 99, 115, 132, 151, 173, 197, 223, 253, 285, 320, 360,
         402, 448, 499, 553, 611, 675, 743, 815, 894, 977, 1065, 1161, 1260,
         1365, 1477, 1594, 1716, 1846, 1980, 2119, 2266, 2417, 2572, 2735,
         2901, 3071, 3248, 3427, 3609, 3797, 3986, 4176, 4371, 4565, 4760,
         4957, 5153, 5346, 5541, 5732, 5919, 6106, 6287, 6462, 6635, 6800,
         6958, 7111, 7255, 7389, 7518, 7636, 7742, 7842, 7929, 8004, 8071,
         8125, 8165, 8197, 8215, 8220, 8215, 8197, 8165, 8125, 8071, 8004,
         7929, 7842, 7742, 7636, 7518, 7389, 7255, 7111, 6958, 6800, 6635,
         6462, 6287, 6106, 5919, 5732, 5541, 5346, 5153, 4957, 4760, 4565,
         4371, 4176, 3986, 3797, 3609, 3427, 3248, 3071, 2901, 2735, 2572,
         2417, 2266, 2119, 1980, 1846, 1716, 1594, 1477, 1365, 1260, 1161,
         1065, 977, 894, 815, 743, 675, 611, 553, 499, 448, 402, 360, 320, 285,
         253, 223, 197, 173, 151, 132, 115, 99, 86, 74, 63, 54, 46, 38, 32, 27,
         22, 18, 15, 12, 10, 8, 6, 5, 4, 3, 2, 2, 1, 1, 1],
    20: [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54,
         64, 75, 87, 101, 117, 135, 155, 178, 203, 231, 263, 297, 335, 378,
         424, 475, 531, 591, 657, 729, 806, 889, 980, 1076, 1180, 1293, 1411,
         1538, 1674, 1817, 1969, 2131, 2300, 2479, 2668, 2865, 3071, 3288,
         3512, 3746, 3991, 4242, 4503, 4774, 5051, 5337, 5631, 5930, 6237,
         6551, 6869, 7192, 7521, 7851, 8185, 8523, 8859, 9197, 9536, 9871,
         10206, 10538, 10864, 11186, 11504, 11812, 12113, 12407, 12689, 12961,
         13224, 13471, 13706, 13929, 14134, 14326, 14502, 14659, 14800, 14925,
         15029, 15115, 15184, 15231, 15260, 15272, 15260, 15231, 15184, 15115,
         15029, 14925, 14800, 14659, 14502, 14326, 14134, 13929, 13706, 13471,
         13224, 12961, 12689, 12407, 12113, 11812, 11504, 11186, 10864, 10538,
         10206, 9871, 9536, 9197, 8859, 8523, 8185, 7851, 7521, 7192, 6869,
         6551, 6237, 5930, 5631, 5337, 5051, 4774, 4503, 4242, 3991, 3746,
         3512, 3288, 3071, 2865, 2668, 2479, 2300, 2131, 1969, 1817, 1674,
         1538, 1411, 1293, 1180, 1076, 980, 889, 806, 729, 657, 591, 531, 475,
         424, 378, 335, 297, 263, 231, 203, 178, 155, 135, 117, 101, 87, 75,
         64, 54, 46, 38, 32, 27, 22, 18, 15, 12, 10, 8, 6, 5, 4, 3, 2, 2, 1, 1,
         1],
    21: [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54,
         64, 76, 88, 102, 119, 137, 158, 182, 208, 237, 271, 307, 347, 393,
         442, 497, 558, 623, 695, 775, 860, 953, 1055, 1163, 1281, 1410, 1546,
         1693, 1852, 2020, 2200, 2394, 2597, 2814, 3046, 3289, 3546, 3819,
         4103, 4403, 4720, 5048, 5392, 5754, 6127, 6517, 6924, 7341, 7775,
         8225, 8686, 9161, 9652, 10151, 10664, 11191, 11724, 12268, 12824,
         13383, 13952, 14529, 15106, 15689, 16278, 16863, 17450, 18038, 18619,
         19198, 19775, 20340, 20898, 21450, 21985, 22511, 23025, 23518, 23997,
         24461, 24900, 25321, 25722, 26095, 26446, 26776, 27072, 27344, 27591,
         27804, 27990, 28149, 28271, 28365, 28431, 28460, 28460, 28431, 28365,
         28271, 28149, 27990, 27804, 27591, 27344, 27072, 26776, 26446, 26095,
         25722, 25321, 24900, 24461, 23997, 23518, 23025, 22511, 21985, 21450,
         20898, 20340, 19775, 19198, 18619, 18038, 17450, 16863, 16278, 15689,
         15106, 14529, 13952, 13383, 12824, 12268, 11724, 11191, 10664, 10151,
         9652, 9161, 8686, 8225, 7775, 7341, 6924, 6517, 6127, 5754, 5392,
         5048, 4720, 4403, 4103, 3819, 3546, 3289, 3046, 2814, 2597, 2394,
         2200, 2020, 1852, 1693, 1546, 1410, 1281, 1163, 1055, 953, 860, 775,
         695, 623, 558, 497, 442, 393, 347, 307, 271, 237, 208, 182, 158, 137,
         119, 102, 88, 76, 64, 54, 46, 38, 32, 27, 22, 18, 15, 12, 10, 8, 6,
         5, 4, 3, 2, 2, 1, 1, 1],
    22: [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54,
         64, 76, 89, 103, 120, 139, 160, 185, 212, 242, 277, 315, 357, 405,
         457, 515, 580, 650, 727, 813, 906, 1007, 1119, 1239, 1369, 1512, 1665,
         1830, 2010, 2202, 2408, 2631, 2868, 3121, 3393, 3682, 3988, 4316,
         4661, 5026, 5415, 5823, 6252, 6707, 7182, 7680, 8205, 8751, 9321,
         9918, 10538, 11181, 11852, 12545, 13261, 14005, 14770, 15557, 16370,
         17202, 18055, 18932, 19826, 20737, 21670, 22617, 23577, 24555, 25543,
         26539, 27550, 28565, 29584, 30611, 31637, 32662, 33689, 34709, 35721,
         36729, 37724, 38704, 39674, 40624, 41552, 42465, 43350, 44207, 45041,
         45842, 46609, 47347, 48046, 48705, 49329, 49910, 50445, 50942, 51390,
         51789, 52146, 52451, 52704, 52912, 53066, 53167, 53222, 53222, 53167,
         53066, 52912, 52704, 52451, 52146, 51789, 51390, 50942, 50445, 49910,
         49329, 48705, 48046, 47347, 46609, 45842, 45041, 44207, 43350, 42465,
         41552, 40624, 39674, 38704, 37724, 36729, 35721, 34709, 33689, 32662,
         31637, 30611, 29584, 28565, 27550, 26539, 25543, 24555, 23577, 22617,
         21670, 20737, 19826, 18932, 18055, 17202, 16370, 15557, 14770, 14005,
         13261, 12545, 11852, 11181, 10538, 9918, 9321, 8751, 8205, 7680, 7182,
         6707, 6252, 5823, 5415, 5026, 4661, 4316, 3988, 3682, 3393, 3121,
         2868, 2631, 2408, 2202, 2010, 1830, 1665, 1512, 1369, 1239, 1119,
         1007, 906, 813, 727, 650, 580, 515, 457, 405, 357, 315, 277, 242, 212,
         185, 160, 139, 120, 103, 89, 76, 64, 54, 46, 38, 32, 27, 22, 18, 15,
         12, 10, 8, 6, 5, 4, 3, 2, 2, 1, 1, 1],
    23: [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54,
         64, 76, 89, 104, 121, 140, 162, 187, 215, 246, 282, 321, 365, 415,
         469, 530, 598, 672, 754, 845, 944, 1053, 1173, 1303, 1445, 1601,
         1768, 1950, 2149, 2362, 2593, 2843, 3110, 3398, 3708, 4039, 4393,
         4773, 5176, 5606, 6065, 6550, 7065, 7613, 8189, 8799, 9444, 10120,
         10833, 11583, 12368, 13191, 14054, 14953, 15892, 16873, 17891, 18950,
         20052, 21190, 22371, 23593, 24852, 26152, 27493, 28869, 30284, 31737,
         33223, 34744, 36301, 37886, 39502, 41149, 42818, 44514, 46234, 47970,
         49726, 51499, 53281, 55074, 56876, 58679, 60484, 62291, 64087, 65877,
         67658, 69419, 71164, 72890, 74585, 76255, 77894, 79494, 81056, 82579,
         84052, 85478, 86855, 88172, 89433, 90636, 91770, 92841, 93846, 94774,
         95632, 96416, 97119, 97745, 98293, 98755, 99136, 99436, 99647, 99774,
         99820, 99774, 99647, 99436, 99136, 98755, 98293, 97745, 97119, 96416,
         95632, 94774, 93846, 92841, 91770, 90636, 89433, 88172, 86855, 85478,
         84052, 82579, 81056, 79494, 77894, 76255, 74585, 72890, 71164, 69419,
         67658, 65877, 64087, 62291, 60484, 58679, 56876, 55074, 53281, 51499,
         49726, 47970, 46234, 44514, 42818, 41149, 39502, 37886, 36301, 34744,
         33223, 31737, 30284, 28869, 27493, 26152, 24852, 23593, 22371, 21190,
         20052, 18950, 17891, 16873, 15892, 14953, 14054, 13191, 12368, 11583,
         10833, 10120, 9444, 8799, 8189, 7613, 7065, 6550, 6065, 5606, 5176,
         4773, 4393, 4039, 3708, 3398, 3110, 2843, 2593, 2362, 2149, 1950,
         1768, 1601, 1445, 1303, 1173, 1053, 944, 845, 754, 672, 598, 530, 469,
         415, 365, 321, 282, 246, 215, 187, 162, 140, 121, 104, 89, 76, 64, 54,
         46, 38, 32, 27, 22, 18, 15, 12, 10, 8, 6, 5, 4, 3, 2, 2, 1, 1, 1],
    24: [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54,
         64, 76, 89, 104, 122, 141, 163, 189, 217, 249, 286, 326, 371, 423,
         479, 542, 613, 690, 776, 872, 976, 1091, 1219, 1357, 1509, 1677, 1857,
         2054, 2270, 2502, 2755, 3030, 3325, 3644, 3990, 4360, 4758, 5188,
         5645, 6136, 6663, 7222, 7819, 8458, 9133, 9852, 10617, 11423, 12278,
         13184, 14136, 15141, 16203, 17315, 18485, 19716, 21001, 22348, 23760,
         25229, 26764, 28366, 30028, 31758, 33558, 35419, 37349, 39350, 41412,
         43543, 45745, 48006, 50335, 52732, 55186, 57705, 60288, 62923, 65618,
         68372, 71172, 74024, 76928, 79869, 82855, 85884, 88939, 92029, 95151,
         98288, 101448, 104627, 107808, 110999, 114195, 117380, 120558, 123728,
         126870, 129992, 133089, 136142, 139159, 142135, 145051, 147915,
         150722, 153453, 156116, 158707, 161206, 163622, 165951, 168174,
         170300, 172326, 174232, 176029, 177714, 179268, 180703, 182015,
         183188, 184233, 185148, 185917, 186552, 187052, 187402, 187615,
         187692, 187615, 187402, 187052, 186552, 185917, 185148, 184233,
         183188, 182015, 180703, 179268, 177714, 176029, 174232, 172326,
         170300, 168174, 165951, 163622, 161206, 158707, 156116, 153453,
         150722, 147915, 145051, 142135, 139159, 136142, 133089, 129992,
         126870, 123728, 120558, 117380, 114195, 110999, 107808, 104627,
         101448, 98288, 95151, 92029, 88939, 85884, 82855, 79869, 76928,
         74024, 71172, 68372, 65618, 62923, 60288, 57705, 55186, 52732, 50335,
         48006, 45745, 43543, 41412, 39350, 37349, 35419, 33558, 31758, 30028,
         28366, 26764, 25229, 23760, 22348, 21001, 19716, 18485, 17315, 16203,
         15141, 14136, 13184, 12278, 11423, 10617, 9852, 9133, 8458, 7819,
         7222, 6663, 6136, 5645, 5188, 4758, 4360, 3990, 3644, 3325, 3030,
         2755, 2502, 2270, 2054, 1857, 1677, 1509, 1357, 1219, 1091, 976, 872,
         776, 690, 613, 542, 479, 423, 371, 326, 286, 249, 217, 189, 163, 141,
         122, 104, 89, 76, 64, 54, 46, 38, 32, 27, 22, 18, 15, 12, 10, 8, 6,
         5, 4, 3, 2, 2, 1, 1, 1],
    25: [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54,
         64, 76, 89, 104, 122, 142, 164, 190, 219, 251, 289, 330, 376, 429,
         487, 552, 625, 705, 794, 894, 1003, 1123, 1257, 1403, 1563, 1741,
         1933, 2143, 2374, 2624, 2896, 3193, 3514, 3861, 4239, 4646, 5084,
         5559, 6068, 6615, 7205, 7835, 8509, 9234, 10005, 10828, 11708, 12642,
         13635, 14693, 15813, 16998, 18257, 19585, 20987, 22471, 24031, 25673,
         27404, 29219, 31124, 33124, 35216, 37403, 39694, 42082, 44571, 47169,
         49870, 52676, 55597, 58623, 61758, 65010, 68370, 71841, 75429, 79126,
         82933, 86857, 90888, 95025, 99276, 103629, 108084, 112648, 117305,
         122057, 126909, 131846, 136867, 141976, 147158, 152411, 157738,
         163125, 168564, 174063, 179602, 185178, 190794, 196430, 202082,
         207753, 213423, 219087, 224746, 230381, 235985, 241562, 247090,
         252561, 257980, 263325, 268588, 273774, 278859, 283837, 288713,
         293463, 298083, 302573, 306916, 311103, 315140, 319006, 322694,
         326211, 329537, 332666, 335607, 338337, 340855, 343168, 345259,
         347123, 348770, 350184, 351362, 352315, 353029, 353500, 353743,
         353743, 353500, 353029, 352315, 351362, 350184, 348770, 347123,
         345259, 343168, 340855, 338337, 335607, 332666, 329537, 326211,
         322694, 319006, 315140, 311103, 306916, 302573, 298083, 293463,
         288713, 283837, 278859, 273774, 268588, 263325, 257980, 252561,
         247090, 241562, 235985, 230381, 224746, 219087, 213423, 207753,
         202082, 196430, 190794, 185178, 179602, 174063, 168564, 163125,
         157738, 152411, 147158, 141976, 136867, 131846, 126909, 122057,
         117305, 112648, 108084, 103629, 99276, 95025, 90888, 86857, 82933,
         79126, 75429, 71841, 68370, 65010, 61758, 58623, 55597, 52676, 49870,
         47169, 44571, 42082, 39694, 37403, 35216, 33124, 31124, 29219, 27404,
         25673, 24031, 22471, 20987, 19585, 18257, 16998, 15813, 14693, 13635,
         12642, 11708, 10828, 10005, 9234, 8509, 7835, 7205, 6615, 6068, 5559,
         5084, 4646, 4239, 3861, 3514, 3193, 2896, 2624, 2374, 2143, 1933,
         1741, 1563, 1403, 1257, 1123, 1003, 894, 794, 705, 625, 552, 487,
         429, 376, 330, 289, 251, 219, 190, 164, 142, 122, 104, 89, 76, 64,
         54, 46, 38, 32, 27, 22, 18, 15, 12, 10, 8, 6, 5, 4, 3, 2, 2, 1, 1, 1]
}
