arbnr

Un arbore cu rădăcină este format dintr-o mulţime de noduri, dintre care un nod special denumit rădăcină. Fiecare nod are precizată o listă ordonată de noduri fiu, iar fiecare nod diferit de rădăcină este fiul al exact unui alt nod denumit părinte. Rădăcina nu are părinte.
Subarborele unui nod $X$ este un arbore cu rădăcină obţinut eliminând orice nod care nu este fiu direct sau indirect al nodului $X$ şi considerând nodul $X$ rădăcină.
Fie doi arbori cu rădăcină $A$, $B$ cu rădăcinile $r_A$ şi respectiv $r_B$. Fie $a_1 \ a_2 \ a_3 \dots a_k$ lista ordonată a fiilor lui $r_A$, $b_1 \ b_2 \ b_3 \dots b_p$ lista ordonată a fiilor lui $r_B$. Spunem că arborii $A$, $B$ sunt egali dacă $p=k$ şi pentru orice $1 \leq i \leq k$ subarborii cu rădăcinile $a_i$ şi $b_i$ sunt egali.
Spunem că arborele $A$ apare în arborele $B$ dacă există un nod $n_B$ din $B$ astfel încât subarborele cu rădăcina $n_B$ este egal cu arborele $A$.
Gigel are o afacere cu o mulţime de $T$ arbori cu rădăcină (denumiţi model) $A_1, A_2, \dots, A_T$. Gigel vinde numai arbori cu rădăcină având $N$ noduri în care nu apar nici unul dintre arborii model.

Cerinţă

Scrieţi un program care să calculeze câţi arbori cu rădăcină cu $N$ noduri distincţi poate vinde Gigel.

Date de intrare

Fişierul de intrare arbnr.in conţine pe prima linie numerele naturale $N$ şi $T$ reprezentând numărul de noduri din arborii vânduţi de Gigel şi respectiv numărul de arbori model. În continuare urmează $T$ blocuri de date, fiecare bloc reprezentând descrierea unui arbore model. Blocul care descrie un arbore model conţine pe prima linie un număr natural $M$ reprezentând numărul de noduri din arbore. Pe cea de a doua linie sunt scrise $M-1$ numere naturale separate prin spaţiu. Al $i$-lea număr de pe linie este nodul părinte al nodului $i+1$. Rădăcina este nodul cu numărul $1$. Ordinea fiilor este considerată ordinea crescătoare a numerelor lor de ordine.

Date de ieșire

Fişierul arbnr.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul de arbori cu rădăcină distincţi cu $N$ noduri în care nu apare nici unul dintre arborii model modulo $9 \ 907$.

Restricții și precizări

• $1 \leq N \leq 10 \ 000$
• $0 \leq T \leq 40$
• $2 \leq M \leq 10 \ 000$
• $30\%$ din punctaj se acordă pentru $N,M \leq 100$ şi $T \leq 10$
• $65\%$ din punctaj se acordă pentru $M \leq 500$

Exemplu

arbnr.in

4 2
3
1 2
3
1 1

arbnr.out

3