/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
1 から N までの番号がついた N 人の参加者が、1 から M までの番号がついた M 問からなるコンテストに参加します。
1 以上 N 以下の整数 i 、1 以上 M 以下の整数 j について、S_i の j 番目の文字が o のとき参加者 i は問題 j を解くことが可能で、S_i の j 番目の文字が x のとき参加者 i は問題 j を解くことが不可能です。
このコンテストは、二人の参加者でペアを組んで参加します。二人が協力することで M 問全てを解くことが可能であるようなペアの個数を答えてください。
より厳密には、1\leq x < y\leq N を満たす整数の組 (x,y) であって、 1 以上 M 以下の任意の整数 j について、参加者 x か参加者 y の少なくとも一方は問題 j を解くことが可能であるという条件を満たすものの個数を答えてください。
制約
- N は 2 以上 30 以下の整数
- M は 1 以上 30 以下の整数
- S_i は
o,xからなる長さ M の文字列
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 S_2 \vdots S_N
出力
答えを出力せよ。
入力例 1
5 5 ooooo oooxx xxooo oxoxo xxxxx
出力例 1
5
参加者 1 と 2 のペア、参加者 1 と 3 のペア、参加者 1 と 4 のペア、参加者 1 と 5 のペア、参加者 2 と 3 のペアの 5 個のペアが条件を満たします。
例えば参加者 2 と 4 のペアは、問題 4 が解けないので条件を満たしません。
入力例 2
3 2 ox xo xx
出力例 2
1
入力例 3
2 4 xxxx oxox
出力例 3
0
Score : 200 points
Problem Statement
N participants, numbered 1 to N, will participate in a contest with M problems, numbered 1 to M.
For an integer i between 1 and N and an integer j between 1 and M, participant i can solve problem j if the j-th character of S_i is o, and cannot solve it if that character is x.
The participants must be in pairs. Print the number of ways to form a pair of participants who can collectively solve all the M problems.
More formally, print the number of pairs (x,y) of integers satisfying 1\leq x < y\leq N such that for any integer j between 1 and M, at least one of participant x and participant y can solve problem j.
Constraints
- N is an integer between 2 and 30, inclusive.
- M is an integer between 1 and 30, inclusive.
- S_i is a string of length M consisting of
oandx.
Input
The input is given from Standard Input in the following format:
N M S_1 S_2 \vdots S_N
Output
Print the answer.
Sample Input 1
5 5 ooooo oooxx xxooo oxoxo xxxxx
Sample Output 1
5
The following five pairs satisfy the condition: participants 1 and 2, participants 1 and 3, participants 1 and 4, participants 1 and 5, and participants 2 and 3.
On the other hand, the pair of participants 2 and 4, for instance, does not satisfy the condition because they cannot solve problem 4.
Sample Input 2
3 2 ox xo xx
Sample Output 2
1
Sample Input 3
2 4 xxxx oxox
Sample Output 3
0