The cows keep getting in trouble by taking rides on Farmer John's tractor, so he has hidden the keys to the tractor in a fancy new safe in his office. Undeterred, the cows have vowed to try and break into this safe.

The safe is protected by a rather complicated passcode system. The passcode entry system is arranged as a rooted tree of N (1 <= N <= 20,000) nodes, each of which requires a digit between 0 and 9. The nodes are indexed 0..N-1.

The only information that the cows have is that certain sequences of length 5 do not occur along particular paths upwards through the tree.

For instance, suppose the tree is the following (rooted at A):

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

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

or

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

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

Given M (1 <= M <= 50,000) length-5 sequences, together with their starting nodes in the tree, help the cows figure out how many passcodes have been ruled out. You should compute your answer modulo 1234567.

입력

• Line 1: Two space-separated integers, N and M.
• Lines 2..N: Line i+1 contains a single integer p(i), denoting the parent of node i in the tree (0 <= p(i) < i).
• Lines N+1..N+M: Line N+i describes the ith sequence known not to occur in the code. The line will contain v(i) and s(i) separated by a space, where v(i) is the starting node of the sequence, and s(i) is a 5-digit string known not to occur starting at v(i) and proceeding upward in the tree. It is guaranteed that the root is at least 4 steps upward from v(i).

출력

입출력 예

입력

6 2
0
1
2
3
3
4 01234
5 91234

출력

19

출처:USACO 2014 US Open, Gold