소들이 Farmer John의 트랙터를 타며 계속 문제를 일으켜 그는 사무실의 멋진 새 금고에 열쇠를 숨겼습니다. 소들은 굴하지 않고 금고를 열기로 했습니다.

금고는 복잡한 암호 체계로 보호됩니다. 입력 체계는 $N$개 노드($1 \leq N \leq 20,000$)의 루트 있는 트리이며, 각 노드에 0부터 9까지 숫자가 필요합니다. 노드는 $0..N-1$로 번호가 매겨집니다.

소들은 특정 위쪽 경로에 어떤 길이 5의 수열이 나타나지 않는다는 것만 압니다.

예를 들어 A가 루트인 다음 트리라면:

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

$F$에서 01234가, $E$에서 91234가 나타나지 않는다고 알 수 있습니다. 그러면 다음 형태의 암호 19개가 제외됩니다.

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

또는

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

다음이:

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

두 번 나타나는 것을 고려하면 19개입니다.

길이 5의 수열 $M$개($1 \leq M \leq 50,000$)와 시작 노드가 주어지면 제외된 암호 수를 구하세요. 1234567로 나눈 나머지를 계산하세요.

입력

• $1$번 줄: 공백으로 구분된 정수 $N$, $M$.
• $2..N$번 줄: $i+1$번 줄은 노드 $i$의 부모인 정수 $p_i$를 포함합니다($0 \leq p_i < i$).
• $N+1..N+M$번 줄: $N+i$번 줄은 나타나지 않는 $i$번째 수열로, 공백으로 구분된 $v_i$, $s_i$를 포함합니다. $v_i$는 시작 노드, $s_i$는 $v_i$에서 위로 갈 때 나타나지 않는 5자리 숫자 문자열입니다. 루트는 $v_i$에서 최소 4단계 위에 있습니다.

출력

• $1$번 줄: 제외된 구성 수를 1234567로 나눈 나머지인 정수 하나.

예제

입력 1

6 2
0
1
2
3
3
4 01234
5 91234

출력 1

19

문제 작성자: Jacob Steinhardt, 2014