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 . A subset of nodes is a perfect tree if there is a root of that subset of nodes that satisfies these properties:

- 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 number of nodes in the tree.

The next lines will each contain two integers, and , indicating that nodes and are connected by an edge.

#### 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 perfect trees, with the roots in red:

#### 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