Parametriziran

시간 제한3초메모리 제한512 MB

요약

길이가 같은 소문자와 물음표 단어들 중에서 물음표를 적당한 소문자로 채워 서로 같게 만들 수 있는 쌍의 개수를 센다.

난이도: 보통10점 중 6점
유형: 비트 연산, 해시맵, 문자열, 완전 탐색
정답자: 아직 제출이 없습니다

문제

영어 소문자와 물음표로 이루어진 문자열을 파라미터화 단어라고 부른다. 예를 들어 a??cd, bcd, ?? 등이 있다. 두 파라미터화 단어가 유사하다는 것은, 두 단어의 물음표를 각각 임의의 영어 소문자로 바꾸어 두 결과 문자열이 같아지도록 만들 수 있다는 뜻이다. 예를 들어 파라미터화 단어 a???와 ?b?a는 유사한데, 두 단어의 물음표를 적절히 바꾸면 abba를 얻을 수 있기 때문이다.

Mirko는 최근에 파라미터화 단어 모음을 하나 샀다. 모음에 들어 있는 N개의 단어 중에서 Mirko는 유사한 파라미터화 단어 쌍이 몇 개인지 궁금해한다. 모음에 있는 모든 단어의 길이는 M으로 같으며, 같은 단어가 모음에 여러 번 나타날 수도 있다.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 50 000)과 M (1 ≤ M ≤ 6)이 주어진다.

다음 N개의 줄에는 모음에 있는 파라미터화 단어가 한 줄에 하나씩 주어지며, 각 단어의 길이는 정확히 M이다.

출력

유사한 파라미터화 단어 쌍의 총 개수를 출력한다.

예제3

예제 1
입력
```
3 3
??b
c??
c?c
```
예상 출력
```
2
```
예제 2
입력
```
4 6
ab??c?
??kll?
a?k??c
?bcd??
```
예상 출력
```
3
```
예제 3
입력
```
5 2
??
b?
c?
?g
cg
```
예상 출력
```
8
```