정확히 K개의 패턴과 일치하는 문자열의 개수

문자열 패턴은 영어 소문자와 물음표(?)로만 이루어진 문자열이다. 어떤 영어 소문자 문자열이 패턴과 일치하려면 두 길이가 같아야 하며, 패턴에서 물음표가 아닌 위치의 문자는 문자열의 같은 위치 문자와 같아야 한다. 물음표는 어떤 영어 소문자와도 일치한다.

N개의 패턴이 주어진다. 영어 소문자로만 이루어진 문자열 중에서, 주어진 패턴 중 정확히 K개와 일치하는 문자열의 개수를 구하시오.

첫째 줄에 패턴의 개수 N과 정수 K가 주어진다. N은 15 이하의 자연수이고, K는 N 이하의 자연수이다.

둘째 줄부터 N개의 줄에 패턴이 하나씩 주어진다. 모든 패턴의 길이는 같고, 길이는 최대 50이다. 각 패턴은 영어 소문자와 물음표(?)로만 이루어져 있다.

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