Description

Sheng_bill not only has amazing mental arithmetic, but can also easily handle various statistics. In yesterday's contest, you tied with him thanks to your excellent program, which made Sheng_bill extremely displeased. So he challenges you again. This time, you must not lose.

The rules are as follows:

Given $N$ strings of the same length (composed of lowercase English letters and ?), $S_1, S_2, \dots, S_N$, count the number of strings $T$ that match exactly $K$ of these $N$ strings. Output the answer modulo $1000003$.

A string $S_x$ ($1 \le x \le N$) matches $T$ if the following conditions hold:

1. $|S_x| = |T|$.
2. For any $1 \le i \le |S_x|$, either $S_x[i] = \texttt{?}$ or $S_x[i] = T[i]$.

Here $T$ contains only lowercase English letters.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case, the first line contains two integers, $N$ and $K$.

The next $N$ lines each contain a string $S_i$.

Output Format

For each test case, output a single line with one integer, the answer.

5
3 3
???r???
???????
???????
3 4
???????
?????a?
???????
3 3
???????
?a??j??
????aa?
3 2
a??????
???????
???????
3 2
???????
???a???
????a??

914852
0
0
871234
67018

Hint

Constraints and Conventions:

• For $30\%$ of the testdata, $N \le 5$, $|S_i| \le 20$.
• For $70\%$ of the testdata, $N \le 13$, $|S_i| \le 30$.
• For $100\%$ of the testdata, $1 \le T \le 5$, $1 \le N \le 15$, $1 \le |S_i| \le 50$.

Translated by ChatGPT 5