Les vaches causent sans cesse des ennuis en conduisant le tracteur de Farmer John. Il a donc caché les clés dans un beau coffre neuf de son bureau. Elles ne se découragent pas et veulent le forcer.

Le coffre a un système de code compliqué. La saisie est organisée en arbre enraciné de $N$ nœuds ($1 \leq N \leq 20,000$), chacun demandant un chiffre de 0 à 9. Les nœuds sont numérotés $0..N-1$.

Elles savent seulement que certaines suites de longueur 5 n'apparaissent pas sur certains chemins remontant l'arbre.

Par exemple, considérons cet arbre, de racine A :

A <- B <- C <- D <- E
               ^
               |
               F

Elles peuvent savoir que 01234 n'apparaît pas depuis $F$ et 91234 depuis $E$. Cela exclut 19 codes, tous ceux de la forme :

4 <- 3 <- 2 <- 1 <- *
               ^
               |
               0

ou

4 <- 3 <- 2 <- 1 <- 9
               ^
               |
               *

en tenant compte du fait que :

4 <- 3 <- 2 <- 1 <- 9
               ^
               |
               0

apparaît deux fois, le nombre est 19.

Avec $M$ suites de longueur 5 ($1 \leq M \leq 50,000$) et leurs nœuds de départ, calculez le nombre de codes exclus, modulo 1234567.

Entrée

• Ligne $1$ : entiers $N$ et $M$ séparés par un espace.
• Lignes $2..N$ : la ligne $i+1$ contient l'entier $p_i$, parent du nœud $i$ ($0 \leq p_i < i$).
• Lignes $N+1..N+M$ : la ligne $N+i$ décrit la suite $i$ interdite. Elle contient $v_i$ et $s_i$ séparés par un espace. $v_i$ est le nœud de départ et $s_i$ une chaîne de 5 chiffres absente en remontant depuis $v_i$. La racine est garantie au moins 4 étapes au-dessus de $v_i$.

Sortie

• Ligne $1$ : un entier donnant le nombre de configurations exclues, modulo 1234567.

Exemples

Entrée 1

6 2
0
1
2
3
3
4 01234
5 91234

Sortie 1

19

Auteur du problème : Jacob Steinhardt, 2014