### Problem Statement

You are given a String[] patterns, each element of which is a single pattern. Each pattern contains only lowercase letters and question marks ('?'). A string matches a pattern if it has the same length as the pattern, and at each position, either the corresponding characters are equal or the character in the pattern is a question mark. For example, "abc" matches "a?c", but not "a?b" or "abc?". Return the number of strings consisting of only lowercase letters that match exactly k of the given patterns, modulo 1,000,003.

### Definition

 Class: SetOfPatterns Method: howMany Parameters: String[], int Returns: int Method signature: int howMany(String[] patterns, int k) (be sure your method is public)

### Constraints

-patterns will contain between 1 and 15 elements, inclusive.
-k will be between 1 and the number of elements in patterns, inclusive.
-Each element of patterns will contain between 1 and 50 characters, inclusive.
-Each element of patterns will have the same length.
-Each element of patterns will contain only lowercase letters ('a' - 'z') and question marks ('?').

### Examples

0)

 `{"?"}` `1`
`Returns: 26`
 Every lowercase letter matches this pattern.
1)

 `{"a","b","c"}` `1`
`Returns: 3`
 "a" or "b" or "c".
2)

 `{"a?","?b"}` `2`
`Returns: 1`
 The only possible solution is "ab".
3)

 `{"?????"}` `1`
`Returns: 881343`
 26^5 mod 1000003 = 881343.

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8307

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11124&pm=8307

srbga

#### Testers:

PabloGilberto , Olexiy , Andrew_Lazarev , ivan_metelsky

#### Problem categories:

Advanced Math, Dynamic Programming, String Manipulation