Коровы постоянно создают неприятности, катаясь на тракторе Farmer John, поэтому он спрятал ключи в новом изящном сейфе в кабинете. Коровы не сдаются и решили взломать его.

Сейф защищён сложной системой кода. Ввод организован как корневое дерево из $N$ узлов ($1 \leq N \leq 20,000$), каждому нужна цифра от 0 до 9. Узлы имеют номера $0..N-1$.

Коровы знают лишь, что некоторые последовательности длины 5 не встречаются на определённых путях вверх по дереву.

Например, пусть дерево с корнем A таково:

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

Они могут знать, что 01234 не начинается в $F$, а 91234 — в $E$. Это исключает 19 кодов всех следующих форм:

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

или

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

с учётом того, что:

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

встречается дважды, получается 19.

Даны $M$ последовательностей длины 5 ($1 \leq M \leq 50,000$) с начальными узлами. Найдите количество исключённых кодов по модулю 1234567.

Входные данные

• Строка $1$: целые $N$ и $M$ через пробел.
• Строки $2..N$: строка $i+1$ содержит целое $p_i$, родителя узла $i$ ($0 \leq p_i < i$).
• Строки $N+1..N+M$: строка $N+i$ описывает последовательность $i$, которая не встречается. Она содержит $v_i$ и $s_i$ через пробел. $v_i$ — начальный узел, $s_i$ — строка из 5 цифр, не встречающаяся от $v_i$ вверх. Корень гарантированно минимум на 4 шага выше $v_i$.

Выходные данные

• Строка $1$: одно целое — число исключённых конфигураций по модулю 1234567.

Примеры

Входные данные 1

6 2
0
1
2
3
3
4 01234
5 91234

Выходные данные 1

19

Автор задачи: Jacob Steinhardt, 2014