As vacas vivem causando problemas passeando no trator de Farmer John, então ele escondeu as chaves num cofre novo e elegante no escritório. Sem se intimidarem, elas tentarão abri-lo.

O cofre usa um sistema de código complicado. A entrada é uma árvore enraizada de $N$ nós ($1 \leq N \leq 20,000$), cada um exigindo um dígito de 0 a 9. Os nós são numerados $0..N-1$.

Elas sabem apenas que certas sequências de comprimento 5 não ocorrem em determinados caminhos para cima na árvore.

Por exemplo, suponha esta árvore com raiz A:

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

Podem saber que 01234 não ocorre desde $F$ e 91234 desde $E$. Isso exclui 19 códigos, todos da forma:

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

ou

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

considerando que:

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

aparece duas vezes, o total é 19.

Dadas $M$ sequências de comprimento 5 ($1 \leq M \leq 50,000$) e seus nós iniciais, calcule quantos códigos foram excluídos, módulo 1234567.

Entrada

• Linha $1$: inteiros $N$ e $M$ separados por espaço.
• Linhas $2..N$: a linha $i+1$ contém o inteiro $p_i$, pai do nó $i$ ($0 \leq p_i < i$).
• Linhas $N+1..N+M$: a linha $N+i$ descreve a sequência $i$ que não ocorre. Contém $v_i$ e $s_i$ separados por espaço. $v_i$ é o nó inicial e $s_i$ uma cadeia de 5 dígitos ausente desde $v_i$ para cima. A raiz fica ao menos 4 passos acima de $v_i$.

Saída

• Linha $1$: um inteiro dando as configurações excluídas, módulo 1234567.

Exemplos

Entrada 1

6 2
0
1
2
3
3
4 01234
5 91234

Saída 1

19

Autor do problema: Jacob Steinhardt, 2014