Exact K Matches

Sheng_bill is not only amazing at mental calculations but also at various statistics. In yesterday's competition, you tied with him using your excellent program, which infuriated Sheng_bill. Now he challenges you again. This time, you must not lose.

The rules of the competition are as follows:

You are given \(N\) strings \(S_1, S_2, \dots, S_N\) of equal length. Each string consists of lowercase English letters and the character ?. A string \(T\) (which contains only lowercase English letters) is said to match a given string \(S_x\) (for \(1 \le x \le N\)) if:

1. \(|S_x| = |T|\).
2. For every position \(1 \le i \le |S_x|\), either \(S_x[i] = \texttt{?}\) or \(S_x[i] = T[i]\).

Your task is to determine the number of strings \(T\) that match exactly \(K\) of the given \(N\) strings. Since the answer can be very large, output it modulo \(1000003\).

Note: All formulas are rendered in \(\LaTeX\) format.

inputFormat

The first line of input contains two integers \(N\) and \(K\) \( (1 \le N \le 15,\ 0 \le K \le N)\), where \(N\) is the number of strings and \(K\) is the number of strings that must match \(T\).

Each of the following \(N\) lines contains a string \(S_i\) consisting of lowercase English letters and the character ?. All strings have the same length \(L\) \( (1 \le L \le 10^5)\).

outputFormat

Output a single integer: the number of strings \(T\) (which contain only lowercase English letters) that match exactly \(K\) of the given strings, taken modulo \(1000003\).

sample

3 2
a?c
??c
abc

25