문제
농부 존은 N마리의 얼룩이 있는 소들과 N마리의 얼룩이 없는 소들을 기르고 있습니다. 그는 방금 소의 유전자에 관한 과정을 마친 후, 자신의 소들의 얼룩이 유전자 변이에 의해 발생한다고 확신합니다.
농부 존은 큰 비용을 들여 자신의 소들의 유전자를 시퀀싱합니다. 각 유전자는 A, C, G, T의 네 문자를 사용하여 길이 M의 문자열로 구성됩니다. 그가 소들의 유전자 정보를 나열하면 다음과 같은 표를 얻게 됩니다 (여기서는 N=3을 예시로 듭니다):
위치: 1 2 3 4 5 6 7 ... M
얼룩 있는 소 1: A A T C C C A ... T
얼룩 있는 소 2: G A T T G C A ... A
얼룩 있는 소 3: G G T C G C A ... A
얼룩 없는 소 1: A C T C C C A ... G
얼룩 없는 소 2: A G T T G C A ... T
얼룩 없는 소 3: A G T T C C A ... T
농부 존은 표를 살펴보며 2번과 4번 위치가 얼룩을 구분하는 데 충분하다고 추측합니다. 즉, 이 두 위치의 문자를 보면 소가 얼룩이 있는지 없는지를 예측할 수 있습니다 (예를 들어, G와 C가 보이면 그 소는 얼룩이 있다고 예측할 수 있습니다).
농부 존은 유전자의 한두 위치뿐만 아니라 세 개의 다른 위치를 보면 얼룩을 설명할 수 있다고 확신합니다. 이제, 세 개의 서로 다른 위치들이 얼룩을 설명할 수 있는 경우의 수를 구하는 문제입니다.
입력
입력의 첫 번째 줄에는 N (1 ≤ N ≤ 500)과 M (3 ≤ M ≤ 50)이 주어집니다. 그 다음 N개의 줄에는 각 얼룩 있는 소의 유전자가 M개의 문자로 이루어진 문자열로 주어집니다. 마지막 N개의 줄에는 얼룩 없는 소들의 유전자가 주어집니다.
출력
세 개의 서로 다른 위치 조합이 얼룩을 설명할 수 있는 경우의 수를 세세요. 세 개의 위치 조합이 얼룩을 설명할 수 있다면, 그 세 위치만 보고 농부 존의 소들 중에서 얼룩 여부를 정확하게 예측할 수 있어야 합니다.
예제
3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT
22
로그인해야 코드를 작성할 수 있어요.