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 nodes, each of which requires a digit between and . The nodes are indexed .
The only information that the cows have is that certain sequences of length 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
The cows might know that the sequence does not occur starting at F, and that the sequence does not occur starting at E. This information rules out possible passcodes: all those of the form
4 <- 3 <- 2 <- 1 <- *
^
|
0
or
4 <- 3 <- 2 <- 1 <- 9
^
|
*
which gives once we account for the fact that
4 <- 3 <- 2 <- 1 <- 9
^
|
0
appears twice.
Given length- 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 .
Input Format
Line : Two space-separated integers, and .
Lines : Line contains a single integer , denoting the parent of node in the tree.
Lines : Line describes the -th sequence known not to occur in the code. The line will contain and separated by a space, where is the starting node of the sequence, and is a -digit string known not to occur starting at and proceeding upward in the tree. It is guaranteed that the root is at least steps upward from .
Output Format
Line : A single integer giving the number of ruled-out configurations, modulo .
