题目描述

译自 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} \ne b_{j,z},\ b_{i,z} \ne b_{k,z},\ b_{j,z} \ne b_{k,z}$（即三个值两两不同）。

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

输入格式

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

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

输出格式

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

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$