Statistics

Problem Statement for "TreeDistance"

Problem Statement

Cat Snuke has a tree with N vertices. The vertices are labeled 0 through N-1.

Snuke is able to modify the tree by performing a special operation. The operation consists of two steps. In the first step, he selects and removes an arbitrary edge of the tree. This divides the tree into two connected components. In the second step, he adds an arbitrary edge that connects those two components back into one tree.

You are given a int[] p that describes a tree, and an int K. The int[] p contains N-1 elements. For each i, the vertex p[i] and the vertex (i+1) are connected by an edge. Note that the initial labeling of the tree is such that for each i, p[i] is less than (i+1).

Snuke currently has the tree described by p. He may now modify it by repeatedly performing the operation described above. The number of operations Snuke will perform will be between 0 and K, inclusive.

Two trees are considered different if there are vertices p and q such that one of the trees contains the edge p-q but the other one does not. Return the number of different trees Snuke can produce, modulo 1,000,000,007.

Definition

Class:
TreeDistance
Method:
countTrees
Parameters:
int[], int
Returns:
int
Method signature:
int countTrees(int[] p, int K)
(be sure your method is public)

Constraints

  • p will contain between 1 and 49 elements, inclusive. (This means that N will be between 2 and 50, inclusive.)
  • For each valid i, p[i] will be between 0 and i, inclusive.
  • K will be between 0 and 50, inclusive.

Examples

  1. {0, 0}

    1

    Returns: 3

    There are three different trees for N=3. The one described by this p contains the edges 0-1 and 0-2. Snuke can turn it into either of the other two trees in a single operation.

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

    1

    Returns: 28

    Some of the trees for N=6 cannot be obtained from the given one in a single operation.

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

    2

    Returns: 222

    In two operations Snuke can produce some more trees, but not all of them. For example, Snuke would need three operations to produce the tree with the edges 0-1, 0-2, 0-3, 0-4, and 0-5.

  4. {0, 1, 2, 2, 0}

    50

    Returns: 1296

    In 50 operations Snuke can produce all trees.

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

    0

    Returns: 1

    As no modifications are allowed, there is only one tree Snuke can produce in this test case.

  6. {0, 0, 1, 3, 0, 0, 5, 0, 0, 1, 7, 6, 8, 7, 12, 3, 8, 0, 16, 17, 13, 14, 18, 19, 21, 17, 1, 22, 0, 14, 22, 1, 10, 3, 18, 0, 6, 4, 15, 32, 3, 16, 22, 0, 31, 37, 10, 37, 44}

    0

    Returns: 1

  7. {0, 1, 0, 3, 3, 4, 4, 5, 6, 8, 3, 1, 12, 12, 13, 10, 4, 8, 13, 17, 2, 10, 12, 20, 2, 14, 17, 19, 15, 0, 22, 15, 3, 8, 3, 17, 27, 2, 12, 38, 37, 4, 40, 29, 9, 22, 43, 32, 37}

    1

    Returns: 7124

  8. {0, 1, 0, 2, 1, 2, 0, 7, 6, 9, 5, 0, 8, 5, 1, 5, 7, 0, 0, 3, 16, 3, 2, 12, 12, 21, 10, 6, 19, 10, 3, 29, 4, 24, 11, 14, 28, 31, 13, 36, 17, 34, 15, 30, 22, 20, 10, 47, 36}

    2

    Returns: 18553157

  9. {0, 1, 1, 2, 3, 5, 3, 4, 6, 2, 2, 3, 6, 4, 3, 9, 2, 14, 15, 12, 16, 15, 1, 5, 8, 21, 0, 10, 18, 14, 20, 6, 9, 31, 28, 15, 12, 30, 8, 7, 35, 39, 10, 2, 4, 44, 36, 11, 10}

    3

    Returns: 685467311

  10. {0, 1, 2, 3, 1, 4, 0, 0, 2, 1, 7, 6, 7, 3, 13, 10, 5, 12, 17, 2, 12, 21, 16, 5, 9, 9, 6, 24, 3, 7, 26, 9, 29, 17, 9, 20, 32, 18, 24, 2, 1, 29, 17, 30, 6, 37, 20, 15, 25}

    4

    Returns: 918275883

  11. {0, 1, 0, 1, 4, 4, 6, 2, 1, 1, 1, 2, 10, 3, 3, 0, 2, 17, 1, 9, 12, 0, 6, 11, 11, 13, 16, 12, 22, 7, 14, 16, 20, 15, 26, 5, 26, 8, 9, 29, 22, 2, 32, 38, 14, 1, 39, 39, 3}

    5

    Returns: 809193281

  12. {0, 1, 0, 3, 4, 3, 3, 2, 7, 1, 6, 9, 12, 1, 5, 2, 1, 5, 18, 4, 13, 12, 20, 20, 19, 24, 6, 0, 2, 26, 0, 21, 11, 11, 22, 18, 34, 12, 11, 39, 13, 12, 14, 11, 16, 35, 38, 0, 35}

    6

    Returns: 372089286

  13. {0, 0, 1, 3, 4, 5, 6, 1, 8, 7, 4, 6, 12, 5, 13, 7, 8, 16, 15, 9, 18, 16, 4, 21, 19, 22, 5, 4, 19, 3, 11, 23, 2, 23, 11, 17, 21, 18, 29, 13, 7, 34, 27, 30, 35, 15, 12, 23, 29}

    7

    Returns: 215827514

  14. {0, 0, 0, 0, 1, 3, 5, 7, 5, 6, 3, 7, 4, 7, 4, 13, 6, 10, 6, 2, 13, 16, 11, 10, 15, 3, 26, 16, 23, 18, 27, 9, 18, 30, 31, 32, 33, 15, 4, 14, 18, 29, 16, 9, 41, 35, 23, 23, 28}

    8

    Returns: 611767291

  15. {0, 1, 0, 1, 2, 3, 6, 1, 1, 1, 3, 0, 1, 1, 10, 4, 6, 15, 9, 16, 20, 11, 6, 3, 3, 24, 15, 15, 23, 9, 15, 13, 28, 5, 7, 16, 33, 0, 28, 39, 8, 22, 24, 1, 21, 9, 43, 7, 34}

    9

    Returns: 857660211

  16. {0, 0, 0, 0, 2, 3, 1, 2, 3, 7, 3, 10, 8, 8, 9, 1, 2, 0, 7, 17, 19, 2, 17, 2, 0, 6, 4, 9, 12, 14, 8, 12, 10, 30, 20, 30, 8, 36, 28, 22, 8, 2, 2, 13, 26, 14, 46, 6, 25}

    10

    Returns: 310259667

  17. {0, 1, 2, 3, 3, 2, 6, 3, 5, 7, 7, 0, 4, 10, 3, 9, 9, 17, 7, 5, 6, 4, 3, 19, 5, 3, 1, 8, 7, 3, 30, 11, 13, 25, 4, 2, 3, 33, 18, 33, 21, 10, 29, 28, 8, 44, 33, 33, 20}

    11

    Returns: 131522691

  18. {0, 1, 2, 0, 3, 1, 1, 4, 5, 3, 1, 4, 3, 8, 1, 14, 13, 13, 1, 13, 16, 12, 19, 2, 16, 1, 8, 11, 21, 22, 6, 30, 20, 31, 34, 1, 17, 33, 26, 17, 34, 15, 37, 4, 41, 4, 46, 46, 35}

    12

    Returns: 804595377

  19. {0, 0, 2, 3, 4, 4, 4, 0, 8, 5, 4, 3, 5, 11, 8, 15, 8, 0, 0, 7, 3, 7, 9, 1, 8, 17, 7, 9, 11, 4, 22, 15, 23, 30, 7, 33, 34, 13, 27, 8, 6, 35, 16, 17, 27, 8, 32, 30, 43}

    13

    Returns: 472419957

  20. {0, 1, 0, 1, 4, 2, 4, 3, 1, 1, 7, 0, 11, 10, 1, 8, 0, 1, 18, 3, 1, 3, 13, 18, 24, 5, 2, 27, 8, 5, 14, 23, 0, 9, 20, 20, 2, 0, 20, 13, 13, 11, 28, 30, 4, 4, 23, 41, 3}

    14

    Returns: 370209126

  21. {0, 1, 2, 0, 1, 3, 2, 2, 5, 8, 9, 5, 4, 5, 3, 8, 1, 8, 0, 19, 0, 5, 22, 21, 9, 3, 15, 26, 4, 28, 25, 19, 22, 2, 25, 6, 14, 36, 37, 23, 6, 0, 33, 12, 33, 27, 8, 26, 6}

    15

    Returns: 502139364

  22. {0, 0, 2, 1, 2, 1, 2, 7, 1, 8, 0, 5, 9, 6, 8, 0, 14, 14, 8, 18, 7, 13, 15, 11, 8, 1, 18, 14, 0, 3, 8, 2, 13, 32, 0, 13, 26, 35, 33, 30, 6, 26, 12, 17, 35, 26, 36, 25, 7}

    16

    Returns: 128268788

  23. {0, 1, 1, 3, 0, 0, 3, 1, 6, 0, 1, 9, 12, 4, 0, 14, 11, 0, 2, 15, 2, 7, 1, 6, 23, 12, 12, 14, 3, 2, 1, 6, 31, 1, 9, 35, 32, 12, 10, 19, 17, 38, 1, 11, 5, 20, 1, 34, 13}

    17

    Returns: 104152651

  24. {0, 1, 2, 0, 4, 4, 3, 6, 2, 6, 1, 10, 7, 5, 5, 3, 1, 8, 15, 2, 9, 6, 6, 22, 18, 1, 6, 2, 23, 13, 3, 9, 5, 25, 16, 24, 28, 36, 10, 36, 33, 3, 7, 21, 0, 8, 45, 12, 23}

    18

    Returns: 906895853

  25. {0, 1, 1, 0, 1, 1, 4, 2, 6, 2, 2, 10, 10, 12, 4, 8, 12, 8, 4, 6, 7, 4, 0, 17, 13, 18, 0, 4, 22, 9, 23, 26, 6, 3, 11, 34, 33, 25, 24, 16, 37, 10, 8, 24, 40, 34, 16, 44, 35}

    19

    Returns: 346217672

  26. {0, 0, 1, 1, 4, 5, 6, 0, 8, 5, 0, 8, 12, 12, 11, 14, 2, 1, 1, 3, 1, 15, 2, 18, 7, 19, 3, 16, 6, 14, 23, 25, 19, 26, 10, 10, 15, 10, 11, 16, 32, 1, 14, 32, 13, 2, 17, 24, 31}

    20

    Returns: 36586613

  27. {0, 0, 0, 0, 0, 5, 5, 1, 8, 7, 0, 11, 9, 10, 14, 1, 14, 0, 13, 9, 5, 21, 17, 7, 18, 24, 15, 22, 2, 28, 19, 18, 16, 30, 5, 17, 13, 34, 37, 0, 4, 0, 14, 38, 23, 29, 46, 17, 30}

    21

    Returns: 586882927

  28. {0, 0, 1, 3, 0, 1, 6, 5, 2, 1, 0, 5, 8, 6, 2, 8, 5, 9, 11, 11, 9, 15, 5, 12, 10, 11, 24, 2, 17, 8, 15, 19, 7, 8, 28, 27, 9, 10, 22, 8, 40, 37, 22, 34, 26, 1, 40, 6, 7}

    22

    Returns: 169764166

  29. {0, 0, 0, 2, 0, 1, 1, 0, 4, 7, 7, 2, 4, 7, 12, 15, 11, 14, 12, 6, 7, 0, 3, 18, 3, 23, 16, 19, 16, 9, 29, 19, 21, 16, 6, 31, 34, 22, 26, 34, 3, 29, 18, 10, 17, 13, 14, 29, 17}

    23

    Returns: 580441099

  30. {0, 0, 0, 0, 4, 0, 0, 5, 1, 1, 8, 9, 11, 13, 13, 5, 14, 8, 6, 9, 11, 20, 1, 15, 7, 2, 2, 27, 13, 26, 4, 19, 23, 21, 22, 28, 4, 23, 12, 3, 38, 24, 21, 8, 38, 43, 33, 4, 0}

    24

    Returns: 173361395

  31. {0, 1, 1, 0, 1, 4, 2, 2, 7, 8, 9, 5, 9, 12, 8, 0, 7, 1, 8, 12, 16, 9, 21, 1, 4, 5, 20, 24, 22, 2, 11, 26, 0, 1, 4, 30, 11, 33, 36, 21, 27, 19, 35, 7, 16, 43, 19, 34, 25}

    25

    Returns: 587699234

  32. {0, 1, 1, 2, 3, 0, 1, 4, 4, 9, 10, 10, 2, 11, 2, 1, 16, 17, 0, 7, 18, 20, 13, 3, 1, 2, 20, 26, 9, 19, 22, 12, 0, 22, 3, 28, 5, 13, 28, 6, 40, 33, 22, 0, 13, 23, 32, 41, 11}

    26

    Returns: 336472092

  33. {0, 1, 0, 2, 4, 2, 0, 7, 1, 2, 6, 5, 3, 5, 8, 6, 14, 7, 16, 13, 7, 0, 9, 3, 24, 5, 24, 20, 4, 12, 27, 30, 3, 15, 4, 18, 21, 6, 14, 27, 32, 9, 3, 13, 20, 26, 15, 7, 39}

    27

    Returns: 912194580

  34. {0, 0, 1, 2, 3, 4, 3, 7, 8, 2, 0, 11, 2, 10, 5, 1, 14, 14, 6, 16, 5, 8, 22, 9, 20, 12, 16, 2, 9, 15, 12, 23, 14, 31, 10, 15, 18, 12, 9, 34, 8, 11, 26, 2, 10, 37, 26, 26, 9}

    28

    Returns: 540300690

  35. {0, 1, 0, 1, 1, 2, 5, 0, 7, 5, 2, 8, 0, 10, 9, 6, 2, 10, 14, 6, 19, 2, 16, 13, 1, 18, 23, 27, 19, 19, 27, 9, 14, 9, 34, 24, 35, 36, 35, 14, 19, 0, 15, 34, 5, 45, 19, 16, 29}

    29

    Returns: 679873785

  36. {0, 1, 2, 0, 3, 3, 5, 4, 1, 0, 10, 7, 5, 12, 3, 7, 7, 16, 9, 19, 1, 2, 16, 13, 16, 23, 5, 21, 12, 19, 11, 21, 6, 8, 22, 24, 28, 6, 24, 23, 18, 33, 14, 29, 30, 19, 20, 27, 36}

    30

    Returns: 451379303

  37. {0, 0, 0, 3, 3, 0, 3, 1, 3, 3, 7, 1, 8, 6, 1, 8, 1, 0, 2, 6, 6, 17, 1, 4, 15, 23, 23, 21, 5, 19, 18, 17, 10, 2, 23, 1, 5, 27, 37, 1, 16, 39, 33, 2, 27, 22, 1, 3, 48}

    31

    Returns: 53280858

  38. {0, 0, 0, 1, 0, 0, 0, 4, 7, 0, 4, 0, 9, 10, 11, 14, 14, 0, 14, 8, 6, 15, 9, 12, 8, 21, 9, 19, 9, 17, 3, 11, 3, 22, 12, 30, 26, 37, 7, 17, 13, 10, 24, 2, 23, 36, 33, 6, 37}

    32

    Returns: 563533387

  39. {0, 1, 1, 2, 4, 4, 5, 3, 8, 2, 8, 3, 5, 12, 4, 4, 12, 12, 18, 16, 15, 11, 15, 13, 1, 3, 16, 25, 18, 21, 26, 7, 28, 29, 27, 14, 11, 8, 15, 16, 16, 37, 35, 6, 43, 18, 13, 13, 14}

    33

    Returns: 732957678

  40. {0, 0, 0, 2, 0, 1, 6, 4, 2, 0, 2, 9, 11, 12, 4, 11, 14, 11, 17, 5, 12, 2, 9, 3, 23, 15, 4, 16, 14, 25, 26, 9, 26, 8, 27, 24, 20, 16, 11, 13, 32, 34, 35, 0, 29, 17, 32, 38, 35}

    34

    Returns: 951529639

  41. {0, 1, 1, 3, 2, 4, 3, 6, 1, 5, 8, 2, 3, 1, 3, 5, 10, 17, 13, 12, 18, 17, 17, 9, 15, 17, 15, 4, 24, 27, 7, 31, 4, 5, 30, 30, 14, 13, 21, 26, 35, 25, 13, 41, 33, 38, 10, 38, 0}

    35

    Returns: 298074916

  42. {0, 1, 2, 3, 4, 2, 6, 3, 2, 1, 0, 4, 6, 8, 11, 3, 4, 4, 9, 12, 0, 13, 18, 7, 3, 15, 26, 7, 20, 3, 2, 10, 0, 12, 1, 29, 35, 18, 12, 39, 28, 12, 1, 35, 19, 33, 40, 5, 12}

    36

    Returns: 553571022

  43. {0, 0, 1, 3, 1, 2, 5, 0, 0, 4, 4, 2, 11, 8, 9, 13, 5, 3, 13, 11, 15, 15, 20, 5, 10, 21, 19, 20, 21, 25, 2, 26, 6, 22, 24, 15, 8, 37, 32, 31, 30, 2, 12, 36, 38, 2, 21, 18, 11}

    37

    Returns: 748603461

  44. {0, 1, 1, 2, 3, 0, 6, 4, 7, 2, 0, 4, 4, 13, 9, 4, 15, 6, 9, 12, 18, 21, 16, 4, 10, 17, 18, 0, 11, 28, 7, 14, 0, 30, 8, 27, 16, 3, 5, 16, 37, 7, 39, 32, 39, 24, 15, 1, 34}

    38

    Returns: 6584555

  45. {0, 1, 1, 2, 3, 2, 2, 2, 8, 4, 10, 7, 7, 8, 2, 0, 4, 7, 2, 6, 4, 7, 12, 5, 23, 25, 22, 1, 9, 17, 8, 6, 28, 19, 16, 13, 10, 1, 1, 2, 20, 8, 26, 22, 35, 23, 32, 31, 22}

    39

    Returns: 45112589

  46. {0, 0, 1, 3, 4, 3, 0, 3, 3, 3, 8, 8, 6, 7, 5, 13, 13, 8, 11, 17, 4, 15, 9, 15, 1, 15, 21, 19, 14, 10, 6, 21, 20, 24, 0, 28, 18, 14, 3, 4, 29, 9, 27, 32, 33, 4, 2, 42, 41}

    40

    Returns: 829068719

  47. {0, 1, 0, 0, 0, 2, 4, 2, 4, 2, 4, 4, 12, 13, 12, 10, 11, 2, 14, 18, 8, 19, 1, 9, 10, 22, 19, 10, 21, 13, 3, 13, 32, 4, 25, 3, 3, 19, 5, 3, 6, 0, 8, 5, 27, 7, 1, 22, 15}

    41

    Returns: 506600068

  48. {0, 0, 1, 2, 1, 3, 6, 4, 3, 3, 6, 11, 8, 6, 9, 13, 14, 13, 18, 18, 6, 21, 4, 21, 10, 21, 0, 23, 7, 20, 7, 4, 8, 21, 11, 24, 5, 22, 5, 20, 18, 2, 17, 7, 26, 42, 28, 28, 11}

    42

    Returns: 668097403

  49. {0, 1, 2, 0, 3, 4, 0, 4, 6, 2, 4, 6, 6, 0, 4, 13, 13, 16, 11, 13, 0, 21, 8, 11, 4, 16, 16, 21, 4, 11, 28, 30, 5, 24, 7, 21, 36, 37, 12, 29, 31, 5, 41, 15, 7, 24, 41, 42, 2}

    43

    Returns: 423080680

  50. {0, 1, 1, 1, 2, 1, 1, 3, 3, 9, 8, 5, 9, 11, 10, 12, 9, 0, 5, 2, 20, 14, 0, 22, 9, 21, 23, 9, 7, 1, 26, 6, 19, 25, 15, 17, 14, 21, 32, 10, 6, 14, 3, 10, 40, 0, 32, 15, 31}

    44

    Returns: 779818755

  51. {0, 0, 1, 3, 4, 3, 6, 5, 8, 4, 10, 8, 1, 11, 4, 14, 11, 0, 5, 6, 20, 11, 16, 13, 17, 7, 19, 10, 1, 4, 15, 30, 9, 6, 18, 14, 6, 34, 38, 8, 14, 26, 18, 14, 18, 35, 35, 22, 25}

    45

    Returns: 182080177

  52. {0, 0, 1, 0, 0, 5, 6, 4, 8, 9, 2, 6, 11, 6, 4, 4, 13, 14, 14, 13, 4, 6, 21, 4, 6, 21, 3, 15, 15, 18, 7, 22, 14, 6, 20, 1, 5, 28, 13, 32, 20, 34, 3, 14, 1, 17, 37, 11, 44}

    46

    Returns: 264993729

  53. {0, 0, 1, 1, 4, 2, 1, 0, 4, 8, 6, 9, 8, 8, 8, 10, 12, 15, 1, 14, 5, 9, 5, 10, 8, 19, 0, 15, 3, 18, 3, 28, 13, 5, 0, 32, 23, 9, 31, 14, 33, 5, 24, 41, 34, 31, 19, 39, 2}

    47

    Returns: 626755812

  54. {0, 0, 1, 3, 0, 1, 5, 3, 6, 2, 8, 10, 5, 0, 5, 12, 5, 14, 6, 6, 20, 9, 13, 18, 3, 1, 7, 3, 6, 17, 9, 14, 23, 23, 5, 28, 31, 7, 14, 28, 20, 7, 7, 8, 18, 37, 8, 11, 0}

    48

    Returns: 678886102

  55. {0, 0, 1, 0, 2, 3, 5, 4, 5, 0, 2, 6, 2, 3, 7, 10, 4, 1, 17, 4, 2, 16, 12, 18, 23, 25, 4, 18, 8, 8, 25, 29, 1, 32, 5, 28, 0, 17, 18, 24, 38, 20, 5, 36, 8, 39, 6, 1, 11}

    49

    Returns: 48440174

  56. {0, 1, 1, 2, 2, 5, 3, 0, 3, 0, 1, 7, 0, 1, 0, 10, 14, 13, 12, 14, 17, 13, 13, 20, 6, 3, 19, 2, 6, 2, 9, 25, 22, 0, 18, 4, 6, 27, 34, 2, 2, 19, 23, 40, 28, 26, 46, 8, 18}

    50

    Returns: 48440174

  57. {0}

    1

    Returns: 1

  58. {0, 0}

    0

    Returns: 1

  59. {0, 1, 1}

    0

    Returns: 1

  60. {0, 0, 0, 2}

    1

    Returns: 15

  61. {0, 1, 0, 2, 0}

    1

    Returns: 28

  62. {0, 1, 0, 2, 0, 3}

    6

    Returns: 16807

  63. {0, 1, 1, 1, 4, 0, 0}

    1

    Returns: 56

  64. {0, 1, 1, 3, 2, 2, 1, 7}

    2

    Returns: 2358

  65. {0, 0, 0, 0, 2, 1, 5, 0, 4}

    7

    Returns: 58471050

  66. {0, 1, 1, 1, 1, 2, 1, 7, 1, 6}

    4

    Returns: 2317806

  67. {0, 1, 1, 3, 0, 5, 5, 3, 0, 9, 0}

    11

    Returns: 917363797

  68. {0, 0, 2, 2, 3, 2, 5, 2, 1, 1, 6, 7}

    2

    Returns: 21027

  69. {0, 0, 2, 1, 3, 0, 3, 1, 7, 7, 6, 11, 0}

    3

    Returns: 1829721

  70. {0, 1, 1, 3, 1, 2, 3, 2, 3, 1, 6, 9, 6, 7}

    0

    Returns: 1

  71. {0, 0, 1, 2, 3, 4, 0, 0, 4, 7, 6, 1, 12, 9, 2}

    5

    Returns: 578776677

  72. {0, 0, 0, 3, 1, 5, 3, 6, 7, 7, 10, 9, 0, 11, 11, 5}

    16

    Returns: 472854576

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

    7

    Returns: 620262291

  74. {0, 0, 2, 3, 1, 1, 1, 4, 0, 8, 4, 10, 4, 12, 12, 6, 14, 17}

    4

    Returns: 456892113

  75. {0, 1, 1, 1, 4, 5, 3, 5, 0, 6, 9, 2, 3, 0, 10, 4, 14, 10, 1}

    0

    Returns: 1

  76. {0, 1, 2, 1, 4, 5, 6, 7, 0, 5, 1, 8, 0, 4, 8, 3, 10, 16, 17, 0}

    13

    Returns: 166478901

  77. {0, 0, 2, 0, 1, 5, 5, 5, 3, 5, 8, 5, 9, 12, 11, 14, 1, 0, 8, 18, 11}

    4

    Returns: 188047434

  78. {0, 1, 0, 0, 2, 5, 5, 2, 3, 9, 3, 9, 5, 6, 10, 6, 13, 1, 2, 16, 12, 15}

    5

    Returns: 613353960

  79. {0, 0, 1, 3, 0, 4, 3, 2, 4, 4, 2, 1, 8, 0, 7, 15, 0, 10, 7, 3, 1, 12, 13}

    12

    Returns: 152418432

  80. {0, 0, 0, 2, 0, 4, 3, 2, 0, 9, 4, 0, 12, 13, 11, 4, 15, 1, 2, 3, 5, 8, 21, 1}

    22

    Returns: 740299968

  81. {0, 1, 0, 2, 1, 2, 3, 7, 3, 0, 2, 8, 10, 10, 7, 8, 11, 11, 18, 9, 6, 8, 10, 20, 3}

    6

    Returns: 163744700

  82. {0, 0, 0, 1, 3, 4, 0, 6, 4, 4, 1, 1, 1, 8, 6, 15, 6, 5, 2, 5, 11, 3, 7, 15, 3, 9}

    12

    Returns: 957755646

  83. {0, 1, 0, 2, 2, 1, 5, 7, 5, 9, 0, 4, 8, 2, 14, 2, 15, 13, 13, 0, 4, 14, 10, 3, 18, 21, 3}

    0

    Returns: 1

  84. {0, 1, 0, 1, 3, 0, 2, 7, 0, 1, 2, 1, 1, 3, 11, 0, 0, 13, 7, 7, 19, 19, 14, 0, 13, 22, 19, 26}

    9

    Returns: 615148294

  85. {0, 0, 2, 2, 3, 1, 0, 3, 3, 9, 1, 0, 11, 12, 3, 9, 0, 14, 18, 9, 0, 3, 9, 9, 10, 9, 7, 23, 0}

    13

    Returns: 798066566

  86. {0, 0, 1, 1, 0, 0, 2, 5, 2, 6, 10, 9, 0, 0, 9, 2, 14, 4, 4, 6, 19, 16, 2, 5, 3, 1, 7, 22, 3, 11}

    1

    Returns: 1807

  87. {0, 1, 1, 1, 1, 5, 2, 6, 6, 2, 2, 8, 0, 3, 0, 13, 11, 15, 3, 2, 20, 9, 15, 5, 21, 16, 24, 18, 7, 10, 6}

    21

    Returns: 137705601

  88. {0, 1, 0, 2, 4, 2, 3, 4, 0, 4, 7, 7, 0, 4, 4, 12, 12, 3, 2, 5, 5, 21, 19, 6, 3, 22, 24, 22, 10, 7, 25, 31}

    14

    Returns: 720401849

  89. {0, 0, 1, 3, 0, 5, 2, 0, 1, 5, 3, 0, 0, 10, 14, 2, 3, 2, 6, 11, 1, 14, 11, 13, 13, 23, 7, 3, 11, 22, 20, 23, 23}

    22

    Returns: 71978452

  90. {0, 0, 0, 1, 3, 2, 3, 2, 8, 0, 10, 8, 12, 12, 8, 12, 11, 6, 12, 18, 11, 17, 2, 13, 15, 21, 19, 27, 19, 9, 26, 24, 8, 18}

    15

    Returns: 479658940

  91. {0, 0, 0, 3, 3, 4, 1, 1, 3, 3, 7, 6, 1, 5, 12, 15, 0, 4, 0, 6, 4, 12, 20, 2, 21, 21, 10, 7, 28, 6, 11, 27, 0, 15, 15}

    30

    Returns: 420923954

  92. {0, 0, 2, 0, 3, 5, 4, 3, 4, 5, 7, 5, 11, 5, 1, 3, 0, 0, 11, 18, 12, 2, 14, 15, 10, 7, 11, 22, 10, 13, 3, 14, 16, 21, 23, 24}

    25

    Returns: 561088439

  93. {0, 0, 2, 2, 1, 1, 6, 0, 0, 4, 9, 6, 9, 11, 12, 2, 8, 8, 12, 11, 8, 4, 18, 8, 11, 17, 7, 15, 25, 2, 6, 14, 5, 19, 7, 20, 3}

    37

    Returns: 358420421

  94. {0, 0, 2, 3, 1, 2, 1, 1, 4, 8, 0, 9, 3, 13, 6, 0, 5, 9, 5, 14, 3, 14, 8, 20, 22, 2, 4, 12, 24, 5, 10, 10, 22, 30, 30, 13, 9, 11}

    12

    Returns: 687913065

  95. {0, 1, 0, 0, 3, 1, 4, 1, 2, 9, 3, 3, 2, 2, 13, 6, 16, 10, 3, 18, 0, 0, 4, 9, 16, 24, 15, 18, 19, 19, 26, 25, 7, 18, 9, 22, 5, 27, 4}

    32

    Returns: 179870771

  96. {0, 1, 0, 0, 3, 3, 5, 5, 1, 6, 3, 10, 12, 10, 9, 10, 15, 0, 6, 5, 14, 10, 16, 5, 17, 14, 3, 13, 22, 18, 18, 16, 27, 11, 32, 18, 36, 15, 19, 8}

    37

    Returns: 422620015

  97. {0, 1, 1, 1, 1, 0, 6, 5, 7, 7, 10, 4, 6, 2, 10, 2, 0, 4, 3, 1, 5, 10, 15, 3, 5, 25, 10, 21, 28, 17, 4, 5, 5, 28, 26, 2, 26, 12, 18, 21, 38}

    10

    Returns: 974230459

  98. {0, 1, 1, 3, 3, 3, 6, 4, 6, 6, 2, 10, 7, 3, 12, 12, 6, 4, 10, 2, 5, 3, 6, 11, 14, 5, 14, 13, 25, 4, 0, 0, 13, 26, 13, 32, 26, 19, 36, 32, 29, 9}

    41

    Returns: 436856494

  99. {0, 1, 0, 0, 3, 3, 4, 2, 2, 3, 7, 9, 10, 11, 6, 2, 15, 8, 10, 3, 16, 7, 1, 15, 22, 1, 7, 9, 20, 5, 21, 17, 7, 0, 21, 27, 35, 20, 1, 0, 21, 2, 30}

    35

    Returns: 428120386

  100. {0, 1, 1, 2, 1, 4, 5, 0, 0, 2, 10, 1, 9, 1, 13, 9, 7, 9, 0, 9, 20, 19, 3, 8, 21, 7, 10, 26, 18, 9, 10, 0, 9, 16, 28, 4, 12, 30, 21, 33, 24, 35, 2, 12}

    39

    Returns: 183410823

  101. {0, 1, 1, 0, 3, 1, 1, 2, 6, 0, 10, 5, 9, 4, 10, 15, 1, 12, 15, 5, 8, 7, 19, 16, 19, 8, 12, 6, 14, 1, 19, 26, 21, 18, 5, 16, 9, 35, 27, 1, 7, 41, 37, 13, 8}

    33

    Returns: 311783308

  102. {0, 1, 2, 0, 4, 5, 3, 4, 4, 9, 5, 1, 9, 1, 7, 5, 2, 9, 9, 12, 14, 0, 7, 3, 24, 10, 17, 4, 18, 12, 20, 4, 4, 9, 10, 11, 20, 23, 20, 14, 19, 32, 38, 43, 1, 33}

    21

    Returns: 29034060

  103. {0, 1, 0, 2, 2, 1, 2, 1, 6, 5, 9, 7, 1, 0, 4, 14, 3, 5, 16, 6, 20, 16, 15, 0, 20, 3, 4, 6, 26, 9, 15, 27, 27, 19, 34, 35, 26, 0, 8, 18, 9, 19, 7, 9, 18, 44, 7}

    40

    Returns: 188376629

  104. {0, 0, 0, 3, 3, 4, 6, 7, 8, 1, 6, 5, 0, 13, 5, 13, 1, 15, 17, 13, 13, 17, 18, 4, 21, 10, 15, 9, 18, 18, 15, 31, 24, 5, 28, 9, 15, 10, 23, 5, 30, 21, 19, 3, 40, 43, 0, 21}

    5

    Returns: 21194268

  105. {0}

    50

    Returns: 1

  106. {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, 48}

    0

    Returns: 1

  107. {0, 0, 2, 3, 4, 5, 6, 7, 7, 8, 9, 10, 11, 13, 13, 15, 15, 17, 17, 18, 19, 21, 22, 23, 24, 25, 25, 26, 28, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 40, 41, 41, 43, 43, 45, 46, 46, 48}

    0

    Returns: 1

  108. {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, 48}

    10

    Returns: 528265439

  109. {0, 0, 2, 2, 3, 5, 6, 7, 7, 9, 9, 10, 12, 13, 14, 15, 15, 17, 18, 19, 19, 21, 22, 22, 24, 25, 25, 27, 27, 28, 29, 30, 32, 32, 33, 34, 35, 37, 37, 39, 40, 40, 41, 43, 43, 45, 46, 46, 48}

    10

    Returns: 626540832

  110. {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, 48}

    20

    Returns: 898455807

  111. {0, 0, 1, 3, 4, 5, 6, 6, 7, 9, 9, 10, 12, 12, 13, 14, 15, 16, 17, 19, 20, 20, 21, 22, 24, 25, 26, 27, 27, 29, 29, 30, 32, 33, 33, 34, 36, 36, 37, 39, 40, 40, 42, 42, 43, 45, 45, 47, 47}

    20

    Returns: 379298501

  112. {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, 48}

    30

    Returns: 259191348

  113. {0, 0, 1, 2, 4, 5, 6, 6, 7, 8, 9, 11, 12, 12, 13, 14, 16, 16, 17, 19, 19, 20, 21, 22, 23, 25, 25, 26, 28, 28, 29, 31, 32, 33, 34, 34, 36, 37, 37, 38, 39, 41, 42, 42, 43, 44, 46, 46, 47}

    30

    Returns: 807493202

  114. {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, 48}

    40

    Returns: 864537814

  115. {0, 0, 2, 3, 3, 5, 6, 7, 7, 8, 10, 11, 11, 13, 14, 15, 15, 16, 17, 19, 20, 21, 21, 23, 24, 25, 25, 26, 27, 28, 29, 30, 32, 33, 34, 35, 36, 37, 38, 38, 39, 40, 42, 42, 44, 45, 46, 46, 48}

    40

    Returns: 688628086

  116. {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, 48}

    50

    Returns: 48440174

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

    50

    Returns: 48440174

  118. {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, 0, 0, 0}

    0

    Returns: 1

  119. {0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0}

    0

    Returns: 1

  120. {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, 0, 0, 0}

    10

    Returns: 210252509

  121. {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1}

    10

    Returns: 522106878

  122. {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, 0, 0, 0}

    20

    Returns: 990015989

  123. {0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1}

    20

    Returns: 529964517

  124. {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, 0, 0, 0}

    30

    Returns: 714117916

  125. {0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1}

    30

    Returns: 886521197

  126. {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, 0, 0, 0}

    40

    Returns: 825757360

  127. {0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1}

    40

    Returns: 881032219

  128. {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, 0, 0, 0}

    50

    Returns: 48440174

  129. {0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1}

    50

    Returns: 48440174

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

    0

    Returns: 1

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

    10

    Returns: 963715954

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

    20

    Returns: 858074398

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

    30

    Returns: 166117077

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

    40

    Returns: 440542418

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

    50

    Returns: 48440174

  136. {0, 0, 0, 0, 2, 3, 1, 2, 3, 7, 3, 10, 8, 8, 9, 1, 2, 0, 7, 17, 19, 2, 17, 2, 0, 6, 4, 9, 12, 14, 8, 12, 10, 30, 20, 30, 8, 36, 28, 22, 8, 2, 2, 13, 26, 14, 46, 6, 25 }

    10

    Returns: 310259667

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: