Bovine Genomics (Silver)#10525
Farmer John owns spotty cows and cows without spots. Having just completed a course in bovine genetics, he is convinced that the spots on his cows are caused by mutations in the bovine genome.
At great expense, Farmer John sequences the genomes of all his cows. Each genome is a string of length consisting of the four characters , , , and . When he lines up the genomes of his cows, he obtains a table like the following, shown here for n = 3:
Positions: 1 2 3 4 5 6 7 ... M
Spotty Cow 1: A A T C C C A ... T
Spotty Cow 2: G A T T G C A ... A
Spotty Cow 3: G G T C G C A ... A
Plain Cow 1: A C T C C C A ... G
Plain Cow 2: A G T T G C A ... T
Plain Cow 3: A G T T C C A ... T Looking carefully at this table, he notices that positions and are sufficient to distinguish the spotty cows from the plain cows. In other words, by looking only at the characters at these two positions, Farmer John can determine with certainty whether a cow is spotty or plain. For example, if he sees at position and at position , the cow must be spotty.
Farmer John believes that spottiness can be explained by looking at a set of three distinct positions in the genome. Please help him count the number of sets of three distinct positions that can distinguish the spotty cows from the plain cows.
The first line contains n~(1 \le n \le 500) and m~(3 \le m \le 50). The next lines each contain a string of characters, describing the genomes of the spotty cows. The final lines describe the genomes of the plain cows.
Print the number of sets of three distinct positions that can explain spottiness. A set of three positions explains spottiness if the spottiness trait can be predicted with perfect accuracy for all of Farmer John's cows by looking only at those three positions in their genomes.
Example 1