A. Shaking Trees
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

One day, Little Z met a towering tree on the road, which blocked his path. With no other choice, he had to figure out a way to remove the entire tree to continue forward. Little Z, being immensely strong, could shake a node of the tree continuously until it fell off, becoming a small tree, while all the leaves of the small tree would drift to the ground and disappear.

Now, Little Z wants to know how many shakes he needs to make all nodes of the tree fall to the ground. But this is too easy for him. He also finds that the tree is not very tall. So, please also tell Little Z how many ways he can achieve this with the minimum number of shakes.

Formally, there is a rooted tree containing $$$n$$$ nodes, numbered from $$$1$$$ to $$$n$$$. The root of the tree is node $$$1$$$, and the height of the tree does not exceed $$$100$$$. In each operation, Little Z can choose a node $$$u$$$, cut $$$u$$$ from its parent (if it has one) to become the root of a new tree, and then delete all leaf nodes in the tree rooted at $$$u$$$.

Now, Little Z wants to know the minimum number of operations required to delete all nodes. You also need to answer the number of ways to delete all nodes with the minimum number of operations after modulo $$$10^9+7$$$.

Two operation schemes are considered the same if and only if they have the same number of operations and the node numbers operated on in each operation are the same.

Input

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2\times10^5 $$$), representing the number of nodes in the tree.

The following $$$n-1$$$ lines, each contain two integers $$$u,v$$$ ($$$1 \le u, v \le n$$$), representing an edge on the tree.

It is guaranteed that the height of the tree does not exceed $$$100$$$.

Output

Output one line with two integers, representing the minimum number of operations and the number of schemes modulo $$$10^9+7$$$.

Example
Input
8
1 2
1 3
1 4
4 5
5 6
1 7
4 8
Output
4 8
Note
The tree in the example

In the example, it takes at least $$$4$$$ operations to delete all nodes, and there are a total of $$$8$$$ ways to delete all nodes with $$$4$$$ operations.

These solutions are: $$$[6,1,4,1], [6,1,1,1], [1,5,4,1], [1,5,1,1], [1,4,1,4], [1,1,1,1], [1,4,4,1], [1,1,4,1]$$$

In the solution $$$[6,1,4,1]$$$, all nodes are deleted as follows:

After selecting node $$$1$$$, all nodes are deleted.