와일드카드 패턴

Time Limit: 4000 msMemory Limit: 512 MBGold V5Author: Super Admin포함-배제와일드카드 매칭조합론

영어 소문자와 물음표(?)로 이루어진 패턴이 N개 주어진다. 물음표는 어떤 소문자든지 일치하는 것으로 간주한다.

예를 들어 패턴 "a?c"는 "abc", "acc", "azc" 등과 일치한다.

주어진 패턴 중 정확히 K개의 패턴과 일치하는 문자열의 개수를 1,000,003으로 나눈 나머지를 구하시오.

입력

첫째 줄에 패턴의 개수 N과 K가 공백으로 구분되어 주어진다. (1 <= K <= N <= 15)

둘째 줄부터 N개의 줄에 걸쳐 각 패턴이 주어진다. 패턴의 길이는 1 이상 50 이하이며, 모든 패턴의 길이는 같다. 패턴은 알파벳 소문자와 물음표로만 이루어져 있다.

출력

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

Problem Statistics

17

Total submissions

13

Accepted

76.5%

Acceptance rate

1

Unique solvers

입력 1

2 1
ab
cd

출력 1

입력 2

2 2
a?
?b

출력 2

제한 수열

Gold V4.5