Геноміка великої рогатої худоби (Срібло)
У фермера Джона є n корів з плямами і n корів без плям. Як генетик, Джон впевнений, що плями на його коровах викликані мутацією в геномі.
За великі гроші Джон отримав геноми своїх корів. Кожен геном представлений рядком довжини m, що складається з чотирьох символів: A, C, G, T. Після запису геномів усіх корів, він отримав таблицю, як показано нижче для 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 рядків описують геноми корів без плям.
Вихідні дані
Обчисліть кількість наборів з трьох різних позицій, які можуть пояснювати плямистість. Набір з трьох різних позицій може пояснювати плямистість, якщо плямистість може бути передбачена абсолютно точно для популяції корів Джона, аналізуючи ці три позиції геному.