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 rA şi respectiv rB. Fie a1a2a3...ak lista ordonată a fiilor lui rA, b1b2b3...bp lista ordonată a fiilor lui rB. Spunem că arborii A, B sunt egali dacă p=k şi pentru orice 1<=i<=k subarborii cu rădăcinile ai şi bi sunt egali.
Spunem că arborele A apare în arborele B dacă există un nod nB din B astfel încât subarborele cu rădăcina nB este egal cu arborele A.
Gigel are o afacere cu o mulţime de T arbori cu rădăcină (denumiţi model) A1, A2, ..., AT. 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 (1<=i<=M-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 9907.
Restricţii
1 ≤ N ≤ 10 000
0 ≤ T ≤ 40
2 ≤ M ≤ 10000
30% din punctaj se acordă pentru N,M≤100 şi T≤10
65% din punctaj se acordă pentru M≤500