You are given a string of length $n$ and a dictionary containing $k$ words. In how many ways can you create the string using the words?

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.

• $1 \le n \le 5000$
• $1 \le k \le 10^5$
• the total length of the words is at most $10^6$

Print the number of ways modulo $10^9+7$ .