Number of Strings Matching Exactly K Patterns

A string pattern consists only of lowercase English letters and question marks (?). A lowercase English string matches a pattern if they have the same length and every non-question-mark character in the pattern is equal to the character at the same position in the string. A question mark matches any lowercase English letter.

Given N patterns, count how many lowercase English strings match exactly K of the given patterns.

The first line contains the number of patterns N and an integer K. N is a positive integer at most 15, and K is a positive integer at most N.

Each of the next N lines contains one pattern. All patterns have the same length, and the length is at most 50. Each pattern consists only of lowercase English letters and question marks (?).

Print the number of strings that match exactly K of the given patterns, modulo 1,000,003.