Bò luôn gây rắc rối khi lái máy kéo Farmer John, nên ông giấu chìa khóa vào két mới sang trọng trong văn phòng. Không nản, chúng quyết thử mở két.

Két được bảo vệ bằng hệ thống mã phức tạp. Nhập mã tổ chức thành cây có gốc gồm $N$ nút ($1 \leq N \leq 20,000$), mỗi nút cần chữ số 0 đến 9. Nút đánh số $0..N-1$.

Chúng chỉ biết một số chuỗi dài 5 không xuất hiện trên những đường đi lên cụ thể trong cây.

Ví dụ cây sau có gốc A:

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

Chúng có thể biết 01234 không xuất hiện từ $F$ và 91234 từ $E$. Điều này loại 19 mã, tất cả dạng:

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

hoặc

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

sau khi tính đến việc:

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

xuất hiện hai lần, tổng là 19.

Cho $M$ chuỗi dài 5 ($1 \leq M \leq 50,000$) và nút bắt đầu, hãy tính số mã bị loại, modulo 1234567.

Dữ liệu vào

• Dòng $1$: số nguyên $N$ và $M$ cách nhau bởi dấu cách.
• Các dòng $2..N$: dòng $i+1$ chứa số nguyên $p_i$, cha nút $i$ ($0 \leq p_i < i$).
• Các dòng $N+1..N+M$: dòng $N+i$ mô tả chuỗi thứ $i$ không xuất hiện. Chứa $v_i$ và $s_i$ cách nhau bởi dấu cách. $v_i$ là nút bắt đầu, $s_i$ là chuỗi 5 chữ số không xuất hiện từ $v_i$ đi lên. Bảo đảm gốc cách $v_i$ ít nhất 4 bước lên.

Dữ liệu ra

• Dòng $1$: một số nguyên, số cấu hình bị loại modulo 1234567.

Ví dụ

Dữ liệu vào 1

6 2
0
1
2
3
3
4 01234
5 91234

Dữ liệu ra 1

19

Tác giả bài toán: Jacob Steinhardt, 2014