Time limit per test: 0.25
Memory limit: 65536
Consider an alphabet consisting of terminal characters 'a' and 'b' and non-terminal characters 1,2,...,N
. Each non-terminal character K
has a description, which is a string of terminal and non-terminal characters; the non-terminal characters in the description are less than K
. The description may be empty.
You take the string containing single non-terminal character N
and replace all non-terminal characters in it by their definitions until we obtain a string containing only terminal characters, which is called the final string.
The task is: given a nonempty string S
of terminal characters, determine the number of its occurences in the final string.
The first line of the input contains single integer N
≤ 30). The second line contains string S
containing at most 100 characters. The rest of the input contains the non-terminal characters' descriptions. The K
+2-nd line (1≤ K
) contains the description of K
-th character. It starts with a non-negative integer LK
, followed by LK
characters of the alphabet separated by spaces. The sum of all LK
does not exceed 500.
The only line of the output must contain the answer without leading zeroes.
2 a b
3 a 1 b
Novosibirsk SU Contest #2, by Novosibirsk Team #1