Codejamon Cipher (Small)

Codejamon monsters talk in enciphered strings. Each kind of monster has its own vocabulary, a list of $V$ different words made of lowercase English letters.

When a monster speaks, it first builds a sentence out of words from its vocabulary. The same word may appear several times in one sentence. It then turns the sentence into an enciphered string in two steps.

1. Shuffle the letters of each word at random.
2. Remove all spaces.

Given an enciphered string, count how many original sentences could have produced it. Two sentences differ when their sequences of words differ, and two vocabulary words that become equal after shuffling still count as different words. For example, with the vocabulary ["this", "is", "a", "dog", "god"], the enciphered string ishtsiaogd comes from four sentences.

• is this a dog
• is this a god
• this is a dog
• this is a god

You have $S$ enciphered strings from the same monster. For each one, report the number of possible original sentences. The answer can be very large, so print it modulo the prime $10^9 + 7$.

The first line contains the number of test cases $T$.

The first line of each test case contains two integers $V$ and $S$, the size of the vocabulary and the number of enciphered strings. The next $V$ lines each contain one word of the vocabulary. Every word consists of lowercase English letters, and the words are different from each other. The next $S$ lines each contain one enciphered string, also made of lowercase English letters.

Every enciphered string is valid: at least one original sentence produces it.

For each test case, print one line in the form Case #x: y, where x is the test case number starting from 1 and y is the list of the $S$ answers separated by single spaces, in the order the strings were given. Each answer is taken modulo $10^9 + 7$.

• $1 \le T \le 100$
• $5 \le V \le 10$
• $1 \le S \le 5$
• Each word of a vocabulary has length between 1 and 5.
• Each enciphered string has length between 1 and 50.