Las vacas siguen causando problemas paseando en el tractor de Farmer John, así que escondió las llaves en una elegante caja fuerte nueva de su oficina. Sin desanimarse, intentarán abrirla.

La caja tiene un sistema de código complicado. La entrada forma un árbol enraizado de $N$ nodos ($1 \leq N \leq 20,000$), cada uno con un dígito de 0 a 9. Los nodos se numeran $0..N-1$.

Solo saben que ciertas secuencias de longitud 5 no aparecen en determinados caminos hacia arriba por el árbol.

Por ejemplo, supón este árbol con raíz A:

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

Pueden saber que 01234 no aparece desde $F$ y 91234 desde $E$. Esto descarta 19 códigos, todos los de la forma:

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

o

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

teniendo en cuenta que:

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

aparece dos veces, el total es 19.

Dadas $M$ secuencias de longitud 5 ($1 \leq M \leq 50,000$) con sus nodos de inicio, calcula cuántos códigos se descartan, módulo 1234567.

Entrada

• Línea $1$: enteros $N$ y $M$ separados por un espacio.
• Líneas $2..N$: la línea $i+1$ contiene el entero $p_i$, padre del nodo $i$ ($0 \leq p_i < i$).
• Líneas $N+1..N+M$: la línea $N+i$ describe la secuencia $i$ que no aparece. Contiene $v_i$ y $s_i$ separados por un espacio. $v_i$ es el nodo inicial y $s_i$ una cadena de 5 dígitos que no aparece desde $v_i$ hacia arriba. La raíz está al menos 4 pasos por encima de $v_i$.

Salida

• Línea $1$: un entero, número de configuraciones descartadas módulo 1234567.

Ejemplos

Entrada 1

6 2
0
1
2
3
3
4 01234
5 91234

Salida 1

19

Autor del problema: Jacob Steinhardt, 2014