You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

T4 字符串

题目信息

时间限制: 3s

空间限制: 128M

输入文件: parametriziran.in

输出文件: parametriziran.out

题目描述

你是算法工程师。

有一天，mentor交给你一个涉密的任务，需要处理一组数据，解析出其中蕴含的信息。数据的格式是这样的： $N$ 个长为 $M$ 的字符串，每个字符串仅由小写字母和 ? 组成， ? 是通配符，可以替换成任意字符，这可能是信息来源方故意做的手脚。

mentor告诉你，如果替换之后的字符串可以相等，那么就说这两个字符串相似。而且mentor接到的需求是求相似字符串的对数，这对涉密任务的完成至关重要，担子就落在你身上了。

输入格式

第一行输入两个正整数 $N,M$，表示串的数量和长度。

接下来 $N$ 行每行一个长度为 $M$ 的字符串，满足题目描述所给的性质。

输出格式

一行输出一个整数，表示总共的对数。

样例

输入1

3 3
??b
c??
c?c

输出1

2

输入2

4 6
ab??c?
??kll?
a?k??c
?bcd??

输出2

3

输入3

5 2
??
b?
c?
?g
cg

输出3

8

数据范围与提示

• 对于 $30 \%$ 的数据, 满足 $M \le 2$
• 另有 $30\%$ 的数据, 满足 $M \le 4$
• 对于 $100 \%$ 的数据, 满足 $N \le 5 \times 10^4 , M \le 6$