Problem H
What Does It Mean?
Bob has always been interested in his family history, and above all else his family name’s meaning. Unfortunately for Bob, no one else in his family has ever had any similar interest whatsoever. Because of this the family name seems to have changed at random points in time without any reason that Bob can find.
You have a dictionary of words that may make up part of Bob’s family name, and one or more unique meanings associated with each word. By concatenating one or more of these dictionary words to construct exactly the family name, count the number of different meanings associated with these different constructions.
Input
The first line contains an integer $N$ and a word $W$, indicating the number of words in the dictionary and the family name respectively. The following $N$ lines contain the dictionary. Each dictionary line starts with the dictionary word followed by an integer representing the number of meanings of the word.
Output
Output the number of possible meanings Bob’s family name can have. As this number can be very large, output it modulo $1\, 000\, 000\, 007$.
Limits
-
$1 \leq N \leq 1\, 000$
-
Each word (family name and dictionary) has a length between $1$ and $32$ characters (inclusive), and uses only characters a–z.
-
The number of meanings of a word in the dictionary is at least $1$ and at most $10\, 000$.
-
Dictionary words are distinct.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 heimark hei 2 mark 2 heim 1 ark 2 heima 1 |
6 |
