Number of Strings Matching Exactly K Patterns

Time limit2sMemory limit128 MB

Summary

Count lowercase strings that match exactly K out of N given letter/question-mark patterns of equal length, modulo 1,000,003.

Level: Medium7 of 10
Topics: Combinatorics, Bit manipulation, String, Math
Solved: No attempts yet

Problem

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.

Input

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 (?).

Output

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

Examples4

Example 1
Input
```
1 1
?
```
Expected output
```
26
```
Example 2
Input
```
3 1
a
b
c
```
Expected output
```
3
```
Example 3
Input
```
2 2
a?
?b
```
Expected output
```
1
```
Example 4
Input
```
1 1
?????
```
Expected output
```
881343
```