- Time limit: 1.00 s
- Memory limit: 512 MB
The first input line has a string containing $n$ characters between a–z.
The second line has an integer $k$: the number of words in the dictionary.
Finally there are $k$ lines describing the words. Each word is unique and consists of characters a–z.
Print the number of ways modulo $10^9+7$.
- $1 \le n \le 5000$
- $1 \le k \le 10^5$
- the total length of the words is at most $10^6$
Explanation: The possible ways are