Given an integer $m$, define the alphabet $\Sigma$ as the first $m$ lowercase letters. For two strings $A, B$ over $\Sigma$, define $f(A,B)$ as the answer to the following question:

Does there exist a finite automaton $M$ such that, for any string $S$ over $\Sigma$ of any length, the automaton can compare the number of occurrences of $A$ and $B$ in $S$ (returning one of <, =, >)? If such an automaton exists, then $f(A,B)=1$; otherwise $f(A,B)=0$.

You are given $n$ strings $s_1,\dots,s_n$. You need to compute: $\sum\limits_{1\le i< j\le n} f(s_i,s_j)$.

In this problem, an automaton $M$ is defined as a 5-tuple $(Q,\Sigma,\delta,q_0,F)$, where:

• $Q$ is the set of states,
• $\Sigma$ is the alphabet,
• $\delta: Q\times \Sigma\rightarrow Q$ is the transition function,
• $q_0$ is the start state,
• $F:Q\rightarrow\{<,=,>\}$ assigns an output to each state.

We say this automaton can compare the occurrence counts of $A$ and $B$ in $S$ if and only if $F(\delta(\dots\delta(\delta(q_0,S_1),S_2)\dots,S_{|S|}))\in {<,=,>}$ equals the true comparison result between the number of occurrences of $A$ and of $B$ in $S$.

Input Format

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

The next $n$ lines each contain a string $s_i$, consisting of the first $m$ lowercase letters.

Output Format

Output one integer on a single line: the answer.

Example

Example Input 1

3 26
ct
ctt
cts

Example Output 1

2

Example 2–7

See the attached files ex_dfa2.in/out through ex_dfa7.in/out. The $(i+1)$-th example satisfies the constraints of Subtask $i$.

Constraints

For all test cases: $2\le n\le 10^6$, $N=\sum\limits_{i=1}^n|s_i|\le 10^6$, $2\le m\le 26$.

This problem enables reasonable subtask dependencies.