Background

In the well-known game SET, there are cards with different numbers, shapes, colors, and so on. The player’s goal is to find an existing triplet of cards (a triple of cards, i.e., a combination of three cards) that satisfies certain rules. Marin and Josip quickly got bored with this game and made it harder.

Problem Description

In this problem, each card is defined as a length $k$ sequence consisting only of $1, 2, 3$. There are $n$ cards. The cards are unordered, and it is guaranteed that the cards are pairwise different.

We define a SET as an unordered triplet of cards such that, for every position, the three sequences are either all the same or all different. Using the original wording, this is “same” or “pairwise different”. More rigorously, let the three sequences be $S_i, S_j, S_k$. Then the following conditions must hold:

• $i \lt j \lt k$.
• $\forall x \in \left[1, k\right]$, we have $S_i(x) = S_j(x) = S_k(x)$ or $S_i(x) \neq S_j(x) \neq S_k(x)$.

For example, $(1123, 1322, 1221)$ satisfies the rule: positions $1, 3$ are the same, and positions $2, 4$ are all different.

Given these sequences, find how many essentially different SETs can be formed.

Input Format

The first line contains two positive integers $n, k$.

The next $n$ lines each contain a length $k$ sequence consisting only of $1, 2, 3$, representing a card.

It is guaranteed that the sequences on the cards are all different.

Output Format

Output one integer in a single line, representing the number of essentially different SETs that can be formed.

3 4
1123
1322
1221

1

2 2
11
22

0

5 3
111
222
333
123
132

2

Hint

[Sample Explanation #3]

The two SETs that can be formed are $(S_1, S_2, S_3)$ and $(S_1, S_4, S_5)$.

[Constraints]

For all testdata, $1\le k\le 12$, $1\le n\le 3^k$, all $S_i$ are different, and $1\le S_i(x) \le 3$.

Notes

The total score for this problem is $110$ points.

This problem is translated from Croatian Open Competition in Informatics 2021/2022 Contest #1 T4 Set。

Translated by ChatGPT 5