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.