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, modulo $10^9^+7$.

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

h2. Date de intrare

h2. Date de ieşire

Î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ă.

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

h2. Restricţii

* $1 ≤ n ≤ 2 000$

* $1 ≤ n ≤ 2000$

* $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 |