Problem D
Poetry Tower
Alice and Bob are young, aspiring poets. Alice likes variation in poems, so she only gets impressed by a poems that do not contain repeated words (and of course, the words used have to be real words).
Bob has found $N$ six-sided blocks where each side has a letter or a wildcard symbol that can be used to represent any letter. He wants to use them to impress Alice with some really tall poetry. He has decided to put some blocks on top of each other to make a poem, and recite it to her. He thinks this is such a good idea that he has decided to do this for all possible poems Alice would be impressed by. Bob only knows $M$ different real words. Help him figure out how many different poems he could impress Alice with using these blocks.
Note that even though the poems “to be or not” and “tob eor not” can be built in exactly the same way, they count as two poems because Bob only cares about how many poems he can recite, not how many different towers he can build.
Input
The first line of the input consists of two space-separated integers $N$ and $M$. The next $M$ lines consists of the words that Bob knows. Each line has a single word $w$. The next $N$ lines each contain a string of six characters representing a die.
Output
Output the number of different impressive poems Bob can build and recite with the provided blocks.
Limits
-
$1 \leq N \leq 20$.
-
$1 \leq M \leq 8$.
-
Each word that Bob knows is between $1$ and $20$ characters long.
-
All words that Bob knows are unique.
-
Each word that Bob knows consists only of the letters a-z.
-
The sides of each die are only the letters a-z or * (representing a wildcard).
| Sample Input 1 | Sample Output 1 |
|---|---|
6 4 abc idi open def idiope nabcde *abcde bcdefg cccccc ****** |
8 |
