[AdditionalFile3133.zip](file://AdditionalFile3133.zip?type=additional_file)

#3133. 「COCI 2019.2」Parametriziran

标签: 传统 | 时间限制: 3000 ms | 内存限制: 64 MiB |

题目描述

译自 COCI 2018/2019 Contest #5 T4「Parametriziran」

给你 $N$ 个长为 $M$ 的字符串，每个字符串仅由小写字母和 ? 组成，问有多少对字符串满足存在一种将问号填为小写字母的方案，使得两个字符串相同。

输入格式

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

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

输出格式

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

样例 1

输入

3 3
??b
c??
c?c

输出

2

可以配对的是 $(1,2), (2,3)$ 两组。

样例 2

输入

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

输出

3

样例 3

输入

5 2
??
b?
c?
?g
cg

输出

8

数据范围与提示

对于 $30\%$ 的数据，保证 $M \le 2$。

对于另外 $30\%$ 的数据，保证 $M \le 4$。

对于 $100\%$ 的数据，保证 $N \le 5\times 10^4, M \le 6$。