Problem Background

In the famous game SET, there are cards with different numbers, shapes, colors, etc. The objective for players is to identify a triplet of cards that meets specific requirements. Marin and Josip quickly grew bored of this game and enhanced it.

Problem Description

In this problem, each card represents a sequence of length \( k \) composed solely of the digits \( 1, 2, 3 \). There are \( n \) such cards, and they are unordered.

A SET is defined as an unordered triplet of cards where each position in the three sequences is either the same or completely different. More formally, let the three sequences be \( S_i, S_j, S_k \), then the following conditions must be met:

• \( i < j < k \)
• \( \forall x \in \left[1, k\right] \), \( 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 that positions \( 1, 3 \) are the same and positions \( 2, 4 \) are different.

Given these sequences, determine how many distinct SETs can be formed.

Input Format

The first line contains two positive integers \( n \) and \( k \).

The next \( n \) lines each contain a sequence of length \( k \) composed of the digits \( 1, 2, 3 \), representing a card.

It is guaranteed that no two cards have the same sequence.

Output Format

Output a single integer representing the number of distinct SETs that can be formed.

Sample Input and Output

Sample Input #1

3 4
1123
1322
1221

Sample Output #1

1

Sample Input #2

2 2
11
22

Sample Output #2

0

Sample Input #3

5 3
111
222
333
123
132

Sample Output #3

2

Notes

[Sample Explanation #3]

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

[Data Range]

For all data, \( 1 \le k \le 12 \), \( 1 \le n \le 3^k \), \( S_i \) are distinct, and \( 1 \le S_i(x) \le 3 \).

This problem is worth a total of 110 points.

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

见题面 Input 部分

见题面 Output 部分