| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 512 MB | 33 | 17 | 13 | 56.522% |
A string of characters consisting of lowercase letters of the English alphabet and question marks is called a parameterized word (e.g., a??cd, bcd, ??). Two parameterized words are considered similar if the question mark symbols in both words can be replaced by arbitrary lowercase letters of the english alphabet so that the resulting strings are the same. For example, parameterized words a??? and ?b?a are similar because by replacing the question marks in both words it is possible to obtain the word abba.
Mirko has recently bought a collection of parametrized words. Among the N words found in the collection, Mirko is interested in how many pairs of similar parameterized words exist. All the words in the collection have the same number of characters, M, and it is possible that a word occurs multiple times in the collection.
The first line contains the integer numbers N (1 ≤ N ≤ 50 000) and M (1 ≤ M ≤ 6).
Each of the following N lines contains one parameterized word from the collection with exactly M characters.
Print the total number of similar pairs of parameterized words.
3 3 ??b c?? c?c
2
Pairs of similar words are: (??b, c??) and (c??, c?c).
4 6 ab??c? ??kll? a?k??c ?bcd??
3
5 2 ?? b? c? ?g cg
8