Given a string $s$ with $n$ characters and a dictionary with $k$ words $w_1, w_2, \ldots, w_k$, compute how many ways there is to produce the given string by concatenating words in the dictionary.

Input

The first line has the exactly $n$ characters, the string $s$.

The next line contains a single integer, $k$, the number of words in the dictionary.

The rest $k$ lines each contain one word in the dictionary.

Output

Output the number of ways modulo $10^9+7$

Limits

• $1 \le n \le 5000$
• $1 \le k \le 10^5$
• The combined length of all words in the dictionary is at most $10^6$.
• Each word consists of only English lower case letters a-z.

Example

Input:

ababc
4
ab
abab
c
cb

Output:

2

Explanation: The ways are ab+ab+c and abab+c.