ZOJ Problem Set - 3181
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.
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 number of ways to cover the target string with the given tiles mod 1000000007
3 ABABA 1 ABA AA 2 AA AA AA 1 BB
1 2 0
Author: HANG, Hang
Contest: The 9th Zhejiang University Programming Contest