Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3181
Cover the String

Time Limit: 2 Seconds      Memory Limit: 32768 KB

You are given a target string and a list of string tiles. You are asked to cover the target string with these tiles according to the following rules:

  • Each tile can cover a sub-string of the target string if and only if the two strings are exactly matched.
  • All the characters must be covered by at least one tile.
  • You can use a tile as many times as you want. You do not have to use all the tiles.
  • The first tile must exactly cover the head of the string, while the last one must exactly cover the tail of the string.
  • Each pair of adjecent tiles you used must overlap with each other by at least one character. (A counter example is given by the invalid case Tiling 2 in the following picture.)
  • For each pair of adjecent tiles you used, the latter one must start at a position strictly after the start position of the former one. Similarly, the latter one must end at a position strictly after the end position of the former one. (A counter example is given by the invalid cases Tiling 3 and Tiling 4 in the following picture)
Some examples of valid and invalid cases

You are asked to calculate the number of ways to cover the target string with the given tiles. The answer may be very large, so just output the result mod 1000000007.

Input

The first line of the input contains an integer t (t <= 50), indicate the number of cases.

For each case, the first line gives the target string S containing only capital letters ([A-Z]). S is non-empty and its length is no more than 1000. The second line contains an positive integer n (n <= 200), indicate the number of tiles. Then n lines follow, representing all the n tiles. Each tile is a non-empty string with length no more than 200, and contains only capital letters too. There may be same tiles and they are consider as different kinds of tiles.

Cases are separated by one blank line.

Output

Output number of ways to cover the target string with the given tiles mod 1000000007

Sample Input

3
ABABA
1
ABA

AA
2
AA
AA

AA
1
BB

Sample Output

1
2
0

Author: HANG, Hang
Contest: The 9th Zhejiang University Programming Contest
Submit    Status