Fişierul intrare/ieşire:	arbnr.in, arbnr.out	Sursă	Lot Iasi 2008, Baraj 6
Autor	Emilian Miron	Adăugată de	Adrian Diaconu •DITzoneC
Timp execuţie pe test	0.275 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Arbnr

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₁a₂a₃...a_k lista ordonata a fiilor lui rA, b₁b₂b₃...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₁, A₂, ..., A_T. Gigel vinde numai arbori cu radacina avand N noduri in care nu apar nici unul dintre arborii model.

Cerinta

Scrieti un program care sa calculeze cati arbori cu radacina cu N noduri distincti poate vinde Gigel.

Date de intrare

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.

Date de iesire

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.

Restricţii

• 1 ≤ N ≤ 10.000
• 0 ≤ T ≤ 40
• 2 ≤ M ≤ 10.000
• 30% din punctaj se acorda pentru N,M ≤ 100 si T ≤ 10
• 65% din punctaj se acorda pentru M ≤ 500

Exemplu

Cum se trimit solutii?