Description

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 \leq N \leq 20,000)$ nodes, each of which requires a digit between $0$ and $9$. The nodes are indexed $0 \dots 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.

Given $M$ $(1 \leq M \leq 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$.

Input Format

Line $1$: Two space-separated integers, $N$ and $M$.

Lines $2\dots N$: Line $i+1$ contains a single integer $p(i)$, denoting the parent of node i in the tree $(0 \leq p(i) < i)$.

Lines $N+1\dots 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)$.

Output Format

Line $1$: A single integer giving the number of ruled-out configurations,modulo $1234567$.

6 2 
0 
1 
2 
3 
3 
4 01234 
5 91234 

19