== include(page="template/taskheader" task_id="arbset") ==

Mioara are un arbore cu $N$ noduri, unde rădăcina este nodul $1$, şi unde fiecare nod $i$ are câte o valoare $v[i]$ între $1$ şi $N$. Toate valorile sunt distincte. O submulţime $A$ de noduri se numeşte bună dacă şi numai dacă:

Mioara are un arbore cu $N$ noduri, unde rădăcina este nodul $1$, şi unde fiecare nod $i$ are câte o valoare $v[i]$ între $1$ şi $N$. Toate valorile sunt *distincte*. O submulţime $A$ de noduri se numeşte *bună* dacă şi numai dacă:

1. Oricare două noduri $i, j ∈ A$, unde $i$ este strămoşal lui $j$, satisfac $v[i] < v[j]$;

1. Oricare două noduri $i, j ∈ A$, unde $i$ este strămoş al lui $j$, satisfac $v[i] < v[j]$;

2. Pentru oricare două noduri $i, j ∈ A$, dacă $l$ este cel mai adânc strămos, comun al lui $i$ şi $j$, atunci $l ∈ A$.
Mioara este curioasă: care este suma valorilor $|A|$ (adică mărimea lui $A$) pentru toate mulţimile $A$ bune?

h2. Date de ieşire

În fişierul de ieşire $arbset.out$ conţine răspunsul cerut, modulo 10^9^ + 7.

Fişierul de ieşire $arbset.out$ conţine răspunsul cerut, modulo 10^9^ + 7.

h2. Subtaskuri

** Oricare nod are cel mult $2$ muchii incidente.
* *Subtask 4 (10 puncte)*

*** $N ≤ 300000$
** OCel mult un nod are mai mult de 1 muchie incident

** $N ≤ 300000$
** Cel mult un nod are mai mult de $1$ muchie incidentă.

*Subtask 5 (30 puncte)*
** $C = 2, N ≤ 8$

* *Subtask 5 (30 puncte)*
** $N ≤ 300000$
** Oricare nod are cel mult 3 muchii incidente.

* *Subtask 6 (20 puncte)*

** $C = 2, N ≤ 18$

** $N ≤ 300000$

h2. Exemplu
table(example). |_. arbset.in |_. arbset.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4
2 1 3 4
1 2
1 3
1 4
| 11

|
h3. Explicaţie

...

Mulţimile bune sunt ∅ (cu mărimea $0$), ${1}, {2}, {3}, {4}$ (cu mărimea $1$), ${1, 3}, {1, 4}$ (cu mărimea $2$) şi ${1, 3, 4}$ (cu mărimea $3$). Astfel rezultatul este $11$.

== include(page="template/taskfooter" task_id="arbset") ==