An archivist reads a scroll written as one unbroken string of lowercase glyphs, with no spaces. A dictionary of allowed words is provided. A reading of the scroll is an ordered sequence of dictionary words that concatenate to exactly the scroll string; a word may be reused any number of times.
Count the number of distinct readings of the scroll.
Input format
Line 1: the scroll string (lowercase letters, no spaces).
Line 2: an integer m, the dictionary size.
Next m lines: one dictionary word each (lowercase letters, all distinct).
Output format
A single integer: the number of distinct readings.
Constraints
- 1 <= length of the scroll <= 30
- 1 <= m <= 10
- 1 <= length of each dictionary word <= 10
- Dictionary words are distinct.