Parametriziran

Time limit3sMemory limit512 MB

Summary

Count pairs of equal-length words over lowercase letters and question marks that can be made identical by filling the question marks.

Level: Medium6 of 10
Topics: Bit manipulation, Hash map, String, Brute force
Solved: No attempts yet

Problem

A string of characters consisting of lowercase letters of the English alphabet and question marks is called a parameterized word (for example, 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, the 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 parameterized 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.

Input

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.

Output

Print the total number of similar pairs of parameterized words.

Examples3

Example 1
Input
```
3 3
??b
c??
c?c
```
Expected output
```
2
```
Example 2
Input
```
4 6
ab??c?
??kll?
a?k??c
?bcd??
```
Expected output
```
3
```
Example 3
Input
```
5 2
??
b?
c?
?g
cg
```
Expected output
```
8
```