配点 : $300$ 点

問題文

$0$ か $1$ で答える問題 $M$ 問からなるテストがあり、これに $N$ 人の生徒が取り組みました。 $N$ 個の長さ $M$ の文字列 $S_1,S_2,\ldots,S_N$ が与えられます。 $S_i$ の $k$ 文字目は 0 と 1 のいずれかであり、 $i$ 番目の生徒の $k$ 問目に対する解答を示しています。各生徒の各問題に対する解答は判明していますが、各問題の正解が $0$ と $1$ のどちらであるかはまだ判明していません。 $1 \leq i < j \leq N$ を満たす組 $(i,j)$ であって、生徒 $i$ と生徒 $j$ の正解した問題の数が等しい可能性がないようなものはいくつあるか求めてください。

制約

• $2 \leq N \leq 10^5$
• $1 \leq M \leq 20$
• $S_i$ は 0 と 1 からなる長さ $M$ の文字列

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$S_1$

$S_2$

$:$

$S_N$

出力

答えを出力せよ。

3 2
00
01
10

2

例えば $1$ 問目の正解と $2$ 問目の正解が共に $0$ のとき、生徒 $2$ と生徒 $3$ の正解数は共に $1$ となり等しくなります。一方、生徒 $1$ と生徒 $2$ のペア、生徒 $1$ と生徒 $3$ のペアでは、二人の正解数が等しいことはありません。

7 5
10101
00001
00110
11110
00100
11111
10000

10