Statistics

Problem Statement for "SubtreeSumHash"

Problem Statement

You are given a tree T with n nodes. The nodes are numbered 0 through n-1. Each node of the tree has a positive integer weight. You are given the weights in the int[] weight with n elements. You are also given a int[] p with n-1 elements that describes the edges of the tree: for each valid i, there is an undirected edge between nodes (i+1) and p[i]. The constraints ensure that this will produce a valid tree.

A subtree of T is any subgraph of T that is a tree. The weight of a subtree is the sum of the weights of its vertices. Let S be the multiset that contains the weights of all nonempty subtrees of T. (In other words, for each subtree of T we calculate its total weight and add the result to S. Note that S may contain some duplicates.)

You are also given an int x. This value is used to define the hash of the multiset S: Hash(S) is defined as the sum of x^s over all elements s of S. For example, if S = {2, 3, 3} then Hash(S) = x^2 + x^3 + x^3.

Please calculate and return the value Hash(S) modulo 1,000,000,007.

Definition

Class:
SubtreeSumHash
Method:
count
Parameters:
int[], int[], int
Returns:
int
Method signature:
int count(int[] weight, int[] p, int x)
(be sure your method is public)

Constraints

  • weight will contain between 1 and 50 elements, inclusive.
  • Each element in weight will be between 1 and 1,000,000,000, inclusive.
  • p will contain exactly |weight|-1 elements.
  • For each i, 0 <= p[i] <= i.
  • x will be between 1 and 1,000,000,000, inclusive.

Examples

  1. {1,2,3}

    {0,1}

    10

    Returns: 1102110

    The tree contains the edges 1-0 and 2-1, so it looks like this: 0 - 1 - 2. This tree has 6 subtrees: {0}, {1}, {2}, {0,1}, {1,2}, and {0,1,2}. Their weights are 1, 2, 3, 3, 5, and 6, respectively. Hence, S = {1, 2, 3, 3, 5, 6} and Hash(S) = x^1 + x^2 + 2*x^3 + x^5 + x^6 = 10 + 100 + 2*1000 + 100000 + 1000000 = 1102110.

  2. {123456789,987654321,111111111,999999999}

    {0,0,0}

    1

    Returns: 11

    There are 11 subtrees. Their weights do not matter: as x = 1, Hash(S) is simply the number of subtrees.

  3. {10}

    {}

    10

    Returns: 999999937

    The answer is 10^10 % (10^9+7).

  4. {3,7,6,8,9,4,2,1,5,6,7,8,9,6,1,2,3,5}

    {0,0,0,3,1,1,2,0,0,3,7,8,9,0,0,4,1}

    987654321

    Returns: 46327623

  5. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    546876

    Returns: 215468008

  6. {586367327, 423641709, 498364979, 576229054, 687114666, 53397788, 208547310, 270000160, 164990510, 676867429, 631047960, 225755141, 323792342, 98429752, 861248117, 569402214, 918087636, 727687544, 708206264, 399857334, 759374387, 596325972, 436276618, 740012400, 950325241, 969445704, 88309795, 401602123, 514518502, 846246281, 514958198, 225255989, 199655217, 56506887}

    {0, 0, 2, 3, 4, 2, 1, 7, 7, 0, 1, 7, 9, 2, 10, 1, 3, 3, 5, 9, 11, 4, 10, 21, 23, 16, 13, 21, 17, 5, 24, 20, 4}

    797108754

    Returns: 657139084

  7. {6595, 8199, 4244, 6810, 3551, 4834, 430, 3501, 7139, 7595, 9971, 8502, 8389, 964, 5626, 4897, 7247, 1632, 7738, 395, 4544, 1556, 6164, 7662, 7789, 5977, 3861, 9126, 2201, 9692, 4884, 1596, 2315, 9053, 1698, 2817, 8336, 1902, 7058, 3306, 7651, 1216, 7788, 1170, 9744, 3057, 5424, 2851}

    {0, 0, 1, 3, 3, 2, 3, 5, 6, 8, 10, 0, 10, 11, 13, 1, 6, 3, 5, 19, 0, 3, 5, 4, 1, 11, 9, 11, 11, 5, 12, 29, 18, 9, 1, 12, 24, 31, 11, 37, 36, 7, 18, 23, 24, 24, 32}

    344

    Returns: 785746490

  8. {30326, 41861}

    {0}

    390651

    Returns: 322864383

  9. {764, 616, 891, 589, 198, 691, 102, 417, 598, 417, 611, 322, 412, 376, 612, 163, 869, 312, 854, 868, 34, 337, 551, 395, 691, 131, 835, 632, 641, 855, 507, 839, 923, 189}

    {0, 1, 1, 2, 2, 3, 0, 3, 2, 8, 9, 7, 11, 6, 10, 4, 10, 11, 8, 2, 8, 15, 5, 21, 8, 5, 22, 26, 13, 6, 18, 28, 28}

    629484

    Returns: 360214661

  10. {3380002, 5724184, 777377, 9548349, 9924580, 8217378, 9092705, 6255761, 5707416, 9613545, 9496856, 423969, 7776178, 5943867, 149892, 1713586, 8571407, 8900646, 7346299, 5728102, 3546752, 6963524, 5602979, 2797200, 983390}

    {0, 1, 1, 3, 4, 1, 4, 5, 0, 6, 3, 6, 5, 1, 1, 10, 5, 6, 7, 1, 14, 5, 13, 10}

    22310423

    Returns: 808800440

  11. {239423224, 212958957, 492268256, 131027684, 119858847, 773851993, 614715827, 151214234, 976056966, 355313761, 244439435, 260253574, 344122296, 126580300, 806711529, 525349659, 532696424, 981087709}

    {0, 1, 1, 2, 2, 2, 6, 5, 8, 4, 1, 10, 4, 1, 6, 14, 12}

    597195026

    Returns: 800476688

  12. {5621, 6691, 7973, 5046, 2650, 2891, 3139, 8552, 5765, 3965, 6239, 3532, 6167, 3899, 6868, 2704, 8538, 437, 2708, 9240, 7307, 8976, 2023, 8684, 6634, 8053, 7473, 5712, 6927, 3370, 9733, 5275, 4110, 3452, 9845, 9481, 4456, 2194, 2848, 4417, 6125, 1344, 2090, 1996, 6379}

    {0, 0, 2, 0, 4, 3, 2, 3, 1, 4, 0, 5, 12, 7, 9, 7, 12, 13, 8, 7, 1, 19, 10, 4, 7, 15, 8, 17, 0, 29, 23, 13, 22, 4, 27, 32, 5, 3, 24, 22, 24, 33, 13, 9}

    95694

    Returns: 411614398

  13. {8474, 128, 871, 104, 2190, 7010, 1892, 6592, 5886, 423, 2146, 3689}

    {0, 1, 2, 3, 1, 3, 6, 6, 8, 7, 8}

    485522

    Returns: 596206402

  14. {10, 8, 9, 2, 8, 10}

    {0, 0, 0, 3, 2}

    849

    Returns: 722297016

  15. {75, 29, 25, 66, 76, 1, 18, 33, 67, 51, 69, 26, 51, 30, 14, 68, 28, 17, 17, 22, 19, 15, 10, 42, 44, 36}

    {0, 0, 0, 1, 4, 0, 4, 1, 1, 9, 9, 3, 2, 0, 9, 3, 15, 13, 7, 19, 14, 17, 18, 18, 24}

    495781

    Returns: 946265444

  16. {10, 9, 10, 6, 8, 3, 5, 9, 8, 8, 4, 1, 9, 9, 9, 7, 10, 5, 2, 9, 3, 1, 6, 5, 9, 3, 1, 6, 9, 10}

    {0, 0, 1, 0, 0, 0, 2, 0, 6, 7, 3, 5, 4, 13, 13, 2, 11, 16, 2, 19, 13, 6, 18, 11, 15, 2, 23, 8, 27}

    85839971

    Returns: 793394957

  17. {15699456, 79728124, 75623708, 98293016, 40791393, 96036116, 691833, 4803821, 39844449, 46998206, 31176175, 95203395, 68029762, 71933285, 24247049, 54153757, 56954304, 50543534, 88278431, 69260113, 86194687, 74698456, 23482899, 46490629, 20402330, 84878084, 65357765, 85745842}

    {0, 0, 2, 2, 4, 0, 1, 5, 7, 3, 9, 2, 8, 0, 2, 3, 7, 3, 10, 13, 2, 19, 3, 7, 23, 12, 21}

    5082680

    Returns: 480347144

  18. {3422, 632, 3068, 120, 2459, 3694, 8779, 2395, 3411, 9109, 625, 4933, 9904, 7786, 8646, 8838, 9802, 9310, 6469, 7894, 9912, 3674, 2081, 2998, 9690, 8291, 6048, 9781, 1717, 5696, 4428, 3069, 5495, 7380, 3589, 3633, 6015, 5508, 3181, 1487}

    {0, 1, 0, 1, 4, 0, 3, 7, 6, 7, 6, 11, 6, 2, 5, 11, 0, 7, 8, 7, 4, 19, 12, 5, 12, 23, 25, 7, 8, 19, 25, 29, 29, 30, 21, 25, 34, 36, 1}

    9

    Returns: 414463351

  19. {7636828, 5296558, 5135496, 3786894, 3825453, 1827596, 7882856, 5495874, 1638383, 7168862}

    {0, 0, 0, 0, 1, 0, 3, 1, 0}

    4

    Returns: 665574422

  20. {4012328, 68521888, 20252606, 75774455, 40072005, 48874812}

    {0, 0, 1, 3, 2}

    6785348

    Returns: 951035520

  21. {46537150, 17420027, 53189074, 97706681, 51512795, 46509745, 77912036, 77740124, 71445569, 71812849, 29565410, 48970372, 30077818, 57761617, 53397987, 17642253, 87885221, 225309, 22716595, 50834550, 31201793, 22450333, 6201544, 15008938, 69983484, 64686616, 95894816, 20706468, 13320163, 23945630, 91666267, 163111, 60693236, 93558824, 53861002, 46242288, 16343770, 66171605, 48224055, 63508057, 18105672, 47466121, 963677, 38780383, 6328360, 71482894, 8787926, 14659469}

    {0, 1, 2, 2, 4, 2, 0, 5, 0, 9, 0, 6, 0, 7, 7, 5, 2, 8, 9, 19, 10, 19, 0, 21, 0, 19, 16, 9, 16, 19, 24, 2, 16, 20, 17, 33, 20, 15, 31, 15, 40, 0, 12, 40, 41, 20, 17}

    410

    Returns: 66131400

  22. {32988200, 69698754}

    {0}

    73451

    Returns: 683143952

  23. {5978, 1106, 7934, 6835, 8396, 5781, 4079, 9871, 3636, 2579, 3606, 2065, 9467, 621, 9365, 5490, 9497, 6961, 6249, 2122, 899, 4805, 8788, 9787, 3035, 1401, 2327, 4987, 8460, 1413, 5049, 2590, 8841, 4448, 8167, 6692, 5070, 5113, 2151, 7754, 6304, 5310, 2870, 6404, 7013, 5756, 354}

    {0, 0, 2, 1, 0, 1, 5, 3, 2, 2, 6, 1, 2, 13, 8, 0, 14, 4, 4, 5, 3, 18, 7, 9, 1, 10, 15, 14, 19, 28, 23, 13, 31, 19, 12, 18, 4, 4, 3, 19, 9, 28, 3, 35, 30, 23}

    9

    Returns: 226023570

  24. {2312, 7899, 6303, 9029, 1119, 369, 3240, 3044, 8284, 9959, 4798}

    {0, 0, 2, 2, 0, 1, 5, 1, 6, 9}

    8819481

    Returns: 872061618

  25. {290801, 381980, 811574, 174610, 306434, 665499, 892539, 952982, 750757, 586157, 414338, 250035, 303963}

    {0, 0, 0, 3, 1, 1, 0, 4, 3, 0, 1, 1}

    3934198

    Returns: 221283189

  26. {58906182, 89049374, 24006838, 58578238, 21663629, 83926691, 6760394, 53317502, 57288324, 67567455, 28777328, 85345119, 99530349, 41076593, 30122823, 21273670, 98475310, 72601466, 11991219, 17195074, 23317404, 11429544, 38101194, 85316669, 88743943, 85087321, 62996850, 53721407, 70603480, 2792966, 55713961, 11722189, 52903372, 58356629, 57217689, 28559433, 76212506}

    {0, 1, 1, 3, 0, 4, 4, 0, 8, 3, 9, 9, 10, 6, 5, 8, 5, 9, 0, 17, 0, 17, 5, 1, 24, 24, 5, 1, 5, 25, 29, 15, 7, 16, 27, 22}

    755729047

    Returns: 604986445

  27. {46765, 11672, 46844, 38544, 79158, 59800, 39193, 30272}

    {0, 0, 1, 2, 2, 5, 0}

    658447

    Returns: 80988925

  28. {7, 3, 1, 9, 10, 10, 7, 9, 4, 1, 2, 3, 8, 9, 2, 9, 8, 7, 2, 6, 5, 1, 9, 6, 1, 8, 5}

    {0, 1, 1, 3, 4, 0, 4, 6, 6, 8, 9, 10, 9, 12, 4, 15, 14, 17, 15, 16, 5, 21, 5, 7, 5, 17}

    79572

    Returns: 564828323

  29. {4949, 5825, 1976, 8176, 4883, 5759, 3895, 2878, 9773, 9538, 4712, 4312, 3660, 9372, 4007, 7965, 5649, 3661, 2961, 7596, 7624}

    {0, 0, 1, 2, 3, 5, 4, 6, 3, 5, 5, 4, 5, 5, 4, 3, 13, 15, 0, 0}

    12070

    Returns: 340217067

  30. {5629752, 9167420}

    {0}

    683422

    Returns: 54010156

  31. {501686392, 54726221, 217773274, 85339043, 186178701, 568606992, 947917029, 631190939, 527447288, 942533969, 657472928, 726453742, 72567252, 142848174, 258672894, 594654672, 780383036, 158020932, 921858104, 172720665, 534482510}

    {0, 0, 2, 2, 4, 0, 4, 7, 6, 4, 1, 11, 1, 7, 7, 14, 1, 11, 7, 19}

    1865

    Returns: 795227711

  32. {504328138}

    {}

    13030684

    Returns: 527775038

  33. {176877, 418470, 700429, 786224, 92808, 873693, 993418, 463170}

    {0, 0, 0, 3, 3, 2, 2}

    54

    Returns: 121001502

  34. {2, 5, 10, 7, 10, 7, 8, 9, 10, 8, 6, 10, 5, 1, 5, 7, 3, 1, 7, 2, 3, 5, 3, 10, 2, 3, 1, 2, 9, 8, 3, 3, 4, 5, 9, 4, 1, 8, 8, 10, 9, 6, 6, 9, 5, 7, 6, 10}

    {0, 0, 0, 2, 1, 4, 0, 2, 3, 7, 2, 1, 7, 12, 13, 10, 10, 5, 5, 3, 17, 15, 18, 0, 22, 18, 18, 14, 24, 23, 8, 17, 8, 17, 5, 22, 36, 21, 31, 37, 2, 16, 9, 17, 42, 5, 12}

    4

    Returns: 344625454

  35. {815, 577, 842}

    {0, 0}

    6534366

    Returns: 168709393

  36. {28161, 64371, 68847, 11382, 47071, 90619, 34745, 41580, 36893, 98067, 97573, 42645, 89090, 67864, 14984, 86742, 98464, 69916, 79301, 35682, 61625, 10260, 11506, 53416, 38327, 73940, 40904, 38538, 83400, 88430, 4718, 51949, 67304, 11244, 80348}

    {0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0}

    50061

    Returns: 371347412

  37. {385, 603, 829, 753, 217, 456, 184, 415, 523, 66, 772, 367, 203, 537, 432, 85, 227, 259, 779, 537, 663, 73, 639, 744, 979, 712, 883, 477}

    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    568439926

    Returns: 692752371

  38. {8972263, 79804380, 99006812, 20237296, 83020231, 20979332, 7294622, 60205769, 84799826, 84863105, 81440210, 67770138, 42525610, 77937625, 54006557, 4596145, 69946415, 92726599, 47636673}

    {0, 1, 2, 2, 2, 0, 2, 2, 1, 0, 2, 1, 0, 1, 1, 1, 1, 2}

    3

    Returns: 398411400

  39. {839527194, 998157691, 673902080, 469923242, 723674569, 961998125, 837460301, 795268810, 592469842, 960924500, 962529685, 244192024, 938423614, 937206184, 527280775, 347319379, 285804990, 751638224, 170231271, 140983136, 723062671, 295915454, 728440437, 623209173, 876498735, 149135111, 62665467, 878088595, 625625922, 779511901, 95899682, 14616084, 946309886, 813090330, 829768531, 182238224}

    {0, 1, 0, 2, 4, 3, 4, 2, 0, 4, 1, 4, 3, 2, 1, 2, 2, 2, 1, 3, 4, 1, 2, 1, 2, 3, 2, 2, 4, 3, 1, 0, 4, 1, 1}

    150382

    Returns: 139029256

  40. {8720, 3618, 5360, 5003, 5625, 9464, 671, 1285, 5864, 5562, 321, 9654, 2296, 4984, 8449, 5809, 2142, 9563, 1404, 8322, 1358, 4761, 478, 1605, 5323, 5121, 4873, 9035, 1695, 1624, 8414}

    {0, 1, 2, 3, 2, 4, 1, 0, 2, 0, 4, 2, 4, 4, 1, 3, 1, 4, 4, 1, 2, 3, 2, 0, 3, 0, 3, 3, 1, 2}

    399104

    Returns: 182916197

  41. {23691, 67491, 3651, 62152, 77077, 45295, 17346, 9919}

    {0, 1, 0, 1, 2, 0, 1}

    8

    Returns: 833815815

  42. {37, 49, 8, 28, 14, 39, 7, 94, 76, 63, 59, 7, 36, 9, 82, 43, 93, 38, 2, 93, 31}

    {0, 1, 2, 0, 1, 2, 1, 2, 2, 0, 0, 2, 0, 1, 0, 1, 1, 0, 2, 0}

    34832

    Returns: 719496658

  43. {9, 4, 6, 10, 5, 7, 1, 5, 2, 5, 6, 7, 2, 2, 3, 5, 2, 2, 4}

    {0, 1, 2, 1, 3, 0, 0, 3, 1, 3, 3, 1, 2, 2, 3, 1, 1, 0}

    497428

    Returns: 284971437

  44. {246, 813, 620, 486, 377, 521, 931, 533, 546, 70, 561, 603, 376, 575, 703, 42, 159, 91, 970, 600, 379, 643, 824, 600, 113, 481, 460, 634, 620, 92, 102, 24, 44, 803, 344}

    {0, 1, 0, 2, 2, 2, 0, 0, 3, 2, 0, 0, 2, 4, 3, 4, 3, 1, 3, 3, 0, 4, 2, 1, 4, 4, 0, 3, 1, 2, 2, 4, 2, 3}

    6377

    Returns: 975806006

  45. {1589, 256, 6042, 1850, 9837, 4416, 6097, 6245, 9268, 8136, 1747, 9475, 6561, 8277, 568, 9875, 649, 1839, 2884, 6677, 511, 4671, 955, 5035, 5382, 6438, 6018, 175, 8556}

    {0, 0, 2, 3, 4, 5, 3, 2, 3, 5, 4, 5, 2, 0, 2, 0, 2, 4, 3, 3, 0, 4, 5, 4, 3, 4, 5, 5}

    175

    Returns: 83360490

  46. {25709886, 74167873, 35600846, 69066286, 94614204, 34923865, 28311075, 17177177, 10200895, 93142344, 45905426, 16574597, 65530059, 17273205, 68648616, 98219175, 40731934, 48799817, 52854510, 84377909, 64988804, 79037816, 984887, 13435775, 21743204, 94588961, 52787387, 2015053, 53073181, 22707270, 80519269, 19040866, 65285617, 94062592, 27602605, 77798851, 16037014, 53631699, 63057400, 77802767, 65429839, 4773963, 5647899}

    {0, 0, 1, 1, 4, 3, 0, 1, 4, 2, 2, 3, 1, 2, 0, 1, 3, 2, 1, 0, 3, 4, 3, 1, 2, 2, 0, 2, 3, 4, 1, 0, 4, 1, 2, 4, 2, 2, 3, 0, 4, 2}

    67760

    Returns: 7963852

  47. {36860, 94073, 31896, 5980, 75025, 2258, 56739, 51690, 20796, 74414, 88430, 25736, 25946, 46528, 99613, 55247, 93145, 35065, 22383, 16826, 83539, 37635, 11745, 30655, 29241, 56949, 70018, 48387, 34127, 66077, 97479, 10387, 43938, 73800, 15706, 86385, 34319, 80832, 4081, 33643, 71982, 11209}

    {0, 0, 1, 2, 2, 2, 1, 2, 2, 0, 2, 3, 3, 0, 3, 0, 1, 3, 3, 2, 0, 2, 0, 1, 2, 2, 3, 2, 0, 2, 3, 3, 2, 3, 2, 1, 3, 2, 3, 3, 0}

    263227

    Returns: 578941710

  48. {214, 425, 157, 445, 481, 945, 781, 788, 24, 834, 51, 140, 944, 145, 410, 779, 795, 949, 353, 400, 85, 558, 215, 616, 899, 682, 554, 851, 123, 632, 153, 611, 729, 142, 208, 43, 608, 392, 192, 975, 312, 905, 429, 795, 125}

    {0, 1, 2, 0, 3, 2, 0, 4, 4, 0, 4, 4, 2, 0, 4, 0, 0, 0, 2, 3, 0, 3, 4, 0, 2, 2, 0, 0, 4, 0, 3, 0, 0, 3, 1, 4, 2, 1, 1, 2, 0, 4, 2, 0}

    93

    Returns: 246756494

  49. {3, 4, 7, 1, 9, 9, 6, 1, 7, 9, 5, 5, 2, 2, 8, 10, 8, 2, 10, 5, 7, 2, 10, 1, 6, 1, 6, 5, 6, 7, 8, 2, 5, 4, 4, 5, 1, 2, 8, 7, 5, 1, 9, 8, 9, 7, 10, 10, 9}

    {0, 1, 2, 0, 0, 0, 2, 1, 0, 3, 2, 3, 2, 2, 0, 3, 0, 3, 1, 1, 3, 3, 1, 3, 3, 2, 3, 2, 0, 0, 3, 1, 2, 1, 2, 1, 0, 1, 1, 3, 2, 1, 1, 1, 0, 2, 3, 1}

    7633633

    Returns: 64039348

  50. {7, 6, 8, 5, 3, 10, 1, 7, 8, 4, 4, 9, 7, 1, 10, 7, 6, 9, 1, 7, 8, 4, 7, 3, 7, 2, 10, 4, 9, 4, 3, 9, 6, 9, 5, 1, 3, 2, 7, 6, 9, 7, 9, 3, 1, 3}

    {0, 0, 1, 0, 3, 2, 1, 0, 1, 3, 3, 2, 2, 1, 3, 2, 0, 0, 3, 2, 3, 3, 1, 2, 1, 3, 0, 1, 2, 1, 3, 3, 2, 3, 3, 2, 3, 1, 0, 3, 3, 2, 1, 0, 1}

    6669831

    Returns: 684665723

  51. {700, 7306, 4562, 5343, 1599, 5041, 2776, 1493, 5611, 5856, 4080, 5280, 7452, 6076, 7096, 2366, 5589, 1657}

    {0, 0, 0, 1, 1, 0, 2, 1, 2, 2, 0, 2, 0, 1, 2, 2, 1}

    6788644

    Returns: 982805482

  52. {8483, 5792, 755, 4485, 5409, 5273, 1316, 1141, 5424, 9092, 446, 7299, 1171, 9196, 9289, 361, 6737, 7617, 5357, 2756, 9198, 1583, 2992, 9838, 2694, 9604, 7807, 6761, 4539, 3478, 2472, 825, 9943, 8432, 7105, 1756, 5006, 5588, 5383, 9671, 3052, 1655, 7891, 5966}

    {0, 0, 1, 2, 2, 0, 2, 1, 2, 0, 1, 1, 0, 0, 0, 2, 1, 2, 2, 2, 2, 0, 2, 1, 1, 0, 2, 2, 2, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 2, 1, 1, 2}

    1320

    Returns: 221719452

  53. {8, 3, 3, 9, 10, 5, 3, 5, 6, 1, 6, 4, 10, 7, 8, 1, 10, 1, 1, 5, 3, 2, 5, 10, 9, 1, 4, 9, 3, 7, 7, 9, 7, 7, 3, 9, 9, 7, 2, 6}

    {0, 0, 1, 2, 0, 1, 0, 1, 1, 3, 3, 0, 2, 3, 1, 2, 2, 1, 3, 3, 0, 3, 0, 1, 0, 3, 1, 0, 1, 0, 3, 2, 1, 2, 0, 0, 0, 2, 2}

    368

    Returns: 340107389

  54. {1844, 7169, 2990, 2315, 8590, 9806, 5975, 4442, 4205, 6802, 6867, 1355, 7707, 5750, 8655, 6234, 5502, 3299, 5670, 1235, 5164}

    {0, 1, 2, 3, 3, 3, 2, 1, 0, 2, 3, 2, 0, 1, 1, 2, 0, 0, 3, 0}

    2466

    Returns: 821472526

  55. {38, 23, 77, 72, 3, 18, 66, 77, 4, 22, 59, 14, 89, 36, 92, 30, 47, 92, 60, 94, 100, 53, 39, 21, 28, 65, 81, 2, 96, 41, 27, 18, 62, 12, 93, 8, 24, 20, 90, 99, 64, 38, 100, 80, 49, 90, 40}

    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    842

    Returns: 138071904

  56. {11559, 10383, 60492, 73642, 65145, 60463, 68104, 53427, 63771, 83212, 16626, 97826, 1947, 69751, 89988, 50261}

    {0, 1, 0, 0, 4, 2, 0, 4, 4, 3, 2, 3, 3, 2, 2}

    4289169

    Returns: 265054769

  57. {576813, 3342, 717423, 144908, 995748, 133139, 487270, 271041, 782262, 219002, 177678, 173484, 413145, 847474, 98867, 118563, 746816, 681492, 203410, 67204, 285851, 240548, 873326, 600242, 61543, 805043, 771804, 129682, 641854, 661411, 285988, 312285, 531403, 345379, 204655, 714648, 455837, 357988, 244661, 392251, 582021, 470901, 190627, 164876, 221282}

    {0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0}

    64346602

    Returns: 694145806

  58. {8999, 4501, 5779, 6854, 6196, 7304, 5613, 2230, 4972, 1449, 9140, 1968, 6990, 7591, 3739, 526, 2340, 208, 1664, 8355, 7920, 4596, 381, 1488, 5637, 3935, 4343, 7449, 7322, 6259, 6045, 8119, 3176, 3058, 6456, 960, 2437, 5864, 7169, 346, 9443, 2256}

    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    196163361

    Returns: 532090122

  59. {471, 914, 552, 420, 730, 999, 416, 333, 804, 146, 129, 957, 267, 440, 635, 907, 489, 843, 254, 994, 767, 704, 879, 784, 795, 655, 839, 212, 745, 913, 646, 542, 894}

    {0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0}

    8

    Returns: 774530556

  60. {65813, 89928, 25646, 61358, 95015, 90393, 52248, 83092, 80073, 16152, 18544, 23567, 86314, 54219, 99599, 9014, 32803, 69554, 56428, 29803, 97004, 79763, 60043, 70017, 53713, 77980, 33581, 79124, 57481, 12507, 56219, 93769, 59523, 17985, 68406, 29881, 29644, 80370, 51351, 68469, 28726, 43084, 90421, 24217}

    {0, 0, 1, 2, 3, 4, 1, 0, 3, 0, 0, 4, 3, 1, 1, 2, 4, 2, 2, 0, 4, 2, 0, 1, 1, 0, 3, 1, 0, 1, 4, 2, 2, 3, 2, 1, 2, 1, 1, 4, 3, 2, 4}

    2697

    Returns: 76098647

  61. {41, 61, 41, 12, 36, 30, 35, 57, 15, 33, 61, 13, 7, 63, 11, 12, 92, 87, 13, 72, 3, 77, 90, 64, 70, 82, 64, 78, 69, 54, 72}

    {0, 1, 0, 2, 0, 0, 2, 2, 1, 0, 2, 0, 2, 1, 2, 2, 2, 1, 2, 0, 1, 2, 2, 0, 2, 0, 1, 0, 0, 1}

    25353

    Returns: 657276336

  62. {789240, 6531, 595012, 545599, 759731, 143256, 271348, 687261, 447051, 569321, 596038, 206245, 801260, 29956, 27805, 524860, 874490, 623727, 914614, 196723, 340876, 760706, 861577, 662297, 325913, 151016, 717970}

    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    35075892

    Returns: 145721115

  63. {334656, 357889, 505010, 187361, 208436, 893666, 868513, 632673, 479656, 829390, 854783, 392967, 401653, 944483, 844145, 254969, 653507, 479640, 476059, 297476, 970578, 700378, 444172, 539512, 195318, 587154, 541931, 937694, 845626, 705002, 792451, 958672, 565337, 274733, 347743, 118602, 450228, 518086, 110689, 929152, 163159, 884957, 558491, 80632, 627608}

    {0, 1, 1, 0, 2, 2, 1, 3, 0, 4, 2, 4, 2, 3, 4, 3, 4, 2, 2, 0, 4, 0, 1, 2, 3, 1, 3, 2, 2, 1, 1, 1, 1, 1, 4, 3, 4, 3, 1, 2, 1, 1, 3, 4}

    999

    Returns: 714352048

  64. {5939, 6032, 5319, 5982, 1119, 9106, 4764, 5138, 9790, 7010, 2023}

    {0, 0, 1, 2, 2, 0, 0, 0, 2, 3}

    40507

    Returns: 267603635

  65. {566, 168, 844, 395, 551, 135, 507, 984, 786, 715, 394, 622, 260, 428, 228, 11, 908, 567, 484, 616, 897, 894, 367, 216, 500, 123, 511, 365, 945, 892, 50, 579, 723, 518, 542, 148}

    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    9172275

    Returns: 553326621

  66. {4952031, 187211, 220187, 299314, 1993253, 6853896, 8160975, 4042482, 2037210, 1651870, 7872807, 5632555, 4085962, 8644885, 3465283, 2435724, 9413696}

    {0, 0, 1, 3, 3, 3, 6, 4, 7, 9, 10, 10, 12, 10, 11, 14}

    4959

    Returns: 177434550

  67. {65301472, 60985410, 88176574, 20919375, 33046580, 67447529, 37881683, 52967178, 66036939, 88899551, 53663422, 71429208, 79941933}

    {0, 1, 0, 3, 0, 4, 6, 5, 6, 9, 10, 6}

    284929

    Returns: 934981039

  68. {352, 178, 284, 441, 332, 956, 109, 13, 751, 734, 855, 320, 377, 994, 468, 294, 53, 474, 701, 925, 885, 849, 202, 355, 548, 418, 585, 523, 528, 529, 671, 107, 976, 14, 161, 420, 475, 594, 947, 782, 203, 248, 362, 921, 941, 106, 835, 753}

    {0, 1, 1, 3, 2, 3, 4, 6, 7, 8, 8, 11, 11, 13, 13, 15, 15, 16, 17, 18, 20, 21, 20, 21, 22, 24, 25, 27, 28, 27, 30, 29, 31, 33, 33, 34, 36, 36, 38, 38, 38, 39, 41, 41, 44, 43, 45}

    983548

    Returns: 175403007

  69. {2214, 8720, 7248, 5773, 4568, 6148, 7524, 2267, 2565, 6396, 4751, 4619, 617, 2491, 4613, 8233, 5602, 4044, 7597, 2548, 1230, 1049, 6586, 8002, 9430, 6516, 2291, 9079, 8356, 244, 1053, 8636, 9789, 9241, 7191, 8317, 7681, 2566, 2858, 263, 2306, 8677, 8741, 7841, 4118, 3073}

    {0, 0, 1, 1, 2, 3, 6, 5, 7, 7, 8, 10, 10, 12, 13, 15, 14, 17, 16, 19, 19, 20, 21, 22, 24, 24, 25, 27, 28, 27, 29, 29, 31, 31, 32, 33, 35, 35, 36, 38, 38, 40, 42, 43, 42}

    45872

    Returns: 898336779

  70. {7811044, 1433503, 650637, 251811, 5445029, 8786022, 3685215, 2078632, 590454, 2976940}

    {0, 1, 1, 3, 4, 4, 3, 6, 6}

    7

    Returns: 368107821

  71. {299, 269, 6777, 5792, 5870, 5449, 4826, 9714, 3892, 2407, 8320, 9042, 3156, 1230, 7342, 3289, 4743, 6449, 1034, 5228, 1917, 2429, 4811, 7342, 9825, 5998, 229, 826, 9910, 796, 3784, 7778, 3345, 1724, 4786, 2938, 6636, 1948, 4323, 6002, 5261, 2043, 3296, 2137, 4623}

    {0, 0, 0, 0, 3, 5, 5, 7, 6, 9, 8, 9, 12, 11, 14, 15, 14, 14, 18, 17, 20, 18, 22, 22, 21, 22, 25, 25, 28, 28, 29, 31, 32, 32, 34, 32, 33, 37, 36, 36, 38, 39, 41, 41}

    843778

    Returns: 417728871

  72. {2064398, 1650356, 88464, 5998408, 1290143, 6436944, 9719654, 288793, 700313, 7979906, 1743842, 1693190, 5060041, 6761021, 9801067, 921932, 518245, 2630664}

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}

    25

    Returns: 82631118

  73. {266496, 893842, 184784, 198551, 795870, 194898, 102186, 389061, 434421, 106579, 73410, 887053, 605346, 71848, 874759, 79588}

    {0, 1, 2, 3, 3, 4, 6, 7, 7, 8, 10, 10, 11, 13, 13}

    40

    Returns: 558020523

  74. {1200891, 7669924}

    {0}

    4

    Returns: 850171748

  75. {814, 880, 438, 331, 814, 297, 409, 985, 136, 511, 169, 834, 118, 988, 728, 67, 277, 104, 385, 741, 735, 224, 175, 440, 486, 794, 943, 89, 321, 17, 457, 797, 471, 921, 473, 879, 751, 870, 244, 246, 288, 896, 686, 417, 89, 411, 999, 256, 754}

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47}

    2864527

    Returns: 746905952

  76. {437760, 324733, 796475, 884523, 817200, 400396, 880772, 966314, 195493, 285457, 636080, 136911, 785134, 686890, 332511, 472639, 108897, 106883, 970880, 362488, 94762, 818653, 967147, 649696, 225206, 548331, 599909, 564557, 284805, 16939, 651027, 506485, 487311, 947269, 842441, 765952, 656831, 656192, 478554, 526572, 151051, 424013, 293274, 537617, 481343, 502389}

    {0, 0, 0, 3, 2, 4, 4, 6, 6, 9, 8, 11, 10, 12, 12, 14, 14, 16, 16, 17, 19, 19, 20, 23, 23, 23, 26, 27, 27, 27, 29, 30, 30, 31, 34, 33, 34, 37, 38, 38, 40, 40, 40, 42, 42}

    7037306

    Returns: 308036351

  77. {868905216, 599624632, 618812219, 535153092, 728986420, 403786451, 198789492, 8599133, 444910337, 457286891, 234051167, 535494141, 687989621, 40109992, 639187401, 353280866, 50973527, 770785766, 136667558, 60809792, 619922640, 707590727, 582077022, 433941946, 762004396, 243103874, 881119775, 175796875, 34924114, 204832332, 29073118, 605362089, 702085300, 460042963, 925708807, 967352409, 677850673, 247327149, 229267716, 643976471, 38969681, 716292482, 485209407, 225471162}

    {0, 0, 2, 2, 3, 0, 6, 5, 3, 7, 9, 6, 9, 10, 14, 15, 12, 17, 14, 17, 19, 21, 18, 21, 23, 20, 25, 25, 26, 29, 26, 26, 28, 32, 34, 30, 36, 34, 38, 39, 36, 41, 42}

    32

    Returns: 310143273

  78. {2271, 15941, 14632, 43648, 58996, 10500, 31331, 9894, 91065, 94689, 69154, 99468, 5326}

    {0, 0, 0, 1, 2, 4, 6, 6, 8, 9, 8, 11}

    987

    Returns: 16749755

  79. {6032041, 225148, 1881585, 3186044, 1284684, 5455636, 8218380, 7701985, 1559349, 4333942, 4173546, 3654391}

    {0, 0, 2, 2, 4, 5, 6, 6, 8, 8, 9}

    681

    Returns: 439449127

  80. {15845, 75936, 25202, 54080, 66893, 47526, 81134, 61695, 31234, 24069, 46642, 56278, 79291, 29885, 11817, 6948, 44764, 49065, 19267}

    {0, 1, 0, 0, 2, 5, 6, 5, 7, 8, 10, 11, 9, 12, 12, 15, 15, 14}

    1

    Returns: 767

  81. {214249530, 320941313, 955509509, 554593106, 346075608, 522227874, 422071229, 134640713, 478663191, 807113159, 913819955, 887493658, 751505683, 791876164, 476811301, 903402672, 775742737, 775054640, 967754856, 864210551, 366314478, 933806042, 665622252, 690458254, 1464112}

    {0, 0, 1, 2, 1, 4, 3, 4, 6, 9, 9, 7, 8, 12, 14, 14, 15, 14, 15, 17, 19, 20, 21, 20}

    241466

    Returns: 405055049

  82. {373, 728, 432, 688, 689, 215, 402, 819, 291, 838, 28, 648, 534, 972, 388, 95, 883, 651, 556, 624, 1, 864, 590, 607, 912, 432, 502, 412, 857, 855, 679}

    {0, 1, 1, 2, 0, 5, 2, 7, 3, 8, 7, 10, 9, 11, 14, 15, 14, 13, 14, 15, 17, 16, 21, 23, 20, 21, 21, 23, 28, 25}

    44910563

    Returns: 41136078

  83. {531105, 595881}

    {0}

    885481

    Returns: 665143455

  84. {8, 7, 5, 8, 2, 6, 1, 5, 6, 6, 7, 3, 9, 9, 10, 1, 10, 6, 7, 8, 9, 4}

    {0, 0, 2, 2, 2, 5, 4, 5, 8, 8, 9, 9, 11, 11, 13, 13, 14, 15, 18, 19, 18}

    12117

    Returns: 962741998

  85. {35191401, 39664059, 90667777, 17994469, 5948873, 2259292, 10869609, 23532820, 76544836, 8071815, 50745606, 52297184, 32612601}

    {0, 0, 2, 3, 3, 3, 3, 7, 7, 7, 9, 9}

    109142

    Returns: 940519216

  86. {346318, 239400, 970205, 300637, 19536, 814025, 562470, 684484, 16112, 922537, 524209, 597791, 339647, 222123, 715989, 608704, 427860, 475003, 142951, 657889, 571709, 859728, 165018, 840990, 286917, 984541, 19607, 479720, 170345, 687646, 52701, 272154, 105550, 313358, 423553, 912336, 353353, 199889, 109734}

    {0, 1, 2, 2, 3, 4, 5, 7, 7, 8, 9, 11, 12, 12, 13, 15, 15, 17, 17, 18, 20, 21, 21, 23, 24, 24, 25, 26, 27, 29, 29, 31, 32, 33, 34, 35, 35, 36}

    3914427

    Returns: 125982084

  87. {75067, 24758, 75973, 54705, 1264, 47828, 10624, 21457, 65899, 19008, 75879, 39686, 99626, 65915, 29682, 27118, 36878, 18655, 3170, 19292, 23410, 40387, 60780, 10485, 66264, 73695}

    {0, 0, 0, 2, 1, 3, 4, 7, 8, 7, 10, 10, 11, 12, 11, 14, 14, 14, 17, 15, 17, 17, 20, 21, 24}

    8809446

    Returns: 795841925

  88. {4866814, 498045, 981219, 7832233, 1581876, 4721270, 5871783, 8359479, 3336723, 6610852, 3821033, 3492023}

    {0, 0, 2, 1, 3, 4, 2, 7, 6, 9, 10}

    225550

    Returns: 968299978

  89. {950, 519, 99, 912, 539, 378, 719, 200, 626, 281, 398, 272, 354, 470, 345, 305, 478, 536, 524, 579, 668, 416, 810, 212, 913, 755, 593, 848, 176, 593, 234, 959, 890, 94, 260, 284, 910, 619, 528, 585}

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38}

    379092603

    Returns: 17463618

  90. {972, 171, 492, 348, 999, 743, 659, 844, 443, 474, 257, 638, 408, 284, 484, 141, 749, 293, 673, 73, 432, 359, 438, 168, 270, 188, 217, 514, 671, 397, 496, 827, 757, 707, 763}

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33}

    23573460

    Returns: 769037847

  91. {677, 602, 211, 152, 931, 178, 350, 556, 390, 143, 611, 452, 474, 205, 475, 751, 435, 643, 48, 122, 162, 289}

    {0, 1, 0, 0, 3, 0, 2, 3, 5, 9, 10, 7, 8, 12, 12, 10, 14, 12, 18, 15, 15}

    381350

    Returns: 954760776

  92. {66519, 30712, 44258, 79617, 26707, 72877, 69358, 22153, 3021, 35300, 79205, 39372, 48310, 41495, 98107, 28212, 56728, 89522, 44142, 26332, 54547, 51819, 38061, 85599, 8677, 48736, 55510, 97170, 23088, 44255, 83885, 398, 99038, 89214, 49290}

    {0, 0, 1, 2, 3, 4, 6, 6, 8, 8, 9, 10, 11, 12, 13, 15, 16, 16, 18, 19, 19, 21, 22, 22, 23, 24, 26, 26, 28, 28, 30, 31, 31, 33}

    3174

    Returns: 459587111

  93. {8837, 3160, 5002, 2012, 3423, 9413, 5512, 8939, 7292, 9200, 9780, 2321, 4322, 5115, 1783, 6327, 7577, 1328, 3159, 7609, 511, 6823, 6027, 7817, 8640, 81, 3287}

    {0, 1, 2, 3, 3, 5, 6, 6, 7, 9, 10, 11, 11, 12, 13, 15, 15, 16, 18, 18, 20, 20, 21, 23, 24, 25}

    2

    Returns: 505683532

  94. {1608333, 9860197, 9754379, 6427034, 3481649, 344201, 3031276, 120042, 1677917, 7665932, 8951433, 7174694, 3581842, 1389105, 9325480, 119396, 7214249, 2244107, 3060668, 8223354, 6929192, 5544456, 8820555, 7346145, 9067662, 3519251, 7382379, 9398974, 4279087}

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27}

    602

    Returns: 181031661

  95. {3, 6, 7, 5, 7, 8, 10, 1, 1, 8, 8, 9, 5, 7, 3, 1, 5, 6, 6, 5, 6, 7, 6, 8, 4, 7, 1, 3, 6, 4, 2, 1, 7, 7, 10, 9, 4, 9, 3, 1}

    {0, 1, 0, 2, 4, 5, 3, 7, 5, 8, 9, 11, 9, 12, 11, 14, 15, 16, 16, 19, 17, 19, 19, 21, 24, 23, 26, 26, 25, 26, 30, 30, 32, 32, 34, 33, 35, 34, 36}

    56460351

    Returns: 299431740

  96. {804289383, 846930886, 681692777, 714636915, 957747793, 424238335, 719885386, 649760492, 596516649, 189641421, 25202362, 350490027, 783368690, 102520059, 44897763, 967513926, 365180540, 540383426, 304089172, 303455736, 35005211, 521595368, 294702567, 726956429, 336465782, 861021530, 278722862, 233665123, 145174067, 468703135, 101513929, 801979802, 315634022, 635723058, 369133069, 125898167, 59961393, 89018456, 628175011, 656478042, 131176229, 653377373, 859484421, 914544919, 608413784, 756898537, 734575198, 973594324, 149798315, 38664370 }

    {0, 0, 0, 3, 3, 1, 3, 4, 6, 1, 8, 7, 0, 11, 8, 6, 11, 0, 5, 16, 17, 8, 2, 21, 7, 18, 26, 27, 16, 25, 12, 26, 21, 0, 24, 3, 8, 34, 22, 2, 5, 39, 34, 23, 14, 1, 13, 20, 23 }

    123123

    Returns: 745185058

  97. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8100, 16000, 32000, 64000, 128000, 256000, 512000, 1000000, 2000000, 4000000, 16000000, 8000000, 32000000, 64000000, 128000000, 256000000, 512000000, 1000000000 }

    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    1

    Returns: 73741847

  98. {3, 7, 6, 8, 9, 4, 2, 1, 5, 6, 7, 8, 9, 6, 1, 2, 3, 5 }

    {0, 0, 0, 3, 1, 1, 2, 0, 0, 3, 7, 8, 9, 0, 0, 4, 1 }

    987654321

    Returns: 46327623

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: