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 de prima secundă în care regele va fi mulţumit dacă îşi desfăşoară planul, modulo $10^9^+7$.

h2. Date de intrare