奇妙的相似

题目描述

有 $N$ 个长度为 $M$ 的序列,记为 $A_1, A_2, \ldots, A_N$。第 $i$ 个序列由 $M$ 个整数 $A_{i,1}, A_{i,2}, \ldots, A_{i,M}$ 表示。

对于两个长度为 $M$ 的序列 $X$ 和 $Y$,当且仅当满足 $X_i = Y_i$ 的下标 $i$ $(1 \le i \le M)$ 的个数为奇数时,称它们「相似」。

求满足 $1 \le i \lt j \le N$ 且 $A_i$ 与 $A_j$ 相似的整数对 $(i, j)$ 的个数。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$
$A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,M}$
$A_{2,1}$ $A_{2,2}$ $\ldots$ $A_{2,M}$
$\vdots$
$A_{N,1}$ $A_{N,2}$ $\ldots$ $A_{N,M}$

输出格式

以整数形式输出答案。

样例

3 3
1 2 3
1 3 4
2 3 4

1

整数对 $(i,j) = (1,2)$ 满足条件,因为满足 $A_{1,k} = A_{2,k}$ 的下标 $k$ 只有 $k=1$,共 $1$ 个,为奇数。

整数对 $(i,j) = (1,3), (2,3)$ 不满足条件,因此满足条件的只有 $(1,2)$。

6 5
8 27 27 10 24
27 8 2 4 5
15 27 26 17 24
27 27 27 27 27
27 7 22 11 27
19 27 27 27 27

5

数据范围

• $1 \le N \le 2000$
• $1 \le M \le 2000$
• $1 \le A_{i,j} \le 999$
• 输入均为整数。