乳牛總是偷開 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。

給出 $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$ 是從 $v_i$ 開始向上不會出現的五位數字字串。保證從 $v_i$ 向上到根至少需要 4 步。

輸出格式

• 第 $1$ 行：被排除配置數量對 1234567 取模的整數。

範例

輸入格式 1

6 2
0
1
2
3
3
4 01234
5 91234

輸出格式 1

19

題目作者：Jacob Steinhardt，2014