Сет
Сет
В популярной карточной игре SET цель игрока состоит в том, чтобы идентифицировать определенную тройку карт с некоторыми особыми свойствами, называемую набором. На каждой карточке изображено несколько фигурок, которые различаются по количеству, форме, прозрачности и цвету.
Марин и Иосип недавно купили колоду этих карт и теперь не могут оторваться от игры. Они настолько научились замечать наборы, что вскоре стало скучно, что карты определяются только четырьмя свойствами. Таким образом, они решили повеселиться с обобщенной версией игры.
В их распоряжении колода из $n$ разных карт. Каждая карта представлена последовательностью $k$ символов, каждый из которых является одним из $1$, $2$ или $3$. Порядок карт в колоде не имеет значения.
Неупорядоченная тройка карт называется набором, если для каждой из $k$ позиций три символа, соответствующие трем картам, либо одинаковы, либо попарно различны. Например, три карты, представленные $1123$, $1322$ и $1221$, составляют набор, поскольку все символы в первой и третьей позициях одинаковы ($1$ и $2$ соответственно), а символы во второй и четвертой позициях различны ($1$, $2$ и $3$ в некотором порядке).
Глядя на эти $n$ карты на столе, они начали задаваться вопросом: сколько неупорядоченных троек этих $n$ карт составляют набор. Напишите программу, которая ответит на их вопрос.
Входные данные
Первая строка содержит целые числа $n$ и $k$ ($1 ≤ k ≤ 12$, $1 ≤ n ≤ 3^k$) - количество карт в колоде и количество свойств одной карты соответственно.
Каждая из следующих $n$ строк содержит последовательность из $k$ символов, представляющих карту. Каждый символ является одним из $1$, $2$ или $3$. Разные строки содержат разные последовательности символов.
Выходные данные
Выведите количество неупорядоченных троек, образующих множество.
3 4 1123 1322 1221
1
2 2 11 22
0
5 3 111 222 333 123 132
2