牛たちが 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

2 回現れることを考慮して 19 通りになります。

$M$ 個（$1 \leq M \leq 50,000$）の長さ 5 の列と開始頂点から、排除される暗証番号の数を求めてください。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