Paint the Tree

Limits: 2 sec., 256 MiB

Today Zenyk wants to present Marichka a tree. Tree is such connected graph that consists of \(N\) vertices and \(N-1\) edges. Zenyk decided that tree will be much more interesting if he paints it. He has \(K\) colors and every vertex should be painted in one color.

Zenyk thought that the tree is the most interesting if the distance between 2 nearest vertices with same color is maximal possible. You should find this maximal distance and the number of such paintings modulo \(10^9+7\). Two paintings are considered different if there exist at least one vertex which has different colors.

Input

First line of the input contains 2 integers \(N\) and \(K\). Each of the next \(N-1\) lines contains 2 integers \(a_i,b_i\), which means that vertices \(a_i\) and \(b_i\) are connected by an edge.

Output

Print 2 integers – maximal distance between nearest vertices with same color and number of such paintings modulo \(10^9+7\).

Constraints

\(2 \le N \le 2000\),

\(1 \le K < N\),

\(1 \le a_i,b_i \le N\).

Samples