Înghetare

inghetare

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

h2. Date de intrare

1 3
1 4
| 1

‎
‎
‎

|
| 8
1 2

2 6
2 7
3 8

‎
‎
‎
‎

| 685714294

‎
‎
‎
‎
‎
‎
‎
‎
‎
‎
‎

|
h3. Explicaţie