Regele Gheţii, supărat că Finn şi Jake îl tot înfrâng, vrea să aducă haos în ţinut. Planul lui este simplu: va distruge potecile una câte una. În fiecare secundă, el alege aleatoriu o potecă neîngheţată şi creează pe ea un strat gros de gheaţă, astfel blocând-o. Regele se declară mulţumit doar în momentul în care nu mai există vreo aşezare cu $3$ sau mai multe poteci neîngheţate care o leagă de alte aşezări.

Determinaţi expected value la prima secundă în care regele va fi mulţumit dacă îşi desfăşoară planul.

Determinaţi expected value la prima secundă în care regele va fi mulţumit dacă îşi desfăşoară planul, modulo $10^9^+7$.

h2. Date de intrare

h2. Date de ieşire

În fişierul de ieşire $inghetare.out$ se va afişa un număr real: valoarea aşteptată căutată.

În fişierul de ieşire $inghetare.out$ se va afişa un număr întreg între $0$ şi $10^9^+7$, răspunsul la problemă.

h2. Restricţii

* $1 ≤ n ≤ 2000$

* $1 ≤ n ≤ 2 000$

* $1 ≤ u, v ≤ n$

Subtaskuri:
 

|_. #  |_. Punctaj |_. Restricţii |
| 1 | 3 | $n ≤ 10$ |
| 2 | 12| Există exact $1$ aşezare cu strict mai mult de $2$ poteci conectate la ea |