와일드카드 패턴

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

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

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

입력

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

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

출력

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

입출력 예시

입력 1

2 1
ab
cd

출력 1

2

입력 2

2 2
a?
?b

출력 2

1