#1985. Let's Get a Perfect Score

Let's Get a Perfect Score

[ABC282B] Let's Get a Perfect Score

题面翻译

题意简述

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

一个队伍有且仅有 22 人。

题目描述

1 1 から N N までの番号がついた N N 人の参加者が、1 1 から M M までの番号がついた M M 問からなるコンテストに参加します。

1 1 以上 N N 以下の整数 i i 1 1 以上 M M 以下の整数 j j について、Si S_i j j 番目の文字が o のとき参加者 i i は問題 j j を解くことが可能で、Si S_i j j 番目の文字が x のとき参加者 i i は問題 j j を解くことが不可能です。

このコンテストは、二人の参加者でペアを組んで参加します。二人が協力することで M M 問全てを解くことが可能であるようなペアの個数を答えてください。

より厳密には、1 x < y N 1\leq\ x\ <\ y\leq\ N を満たす整数の組 (x,y) (x,y) であって、 1 1 以上 M M 以下の任意の整数 j j について、参加者 x x か参加者 y y の少なくとも一方は問題 j j を解くことが可能であるという条件を満たすものの個数を答えてください。

输入格式

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

N N M M S1 S_1 S2 S_2 \vdots SN S_N

输出格式

答えを出力せよ。

样例 #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 N 2 2 以上30 30 以下的整数 ,特别的还有30%的n=10000
  • M M 1以上 1以上 30以下的整数
  • si s_i 是由ox组成的长度为M M 的字符串

Sample Explanation 1

参加者 1 1 2 2 のペア、参加者 1 1 3 3 のペア、参加者 1 1 4 4 のペア、参加者 1 1 5 5 のペア、参加者 2 2 3 3 のペアの 5 5 個のペアが条件を満たします。 例えば参加者 2 2 4 4 のペアは、問題 4 4 が解けないので条件を満たしません。