Page not loading? Try clicking here.
Placeholder

#6335

만들 수 있는 단어 개수 1s 1024MB

Problems

A부터 시작하는 m개의 영대문자 알파벳을 최대 하나까지만 사용하여 어떤 단어를 만드는 것이 가능한지 알아보려고 한다.

예를 들어 m=3이라면 사용 가능한 알파벳은 A, B, C 뿐이고, 이 때 만들 수 있는 단어는 "BA", "CBA", "A" 등이 있고, 만들 수 없는 단어로는 "E", "AA", "ABD" 등이 있다.

주어진 n개의 단어들 중 만들 수 있는 단어의 개수가 몇 개인지 알아보자.


Input

첫 줄에 두 정수 n과 m이 주어진다. (1 \le n \le 100, 1 \le m \le 15)

두 번째 줄부터 n줄에 걸쳐 길이 1 이상, 15 이하의 영대문자로만 이루어진 단어가 한 줄에 하나씩 주어진다.


Output

주어진 n개의 단어들 중 만들 수 있는 단어의 개수가 몇 개인지 출력한다.


Example #1

6 12
CAD
ADD
ALE
DALE
PAT
ICPC
3

Example #2

4 15
KEK
LMAO
LEL
LOL
1

Source

2019 ICPC South Pacific Regionals D번
You must sign in to write code.