Геноміка великої рогатої худоби (Срібло)#10525
У Фермера Джона є плямистих корів та корів без плям. Нещодавно закінчивши курс з генетики великої рогатої худоби, він переконаний, що плями на його коровах спричинені мутаціями в геномі.
Заплативши чималі гроші, Фермер Джон визначив геноми всіх своїх корів. Кожен геном являє собою рядок довжини , що складається з чотирьох символів: A, C, G та . Розташувавши геноми корів одна під одною, він отримує таблицю, подібну до наведеної нижче, для випадку 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 Уважно вивчивши цю таблицю, він помічає, що позицій та достатньо, щоб відрізнити плямистих корів від корів без плям. Іншими словами, дивлячись лише на символи в цих двох позиціях, Фермер Джон може однозначно визначити, чи є корова плямистою, чи ні. Наприклад, якщо в позиції знаходиться , а в позиції — , то корова обов'язково є плямистою.
Фермер Джон вважає, що наявність плям можна пояснити, розглядаючи деякий набір із трьох різних позицій у геномі. Допоможіть йому визначити кількість наборів із трьох різних позицій, які дозволяють відрізнити плямистих корів від корів без плям.
У першому рядку містяться n~(1 \le n \le 500) та m~(3 \le m \le 50). У наступних рядках містяться рядки довжини , що описують геноми плямистих корів. В останніх рядках містяться геноми корів без плям.
Виведіть кількість наборів із трьох різних позицій, які дозволяють пояснити наявність плям. Набір із трьох позицій дозволяє пояснити наявність плям, якщо ознаку «плямистість» можна визначити зі стовідсотковою точністю для всіх корів Фермера Джона, розглядаючи лише символи в цих трьох позиціях їхніх геномів.
Приклад 1