Problem Description

We define a string containing lowercase letters and question marks as a parameterized word. For example, a??cd, bcd, and ?? are all parameterized words.

Two parameterized words are considered similar if specific lowercase letters can replace the question marks in both words to make them identical. For instance, both a??? and ?b?a can be replaced to form abba, thus a??? and ?b?a are similar.

Given \( N \) parameterized words each of length \( M \), find the number of pairs of similar parameterized words.

Input Format

The first line contains two integers \( N \) and \( M \).

The following \( N \) lines each contain a parameterized word of length \( M \).

Output Format

Output the number of pairs of similar parameterized words.

Sample Input and Output

Sample Input #1

3 3
??b
c??
c?c

Sample Output #1

2

Sample Input #2

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

Sample Output #2

3

Sample Input #3

5 2
??
b?
c?
?g
cg

Sample Output #3

8

Notes/Hints

Sample 1 Explanation

??b and c?? are similar, and c?? and c?c are also similar. Thus, there are 2 pairs of similar parameterized words.

Data Size and Constraints

For 30% of the data, \( M \le 2 \).

For another 30% of the data, \( M \le 4 \).

For 100% of the data, \( 1 \le N \le 5 \times 10^4 \), \( 1 \le M \le 6 \).

Note

This problem's score is set according to the original COCI contest, with a maximum score of 110.

The problem is translated from COCI2018-2019 CONTEST #5 T4 Parametriziran.

见题面 Input 部分

见题面 Output 部分