Sheng_bill not only has amazing mental arithmetic skills but can also easily perform various statistics. In yesterday's competition, you tied with him thanks to your excellent program, which left Sheng_bill extremely dissatisfied, so he challenged you again. This time, you cannot lose!

The rules of the competition are as follows:

Given $N$ strings of the same length (consisting of lowercase English letters and ?), find the number of strings $T$ that match exactly $K$ of these $N$ strings (the answer should be modulo $1\,000\,003$).

A string $S_x$ ($1 \leq x \leq N$) matches $T$ if the following conditions are met:

1. $|S_x| = |T|$
2. For any $1 \leq i \leq |S_x|$, either $S_x[i] = \,?$ or $S_x[i] = T[i]$.

Here, $T$ consists only of lowercase English letters.

Input

This problem contains multiple test cases.

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

For each test case:

• The first line contains two integers, $N$ and $K$ (as described in the problem).
• The next $N$ lines each contain a string.

Output

Output one integer per line, representing the answer modulo $1\,000\,003$.

Examples

Input 1

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

Output 1

914852
0
0
871234
67018

Subtasks

For $30\%$ of the data, $N \leq 5$.

For $50\%$ of the data, $N \leq 10$.

For $70\%$ of the data, $N \leq 13$.

For $100\%$ of the data, $T \leq 5$, $K \leq N \leq 15$, and the string length $L \leq 50$.