Code Submission Evaluation System Login

CSES Problem Set

Word Combinations


Task | Statistics


CSES - Word CombinationsCSES - Word Combinations

Time limit:1.00 s Memory limit:512 MB

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?

Input

The first input line has a string containing $m$ 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
Example

Input:
ababc
4
ab
abab
c
cb


Output:
2

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