1614: 单词缩写

树树发现好多计算机中的单词都是缩写，如GDB，它的全称是Gnu DeBug的缩写。但是，有时候缩写对应的全称会不固定，如缩写LINUX，可以理解为：

（1）    LINus’s UniX；

（2）    LINUs’s miniX;

（3）    Linux Is Not UniX。

 现在树树给出一个单词缩写，以及一个固定的全称（若干个单词组成，空格隔开）。全称可能会有无效的单词，需要忽略掉，一个合法缩写要求每个有效单词中至少有一个字符出现在缩写中，缩写必须按顺序出现在全称中。

对于给定的缩写和一个固定的全称，问有多少种解释方法？解释方法为缩写的每个字母在全称每个有效单词中出现的位置，有一个字母位置不同，就认为是不同的解释方法。

The sadists who design problems for ACM programming contests often like to include the abbre- viation "ACM" somewhere in their problem descriptions. Thus, in years past, the World Finals has had problems involving "Apartment Construction Management," the "Atheneum of Culture and Movies," the "Association of Cover Manufacturers," "ACM Airlines," the "Association for Computa- tional Marinelife," and even an insect named "Amelia Cheese Mite." However, the number of word combinations beginning with A, C, and M that make sense is finite and the problem writers are starting to run out of ideas (it's hard to think of problems about "Antidisestablishmentarianistic Chthonian Metalinguistics"). Fortunately, modern culture allows more flexibility in designing abbreviations ― consider, for example:

GDB ― Gnu DeBugger
LINUX ― either "LINus's UniX" or "LINUs's miniX" or "Linux Is Not UniX"
SNOBOL ― StriNg Oriented symBOlic Language
SPITBOL ― SPeedy ImplemenTation of snoBOL

The rules used in these examples seem to be:

• Insignificant words (such as "of", "a", "the", etc.) are ignored.
• The letters of the abbreviation must appear, in the correct order, as an ordered sublist of the letters in the significant words of the phrase to be abbreviated.
• At least one letter of the abbreviation must come from every significant word (multiple occurrences of a letter are, of course, treated as distinct).

Of course these rules are often broken in real life. For instance, RADAR is an abbreviation for "RAdio Detecting And Ranging". Under our rules (assuming that "and" is an insignificant word), this would not be a valid abbreviation (however, RADR or RADRAN or DODGING would be valid). You have been asked to take a list of insignificant words and a list of abbreviations and phrases and to determine in how many ways each abbreviation can be formed from the corresponding phrase according to the rules above.

第一行输入一个N，表示有N个无效单词；

   接下来N行分别描述一个由小写字母组成的无效单词；

   最后是若干个询问，先给出缩写（只有大写字母），然后给出一个全称，读入以“LAST CASE”结束。

The input consists of multiple scenarios. Each scenario begins with an integer 100 ≥ n ≥ 1 followed by n insignificant words, all in lower case, one per line with no extra white space. (A line containing 0 indicates end of input.) Following this are one or more test cases for this scenario, one per line, followed by a line containing the phrase "LAST CASE". Each line containing a test case begins with an abbreviation (uppercase letters only) followed by a phrase (lowercase letters and spaces only). The abbreviation has length at least 1 and the phrase contains at least one significant word. No input line (including abbreviation, phrase, and spaces) will contain more than 150 characters. Within these limits, however, abbreviations and phrase words may be any length.

对于每个询问先输出缩写，如果当前缩写不合法，则输出“is not a valid abbreviation”，否则输出“can be formed in i ways”（i表示解释方法种数）。

For each test case, output the abbreviation followed by either

is not a valid abbreviation

or

can be formed in i ways

where i is the number of different ways in which the letters of the abbreviation may be assigned to the letters in the phrase according to the rules above. The value of i will not exceed the range of a 32-bit signed integer.

2
and
of
ACM academy of computer makers
RADAR radio detection and ranging
LAST CASE

ACM can be formed in 2 ways
RADAR is not a valid abbreviation