让我们拿满分

题目描述

编号为 $1$ 到 $N$ 的 $N$ 名参赛者将参加一场包含 $M$ 道题(编号为 $1$ 到 $M$)的比赛。

对于介于 $1$ 和 $N$ 之间的整数 $i$ 以及介于 $1$ 和 $M$ 之间的整数 $j$,若 $S_i$ 的第 $j$ 个字符是 o,则参赛者 $i$ 能解出第 $j$ 题;若该字符是 x,则不能解出。

参赛者必须两人一组组队。求能组队使得两人合计可以解出全部 $M$ 道题的方案数。

更形式化地说,求满足 $1 \le x \lt y \le N$,且对于任意介于 $1$ 和 $M$ 之间的整数 $j$,参赛者 $x$ 和参赛者 $y$ 中至少有一人能解出第 $j$ 题的整数对 $(x,y)$ 的个数。

输入格式

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

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

输出格式

输出答案。

样例

5 5
ooooo
oooxx
xxooo
oxoxo
xxxxx

5

满足条件的组队有以下 5 组:参赛者 1 和 2、参赛者 1 和 3、参赛者 1 和 4、参赛者 1 和 5、参赛者 2 和 3。

另一方面,例如参赛者 2 和 4 的组队不满足条件,因为他们无法解出第 4 题。

3 2
ox
xo
xx

1

2 4
xxxx
oxox

0

数据范围

• $N$ 是介于 $2$ 和 $30$(含两端)之间的整数。
• $M$ 是介于 $1$ 和 $30$(含两端)之间的整数。
• $S_i$ 是由 o 和 x 组成的长度为 $M$ 的字符串。