Farmer John has N spotted cows and N spotless cows. As a geneticist, FD is certain that the spots on his cows are caused by a mutation in the cow's genome.
For a lot of money, the FD issued the genomes of his cows. Each genome is a string of length M, consisting of four characters A, C, G, T. When he wrote out the genomes of all cows, he got the table below for N=3:
Position: 1 2 3 4 5 6 7 ... M
Spotted Cow 1: A A T C C C A ... T
Spotted Cow 2: G A T T G C A ... A
Spotted Cow 3: G G T C G C A ... A
Cow without spots 1: A C T C C C A ... G
Cow without spots 2: A G T T G C A ... T
Cow without spots 3: A G T T C C A ... T
Looking closely at this table, he suggested that positions 2 and 4 might be responsible for the spotting. Because by looking at the characters in these positions, the FD can predict which of his cows are spotted and which are not (for example, if he sees G and C, then the cow is not spotted).
FD suggested that it could be explained by a set of three different positions. Help him count the number of three different positions that could explain the spotting.
INPUT FORMAT:
The first input line contains NN (1≤N≤500) and MM (3≤M≤50). Each of the following N lines contains M characters. This is a description of the genomes of spotted cows. The next N lines describe the genomes of spotless cows.
OUTPUT FORMAT:
Compute the number of sets from three different positions that can explain the spotting. A plurality of three different positions can explain spotting if spotting can be predicted absolutely accurately for a population of FD cows by analyzing these three positions of the genome.
| Input |
Output |
|
3 8
ATCCCAT
GATTGCAA
GGTCGCAA
ACTCCAG
ACTCGCAT
ACTTCCAT
|
22 |