Ninjaclasher, MCPT's self-proclaimed President, has an obsession with all things perfect. One day, while he was working on a tree problem, he began wondering how many perfect trees existed in the problem. As such, he has hired you to find the number of perfect trees on a given tree.
More specifically, he wants to know the number of non-empty subset of nodes in the tree that form a perfect tree, modulo
- The subset of nodes forms a connected tree.
- Every non-leaf node in the tree has the same amount of children
. - Every leaf is equidistant to the root node.
Input Specification
The first line will contain the integer
The next
Output Specification
The number of subset of nodes of the tree that form a perfect tree, modulo
Subtasks
Subtask 1 [27%]
Subtask 2 [73%]
No additional constraints.
Sample Input for Subtask 1
8
1 2
1 3
1 4
2 5
2 6
4 7
4 8
Sample Output for Subtask 1
21
Explanation for Sample for Subtask 1
The following tree is given:
The following are the
Sample Input for Subtask 2
15
1 2
1 3
1 4
1 5
1 6
2 7
2 8
2 9
2 10
6 11
6 12
6 13
6 14
11 15
Sample Output for Subtask 2
130
Comments