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

Poveste şi cerinţă...

Un arbore cu radacina este format dintr-o multime de noduri, dintre care un nod special denumit radacina. Fiecare nod are precizata o lista ordonata de noduri fiu, iar fiecare nod diferit de radacina este fiul al exact unui alt nod denumit parinte. Radacina nu are parinte.
Subarborele unui nod $X$ este un arbore cu radacina obtinut eliminand orice nod care nu este fiu direct sau indirect al nodului $X$ si considerand nodul $X$ radacina.
Fie doi arbori cu radacina {$A$}, $B$ cu radacinile $rA$ si respectiv {$rB$}. Fie {$a{~1~}a{~2~}a{~3~}...a{~k~}$} lista ordonata a fiilor lui {$rA$}, {$b{~1~}b{~2~}b{~3~}...b{~p~}$} lista ordonata a fiilor lui {$rB$}. Spunem ca arborii {$A$}, {$B$} sunt egali daca {$p=k$} si pentru orice {$1 ≤ i ≤ k$} subarborii cu radacinile {$a{~i~}$} si {$b{~i~}$} sunt egali.
Spunem ca arborele $A$ apare in arborele $B$ daca exista un nod {$nB$} din $B$ astfel incat subarborele cu radacina $nB$ este egal cu arborele {$A$}.
Gigel are o afacere cu o multime de $T$ arbori cu radacina (denumiti model) {$A{~1~}$}, {$A{~2~}$}, ..., {$A{~T~}$}. Gigel vinde numai arbori cu radacina avand $N$ noduri in care nu apar nici unul dintre arborii model.
 
h2. Cerinta
 
Scrieti un program care sa calculeze cati arbori cu radacina cu $N$ noduri distincti poate vinde Gigel.

h2. Date de intrare

Fişierul de intrare $arbnr.in$ ...

Fisierul de intrare $arbnr.in$ contine pe prima linie numerele naturale $N$ si $T$ reprezentand numarul de noduri din arborii vanduti de Gigel si respectiv numarul de arbori model. In continuare urmeaza $T$ blocuri de date, fiecare bloc reprezentand descrierea unui arbore model. Blocul care descrie un arbore model contine pe prima linie un numar natural $M$ reprezentand numarul de noduri din arbore. Pe cea de a doua linie sunt scrise $M-1$ numere naturale separate prin spatiu. Al {$i$}-lea numar de pe linie este nodul parinte al nodului {$i+1$} ({$1 ≤ i ≤ M-1$}). Radacina este nodul cu numarul {$1$}. Ordinea fiilor este considerata ordinea crescatoare a numerelor lor de ordine.

h2. Date de ieşire

h2. Date de iesire

În fişierul de ieşire $arbnr.out$ ...

Fisierul $arbnr.out$ va contine o singura linie pe care va fi scris un numar natural reprezentand numarul de arbori cu radacina distincti cu $N$ noduri in care nu apare nici unul dintre arborii model modulo {$9907$}.

h2. Restricţii

* $... ≤ ... ≤ ...$

* {$1 ≤ N ≤ 10.000$}
* {$0 ≤ T ≤ 40$}
* {$2 ≤ M ≤ 10.000$}
* {$30% din punctaj se acorda pentru N,M & le; 100 si T ≤ 10$}
* {$65% din punctaj se acorda pentru M ≤ 500$}

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

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

|4 2
3
1 2
3
1 1
|3

|
h3. Explicaţie