**Time limit:**1.00 s**Memory limit:**512 MB

**Input**

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.

**Output**

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

**Constraints**

- $1 \le n \le 5000$

- $1 \le k \le 10^5$

- the total length of the words is at most $10^6$

**Example**

Input:

`ababc`

4

ab

abab

c

cb

Output:

`2`

Explanation: The possible ways are

`ab+ab+c`

and `abab+c`

.