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
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 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$.
$1 \leq N \leq 1\,
Each word (family name and dictionary) has a length
between $1$ and
(inclusive), and uses only characters a–z.
The number of meanings of a word in the dictionary is at
least $1$ and at most
Dictionary words are distinct.
|Sample Input 1
||Sample Output 1