题目描述

有 $N$ 名选手，编号为 $1 \sim N$，一起参加了有 $M$ 道题目的比赛，题目编号 $1 \sim M$。$S_{ij}$ 为 o 或 x 分别表示选手 i 能否解出题目 j。请你求出有多少种组成一个队伍的方式，使得这个队伍能共同解出 $M$ 道题。共同解出指，一道题目至少被队伍中的一个选手解出。

一个队伍有且仅有 $2$ 人。

输入格式

第一行两个整数 $N$ $M$

接下来是一个N行M列的字符矩阵

输出格式

有多少种组成一个队伍的方式，使得这个队伍能共同解出 $M$ 道题。

样例 #1

样例输入 #1

5 5
ooooo
oooxx
xxooo
oxoxo
xxxxx

样例输出 #1

5

样例 #2

样例输入 #2

3 2
ox
xo
xx

样例输出 #2

1

样例 #3

样例输入 #3

2 4
xxxx
oxox

样例输出 #3

0

数据范围与提示

• $N$是$2$以上$30$以下的整数 ,特别的还有30%的n=10000
• $M$是$1以上$ 30以下的整数
• $s_i$是由o， x组成的长度为$M$的字符串

输入样例1解释

1、2

1、3

1、4

1、5

2、3

这些人组队可以成功。