The cows have vowed to break into Farmer John's new safe to get the keys to his tractor.

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 the cows have is that certain sequences of length 5 do not occur along particular paths upwards through the tree. For instance, the cows might know that the sequence 01234 does not occur starting at some node F (reading upward toward the root), which rules out a number of possible passcodes.

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. The line contains v(i) and s(i), 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).

A single integer giving the number of ruled-out configurations, modulo 1234567.

riseoj 작성

출처 올림피아드 > USACO > 2013-2014 > US Open > Gold