Zoo

Esmeralda is building a zoo with $N$ cages in a long row. Each cage must be filled with an animal. She has $K$ different species to choose from, which we call A, B, C, and so on. She may put the same species in multiple cages, but not in two cages right next to each other. She also knows that some animals do not get along. More precisely, there are $M$ "quarrel groups" of species, and Esmeralda does not want to place two animals from the same quarrel group in adjacent cages. In how many ways can Esmeralda place animals in the cages?

The first line contains three integers: $2\le N \le 15$, the number of cages, $2\le K \le 10$, the number of species, and $2 \le M\le 5$, the number of quarrel groups. Each of the following $M$ lines contains a string of between $2$ and $K$ letters: a quarrel group of species that do not tolerate each other pairwise. Only the first $K$ letters of the alphabet (and only uppercase) may appear in the strings, and no letter appears more than once in the same string.

The program should print one integer, the number of ways Esmeralda can place animals. For the given input, the answer never exceeds 2 billion.

In the first example, all species get along. In the first cage, Esmeralda can choose among 4 species. For the second and third cages there are three possibilities each, because the species cannot be the same as in the preceding cage. In total there are $4\cdot 3\cdot 3=36$ possible placements.

In the second example, we know that Baboon and Elephant cannot be next to each other. We also know that Baboon, Antelope, Dingo, and Citrus Butterfly are all enemies, so none of these can be placed next to each other. Esmeralda must therefore put an elephant in every other cage and choose freely among antelope, dingo, and citrus butterfly in the remaining ones. This gives 9 possibilities if she starts with an elephant and 9 possibilities if she starts with one of the other animals.