群星的尽头

题目大意

给定整数 $m$，定义字符集 $\Sigma$ 为前 $m$ 个小写字母，对于两个字符集为 $\Sigma$ 的串 $A,B$，定义 $f(A,B)$ 为如下问题的答案：存在一个有限大小的自动机 $M$，使得输入字符集为 $\Sigma$ 的，任意长度的字符串 $S$，都可以比较 $A$ 与 $B$ 在 $S$ 中的出现次数（返回 <，=，>）。如果存在，则 $f(A,B)=1$，否则 $f(A,B)=0$。给定 $n$ 个串 $s_1\sim s_n$，你要求出 $\sum\limits_{1\le i< j\le n}f(s_i,s_j)$

在本题中，我们定义自动机 $M$ 是一个五元组 $(Q,\Sigma,\delta,q_0,F)$，其中 $Q$ 是状态集合，$\Sigma$ 是字符集，$\delta: Q\times \Sigma\rightarrow Q$ 是转移函数，$q_0$ 是起始状态，$F:Q\rightarrow\{<,=,>\}$ 表示每个状态对应的结果。定义这个自动机可以比较 $A$ 和 $B$ 在 $S$ 中的出现次数，当且仅当 $F(\delta(\dots\delta(\delta(q_0,S_1),S_2)\dots,S_{|S|}))\in \{<,=,>\}$ 为 $A$ 和 $B$ 在 $S$ 中出现次数的大小关系。

输入格式

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

接下来 $n$ 行，第 $i$ 行一个字符串 $s_i$，字符集为前 $m$ 个小写字母

输出格式

输出一行一个整数，表示答案。

样例输入 1

3 26
ct
ctt
cts

样例输出 1

2

样例 2~7

见附加文件中的 ex_dfa2.in/out 到 ex_dfa7.in/out，第 $i+1$ 个样例满足子任务 $i$ 的限制。

数据范围

对于所有测试点，$2\le n\le 10^6$，$N=\sum\limits_{i=1}^n|s_i|\le 10^6$，$2\le m\le 26$。

本题开启合理的子任务依赖