Antena

Cerință

Se definește un “arbore antenă” cu $n$ noduri prin următoarea structură:

• $n$ noduri sunt așezate în linie și între oricare două vecine se află o muchie. Aceste noduri sunt numerotate de la $1$ la $n$.
• Fiecare dintre cele $n$ noduri poate avea încă $0$, $1$ sau $2$ vecini laterali.
• Vecinii laterali sunt etichetați cu valori mai mari decât $n$.
• Un “arbore antenă” are cel puțin $n$ și cel mult $3 \cdot n$ noduri.

În figura de mai jos avem un arbore antenă cu $10$ noduri, pentru $n = 5$. Nodurile $1$ și $4$ au doi vecini laterali, nodurile $2$ și $5$ nu au vecini laterali, iar nodul $3$ are un vecin lateral.

Se dă un arbore antenă cu $n$ noduri. Să se determine numărul de subarbori conecși pe care îi are arborele dat, rezultatul fiind calculat modulo $10^9 + 7$.

Date de intrare

Pe prima linie a fișierului de intrare antena.in se află numărul natural $n$.
Fiecare dintre următoarele $n$ linii descriu vecinii laterali ai fiecărui nod de la $1$ la $n$ astfel:

• Primul număr pe fiecare linie este $nv$ reprezentând numărul de vecini laterali ($0$, $1$ sau $2$).
• Următoarele $nv$ valori pe linie reprezintă identificatorii vecinilor laterali, distincte și mai mari decât $n$.

Date de ieșire

Pe prima linie a fișierului de ieșire antena.out se va găsi un singur număr întreg, care reprezintă numărul de subarbori conecși modulo $10^9 + 7$.

Restricții și precizări

• $1 \leq n \leq 100 \ 000$;
• $0 \leq nv \leq 2$;
• Numerele care identifică vecinii laterali sunt naturale, distincte și mai mari decât $n$.
• Se garantează că nodurile arborelui sunt etichetate cu numere consecutive de la $1$ la numărul total de noduri din arbore (cel puțin $n$ și cel mult $3 \cdot n$ noduri).
• Subtaskuri:

Exemplul 1

antena.in

2
2 3 4
1 5

antena.out

17

Explicație

În figura de mai jos se poate observa arborele din exemplu:

Subarborii conecși numărați sunt:

1. Noduri individuale: $(1)$, $(2)$, $(3)$, $(4)$, $(5)$;
2. Grupuri de noduri conectate: $(1,3)$, $(1,4)$, $(1,3,4)$, $(2,5)$, $(1,2)$, $(1,2,3)$, $(1,2,4)$, $(1,2,5)$, $(1,2,3,4)$, $(1,2,3,5)$, $(1,2,4,5)$, $(1,2,3,4,5)$.

Pentru fiecare grup de noduri dintre paranteze, sunt luate în considerare toate muchiile prezente în arbore între acele noduri.
Numărul total de subarbori conecși este $17$.

Exemplul 2

antena.in

5
2 9 7
0
1 8
2 6 10
0

antena.out

131

Explicație

Acest exemplu corespunde arborelui din enunțul problemei: