[AdditionalFile3547.zip](file://AdditionalFile3547.zip?type=additional_file)

#3547. 「COCI 2021.10」Set

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2021/2022 Contest #1 T4「Set」

定义一个有序多元组 $a$ 的第 $i$ 项为 $a_i$。

给定一个 $n$ 个有序 $m$ 元组 $b$，要从这些 $m$ 元组中选出 $3$ 个，设这三个 $m$ 元组的下标为 $i,j,k$，他们要满足如下条件：

• $i<j<k$；
• $\forall 1\le z\le m,b_{i,z}=b_{j,z}=b_{k,z}$ 或者 $b_{i,z}\not=b_{j,z},b_{i,z}\not=b_{k,z},b_{j,z}\not=b_{k,z}$。

请问有多少种选法可以选出这个三元组。

输入格式

第一行为两个整数 $n,m$。

接下来 $n$ 行 $m$ 个字符，第 $i$ 行第 $j$ 个字符表示 $b_{i,j}$ 的值。

输出格式

仅一行一个整数，表示选择方法的种数。

样例 1

输入

3 4
1123
1322
1221

输出

1

样例 2

输入

2 2
11
22

输出

0

样例 3

输入

5 3
111
222
333
123
132

输出

2

两个三元组分别是 $\{1,2,3\}$ 和 $\{1,4,5\}$。

数据范围与提示

对于全部数据，$1\le m\le 12$，$1\le n\le 3^m$，$b_i$ 互不相同，$1\le b_{i,j}\le 3$。