题目描述

有 $N$ 名编号为 $1$ 到 $N$ 的参赛者参加一个包含 $M$ 道编号为 $1$ 到 $M$ 的题目的竞赛。

对于 $1 \leq i \leq N$，$1 \leq j \leq M$，如果 $S_i$ 的第 $j$ 个字符为 o，则第 $i$ 位参赛者可以解答第 $j$ 题；如果为 x，则第 $i$ 位参赛者无法解答第 $j$ 题。

本次竞赛以两人一组的形式参加。请你计算有多少对参赛者可以通过合作解答所有 $M$ 道题目。

更严格地说，请你计算满足 $1 \leq x < y \leq N$ 的整数对 $(x, y)$ 的数量，使得对于任意 $1 \leq j \leq M$，参赛者 $x$ 或参赛者 $y$ 至少有一人能够解答第 $j$ 题。

输入格式

输入按以下格式从标准输入读入。

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

输出满足条件的参赛者对的数量。

样例 1

输入

5 5
ooooo
oooxx
xxooo
oxoxo
xxxxx

输出

5

样例 2

输入

3 2
ox
xo
xx

输出

1

样例 3

输入

2 4
xxxx
oxox

输出

0

说明/提示

限制条件

• $N$ 是 $2$ 到 $30$ 之间的整数。
• $M$ 是 $1$ 到 $30$ 之间的整数。
• $S_i$ 是由 o 和 x 组成的长度为 $M$ 的字符串。

样例解释 1

满足条件的有 $5$ 对：参赛者 $1$ 和 $2$，参赛者 $1$ 和 $3$，参赛者 $1$ 和 $4$，参赛者 $1$ 和 $5$，参赛者 $2$ 和 $3$。例如，参赛者 $2$ 和 $4$ 的组合无法解答第 $4$ 题，因此不满足条件。

由 ChatGPT 4.1 翻译