Những cô bò cứ liên tục gây rắc rối vì lấy máy kéo của Farmer John đi chơi, nên ông đã giấu chìa khóa máy kéo trong một chiếc két sắt mới rất tinh xảo đặt tại văn phòng. Không hề nản lòng, những cô bò quyết tâm tìm cách phá khóa chiếc két này.

Két sắt được bảo vệ bởi một hệ thống mật mã khá phức tạp. Hệ thống nhập mật mã được bố trí dưới dạng một cây có gốc gồm \(N\) đỉnh (\(1 \le N \le 20\,000\)), mỗi đỉnh cần được gán một chữ số từ \(0\) đến \(9\). Các đỉnh được đánh số từ \(0\) đến \(N-1\).

Thông tin duy nhất những cô bò có được là một số dãy độ dài \(5\) không xuất hiện dọc theo những đường đi cụ thể hướng lên trên cây.

Ví dụ, giả sử cây có dạng sau và có gốc tại \(A\):

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

Những cô bò có thể biết rằng dãy 01234 không xuất hiện khi bắt đầu tại \(F\), và dãy 91234 không xuất hiện khi bắt đầu tại \(E\). Thông tin này loại trừ \(19\) mật mã: tất cả các mật mã có dạng

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

hoặc

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

Số mật mã bị loại là \(19\) sau khi tính đến việc mật mã

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

xuất hiện hai lần.

Cho \(M\) dãy độ dài \(5\) (\(1 \le M \le 50\,000\)) cùng với đỉnh bắt đầu tương ứng của chúng trên cây, hãy giúp những cô bò xác định có bao nhiêu mật mã đã bị loại trừ. Hãy tính kết quả theo modulo \(1234567\).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), cách nhau bởi một dấu cách.
• Các dòng từ \(2\) đến \(N\): dòng thứ \(i+1\) chứa một số nguyên \(p(i)\), là cha của đỉnh \(i\) trên cây, với \(0 \le p(i) < i\).
• Các dòng từ \(N+1\) đến \(N+M\): dòng thứ \(N+i\) mô tả dãy thứ \(i\) được biết là không xuất hiện trong mật mã. Dòng này chứa \(v(i)\) và \(s(i)\) cách nhau bởi một dấu cách, trong đó \(v(i)\) là đỉnh bắt đầu của dãy, còn \(s(i)\) là một xâu gồm \(5\) chữ số được biết là không xuất hiện khi bắt đầu tại \(v(i)\) và đi dần lên trên cây. Bảo đảm gốc cây cách \(v(i)\) ít nhất \(4\) bước theo hướng đi lên.

Ràng buộc

• \(1 \le N \le 20\,000\).
• \(1 \le M \le 50\,000\).
• \(0 \le p(i) < i\).
• Mỗi \(s(i)\) là một xâu gồm đúng \(5\) chữ số.
• Gốc cây cách mỗi \(v(i)\) ít nhất \(4\) bước theo hướng đi lên.

Dữ liệu ra

• In ra một số nguyên duy nhất là số cấu hình mật mã bị loại trừ, theo modulo \(1234567\).

Ví dụ

6 2
0
1
2
3
3
4 01234
5 91234

19

Nguồn

USACO 2014 US Open, Gold — Problem 3: Code Breaking

Tác giả đề: Jacob Steinhardt, 2014.