Forbidden Tractor Passcodes

Farmer John has hidden the keys to his tractor in a fancy safe with a complicated passcode system. The passcode is given by assigning a digit from 0 to 9 to each node in a rooted tree with \(N\) nodes (indexed \(0\) to \(N-1\)).

The cows have learned \(M\) facts of the following form: for a given node \(X\) (with depth at least 5), the sequence of digits encountered when starting at \(X\) and moving upward through its four ancestors (i.e. the unique 5‑node upward chain) cannot equal a specified 5‑digit sequence. In other words, if we denote the digits assigned on the chain as \[ d(X),\; d(\mathit{parent}(X)),\; d(\mathit{parent}^2(X)),\; d(\mathit{parent}^3(X)),\; d(\mathit{parent}^4(X)), \] then for a forbidden fact given as
X a b c d e (each of \(a,b,c,d,e\) is a digit), the assignment is ruled out if \[ (d(X), d(\mathit{parent}(X)), d(\mathit{parent}^2(X)), d(\mathit{parent}^3(X)), d(\mathit{parent}^4(X))) = (a,b,c,d,e). \]

Given the tree and \(M\) such facts, compute the number of complete assignments (i.e. assignments of digits to all \(N\) nodes) that must be ruled out – that is, assignments which definitely contain at least one of the forbidden sequences. Output your answer modulo \(1234567\). The total number of assignments (without restrictions) is \(10^N\).

Note: The input guarantees that for every fact with starting node \(X\), the depth of \(X\) is at least 5 so that the required 5‑node chain exists.

inputFormat

The first line contains two integers \(N\) and \(M\) (\(1 \le N \le 20000,\; 1 \le M \le 50000\)).

The next \(N-1\) lines describe the tree. For \(i=1,2,\dots,N-1\), the \(i\)-th of these lines contains a single integer \(p_i\) (\(0 \le p_i < i\)) indicating that the parent of node \(i\) is \(p_i\). Node \(0\) is the root.

The following \(M\) lines each contain a fact. Each fact consists of 6 integers: the first is \(X\) (the starting node) and the next five digits \(a\, b\, c\, d\, e\) (each between 0 and 9) representing the forbidden sequence for the upward chain starting at \(X\):
\(d(X)=a,\; d(\mathit{parent}(X))=b,\; d(\mathit{parent}^2(X))=c,\; d(\mathit{parent}^3(X))=d,\; d(\mathit{parent}^4(X))=e.\)

outputFormat

Output a single integer: the number of assignments that are ruled out (i.e. that must contain at least one forbidden sequence), modulo \(1234567\).

sample

6 2
0
1
2
3
0
5 0 1 2 3 4
4 9 1 2 3 4

19