Krowy ciągle sprawiają kłopoty, jeżdżąc traktorem Farmer John, więc ukrył klucze w nowym eleganckim sejfie w biurze. Niezrażone postanowiły go otworzyć.

Sejf ma skomplikowany system kodu. Wprowadzanie tworzy ukorzenione drzewo $N$ wierzchołków ($1 \leq N \leq 20,000$), każdy wymaga cyfry od 0 do 9. Numeracja to $0..N-1$.

Wiedzą tylko, że pewne ciągi długości 5 nie występują na określonych ścieżkach w górę drzewa.

Na przykład drzewo z korzeniem A wygląda tak:

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

Mogą wiedzieć, że 01234 nie zaczyna się w $F$, a 91234 w $E$. Wyklucza to 19 kodów, wszystkie postaci:

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

lub

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

po uwzględnieniu, że:

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

występuje dwa razy, otrzymujemy 19.

Mając $M$ ciągów długości 5 ($1 \leq M \leq 50,000$) i wierzchołki początkowe, oblicz liczbę wykluczonych kodów modulo 1234567.

Wejście

• Wiersz $1$: całkowite $N$ i $M$ rozdzielone spacją.
• Wiersze $2..N$: wiersz $i+1$ zawiera całkowite $p_i$, rodzica wierzchołka $i$ ($0 \leq p_i < i$).
• Wiersze $N+1..N+M$: wiersz $N+i$ opisuje niewystępujący ciąg $i$. Zawiera $v_i$ i $s_i$ rozdzielone spacją. $v_i$ to wierzchołek początkowy, a $s_i$ napis 5 cyfr niewystępujący od $v_i$ w górę. Korzeń jest co najmniej 4 kroki nad $v_i$.

Wyjście

• Wiersz $1$: liczba całkowita wykluczonych konfiguracji modulo 1234567.

Przykład

Wejście 1

6 2
0
1
2
3
3
4 01234
5 91234

Wyjście 1

19

Autor zadania: Jacob Steinhardt, 2014