Die Kühe sorgen ständig für Ärger mit Fahrten auf Farmer Johns Traktor. Daher versteckt er die Schlüssel in einem schicken neuen Safe im Büro. Unbeirrt wollen die Kühe ihn knacken.

Der Safe hat ein kompliziertes Codesystem. Die Eingabe bildet einen verwurzelten Baum mit $N$ Knoten ($1 \leq N \leq 20,000$), die jeweils eine Ziffer von 0 bis 9 benötigen. Die Knoten sind $0..N-1$ nummeriert.

Sie wissen nur, dass bestimmte Folgen der Länge 5 auf bestimmten aufwärts verlaufenden Baumpfaden nicht vorkommen.

Betrachte etwa diesen Baum mit Wurzel A:

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

Sie könnten wissen, dass 01234 ab $F$ und 91234 ab $E$ nicht vorkommen. Das schließt 19 Codes aus, alle der Form:

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

oder

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

unter Berücksichtigung, dass:

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

zweimal erscheint, ergibt sich 19.

Bestimme aus $M$ Folgen der Länge 5 ($1 \leq M \leq 50,000$) und ihren Startknoten die Zahl ausgeschlossener Codes modulo 1234567.

Eingabe

• Zeile $1$: durch Leerzeichen getrennte ganze Zahlen $N$ und $M$.
• Zeilen $2..N$: Zeile $i+1$ enthält die ganze Zahl $p_i$, den Elternknoten von $i$ ($0 \leq p_i < i$).
• Zeilen $N+1..N+M$: Zeile $N+i$ beschreibt die nicht vorkommende Folge $i$ mit $v_i$ und $s_i$, durch Leerzeichen getrennt. $v_i$ ist der Startknoten, $s_i$ eine 5-stellige Zeichenkette, die ab $v_i$ nach oben nicht vorkommt. Die Wurzel liegt garantiert mindestens 4 Schritte über $v_i$.

Ausgabe

• Zeile $1$: eine ganze Zahl, die ausgeschlossenen Konfigurationen modulo 1234567.

Beispiele

Eingabe 1

6 2
0
1
2
3
3
4 01234
5 91234

Ausgabe 1

19

Aufgabenautor: Jacob Steinhardt, 2014