arbore

Se dă un arbore (graf conex aciclic) cu $N$ noduri. Vrem să eliminăm noduri (împreună cu muchiile adiacente) din arborele dat, astfel încât numărul de componente conexe ale grafului rămas să fie maxim.

Cerință

Aflați care este numărul maxim de componente conexe pe care le putem obține și câte submulțimi distincte de noduri se pot elimina din arbore astfel încât să rămână la final acest număr maxim de componente conexe.

Date de intrare

Pe prima linie a fișierului de intrare arbore.in se va afla numărul natural $N$, reprezentând numărul de noduri ale arborelui. Pe următoarele $N-1$ linii se vor afla câte două numere $X$ și $Y$, cu semnificația că există o muchie între nodurile $X$ și $Y$.

Date de ieșire

Pe prima linie a fișierului de ieșire arbore.out se vor afișa două numere naturale reprezentând numărul maxim de componente conexe pe care îl putem obține, respectiv numărul de moduri în care putem obține acest număr de componente conexe modulo $10^9+7$ (adică restul împărțirii acestui număr la $1\ 000\ 000\ 007$).

Restricții și precizări

• $1 \le N \le 100\ 000$
• Se acordă $40\%$ din punctajul unui test dacă numărul maxim de componente conexe este corect.
• Se acordă $60\%$ din punctajul unui test dacă numărul de moduri este corect.
• Pentru $20\%$ din teste $N \le 20$.
• Pentru alte $30\%$ din teste $N \le 1000$.

Exemplul 1

arbore.in

6 
1 2 
1 3 
1 4 
4 5 
4 6 

arbore.out

4 1

Explicaţie

Se șterg nodurile $1$ și $4$. Nicio altă submulțime de noduri șterse nu produce $4$ sau mai multe componente conexe.

Exemplul 2

arbore.in

4 
1 2 
2 3 
3 4

arbore.out

2 5

Explicaţie

Se pot șterge următoarele submulțimi de noduri pentru a obține $2$ componente conexe: $\{2\}$, $\{3\}$, $\{2, 3\}$, $\{2, 4\}$, $\{1, 3\}$.