Le mucche continuano a causare guai facendo giri sul trattore di Farmer John, che ha nascosto le chiavi in una nuova elegante cassaforte in ufficio. Imperterrite, cercheranno di aprirla.

La cassaforte usa un sistema di codice complicato. L'inserimento è un albero radicato di $N$ nodi ($1 \leq N \leq 20,000$), ciascuno richiede una cifra da 0 a 9. I nodi sono numerati $0..N-1$.

Sanno soltanto che alcune sequenze di lunghezza 5 non compaiono su determinati percorsi verso l'alto nell'albero.

Per esempio, supponi questo albero con radice A:

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

Possono sapere che 01234 non compare da $F$ e 91234 da $E$. Questo esclude 19 codici, tutti quelli della forma:

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

oppure

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

tenendo conto che:

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

compare due volte, si ottiene 19.

Date $M$ sequenze di lunghezza 5 ($1 \leq M \leq 50,000$) coi nodi iniziali, calcola quanti codici sono esclusi, modulo 1234567.

Input

• Riga $1$: interi $N$ e $M$ separati da spazio.
• Righe $2..N$: la riga $i+1$ contiene l'intero $p_i$, padre del nodo $i$ ($0 \leq p_i < i$).
• Righe $N+1..N+M$: la riga $N+i$ descrive la sequenza $i$ assente. Contiene $v_i$ e $s_i$ separati da spazio. $v_i$ è il nodo iniziale e $s_i$ una stringa di 5 cifre assente da $v_i$ verso l'alto. La radice è almeno 4 passi sopra $v_i$.

Output

• Riga $1$: un intero che dà le configurazioni escluse, modulo 1234567.

Esempi

Input 1

6 2
0
1
2
3
3
4 01234
5 91234

Output 1

19

Autore del problema: Jacob Steinhardt, 2014