Phá Mã (Gold)

Cho một cây có gốc gồm $N$ đỉnh, đánh số từ $0$ đến $N-1$, với đỉnh $0$ là gốc. Mỗi đỉnh $i$ ($i\ge 1$) có cha là $p(i)$ với $p(i)<i$.

Một "mã khóa" là phép gán mỗi đỉnh một chữ số từ 0 đến 9. Có $M$ ràng buộc cấm, mỗi ràng buộc gồm một đỉnh $v$ và một chuỗi 5 chữ số $s$. Ràng buộc này cấm các mã khóa mà khi đọc chữ số trên đường đi từ $v$ lên gốc (5 bước), ta thu được chuỗi $s$.

Cụ thể, nếu đường đi từ $v$ lên gốc đi qua các đỉnh $v,p(v),p(p(v)),p(p(p(v))),p(p(p(p(v))))$, thì chuỗi chữ số tại 5 đỉnh này không được bằng $s$.

Đảm bảo rằng mỗi đỉnh có ít nhất 4 tổ tiên (đường đi lên gốc có ít nhất 5 đỉnh).

Hãy đếm số mã khóa bị loại bỏ (vi phạm ít nhất một ràng buộc), modulo $1234567$.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $M$.

• $N-1$ dòng tiếp theo, dòng thứ $i$ chứa $p(i)$ — cha của đỉnh $i$ (với $i$ từ $1$ đến $N-1$).

• $M$ dòng tiếp theo, mỗi dòng chứa số nguyên $v$ và chuỗi 5 chữ số $s$ — một ràng buộc cấm.

Dữ liệu ra

Một số nguyên duy nhất — số mã khóa bị loại bỏ, modulo $1234567$.

Ràng buộc

• $1\le N\le 20000$
• $1\le M\le 50000$
• $0\le p(i)<i$
• $0\le v<N$
• Chuỗi $s$ có đúng 5 ký tự, mỗi ký tự là chữ số 0-9

Ví dụ