Después del exitoso reinado de Luis en WALandia, el trono ha pasado a su hijo, el joven rey Robert. A diferencia de su padre, Robert no solo quiere proteger el reino con la mínima cantidad de guardias, sino que además quiere saber de cuántas maneras distintas puede hacerlo.

El reino está formado por ~N~ ciudades conectadas por ~N-1~ caminos, formando un árbol. Una estación de guardia en una ciudad protege esa ciudad y todas las ciudades directamente conectadas a ella. Robert quiere colocar la mínima cantidad posible de estaciones de guardia que protejan todas las ciudades. Entre todas las configuraciones que usan esa cantidad mínima, quiere saber cuántas formas distintas hay de elegir las ciudades donde se colocan las guardias.

Dos configuraciones se consideran distintas si existe una ciudad que tiene guardia en una configuración pero no en la otra.

Como el número puede ser muy grande, calcula la respuesta módulo ~10^9 + 7~.

Entrada

• La primera línea contiene un entero ~N~, el número de ciudades.
• Las siguientes ~N-1~ líneas contienen dos enteros ~u~ y ~v~, indicando que hay un camino entre la ciudad ~u~ y la ciudad ~v~.

Salida

Dos enteros separados por espacio: la mínima cantidad de guardias necesarias y el número de formas de colocarlas módulo ~10^9 + 7~.

Restricciones

• ~1 \leq N \leq 2 \cdot 10^5~
• ~1 \leq u, v \leq N, u \neq v~

Subtareas

Subtarea	Puntos	Restricción
1	3	~N \leq 16~
2	8	~N \leq 300~
3	16	~N \leq 2000~
4	25	Cada nodo está conectado como máximo a otros dos
5	48	Sin Restricciones Adicionales

Ejemplos de Entrada y Salida

Ejemplo #1 de Entrada

7
1 2
1 3
2 4
2 5
3 6
3 7

Ejemplo #1 de Salida

2 1

Explicación: Hay 7 ciudades. Colocando guardias en las ciudades 2 y 3 se protegen todas las ciudades (la ciudad 2 cubre ~1,2,4,5~ y la ciudad 3 cubre ~1,3,6,7~). La respuesta es 2, y es la única manera de cubrir todo usando solo 2 guardias.

Ejemplo #2 de Entrada

4
1 2
2 3
3 4

Ejemplo #2 de Salida

2 4

Explicación: Se pueden colocar 2 guardias de las siguientes maneras: ~(1,4), (1,3), (2,3), (2,4)~.