
77  The 9th Zhejiang University Programming Contest  H
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:
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 ([AZ]). S is nonempty 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 nonempty 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 