시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB3981318534.694%

문제

문자열 패턴이란 영어 소문자와 물음표 (?) 만으로 이루어져 있다. 어떤 문자열이 어떤 문자열 패턴과 맞을 조건은 일단 문자열과 문자열 패턴의 길이가 같고, 물음표가 아닌 문자가 서로 일치해야 한다. 물음표일 때는, 그냥 아무 문자가 와도 같은 문자로 친다.

예를 들어, "abc"의 패턴은 "a?c"가 될 수 있다. "a?b" 또는, "abc?"는 패턴이라고 할 수 없다.

패턴이 여러개 주어졌을 때, 그 중 정확하게 K개의 패턴만이 일치하는 문자열의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 패턴의 개수 N과 K가 주어진다. N은 15보다 작거나 같은 자연수이고, K는 N보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 패턴이 주어진다. 패턴의 길이는 최대 50이고, 모든 패턴의 길이는 모두 같다. 패턴은 알파벳 소문자와 물음표(?)로만 이루어져 있다.

출력

주어지는 패턴과 정확하게 K개 일치하는 문자열의 개수를 1,000,003로 나눈 나머지를 출력한다.

예제 입력 1

1 1
?

예제 출력 1

26

예제 입력 2

3 1
a
b
c

예제 출력 2

3

예제 입력 3

2 2
a?
?b

예제 출력 3

1

예제 입력 4

1 1
?????

예제 출력 4

881343

출처