P2167 [SDOI2009] Bill's Challenge

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.

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$.

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

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