看到蓝题难度评级和抽象题面直接傻了。
然后发现了奇怪的数据范围——？？
数据范围这么小，肯定考虑状压。

设 $f_{i,S}$ 表示匹配前 $i$ 个字符，匹配成功的字符串编号集合是 $S$，方案数是多少。
转移是显然的。

需要枚举前几个字符，编号集合，下一个字符是什么，遍历所有字符串检验是否可行。
记字符串个数 $n$，长度 $m$，则复杂度为 $O(T nm 2^n \times 26)$。

#include <bits/stdc++.h>
using namespace std;
const int N = 20, M = 55, V = (1 << 15) + 15, mod = 1000003;
int T, n, k, len;
char s[N][V];
int dp[M][V];

int popcnt(int S) {
    int cnt = 0;
    while (S) cnt += (S & 1), S >>= 1;
    return cnt;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; i++) scanf(" %s", s[i] + 1);
        len = strlen(s[1] + 1);
        for (int i = 0; i <= len; i++)
            for (int j = 0; j < (1 << n); j++) dp[i][j] = 0;

        dp[0][(1 << n) - 1] = 1;
        for (int i = 0; i < len; i++) {
            for (int S = 0; S < (1 << n); S++) {
                if (!dp[i][S]) continue;
                for (int p = 0; p < 26; p++) {
                    int T = 0;
                    for (int j = 1; j <= n; j++) {
                        if (!(S & (1 << j - 1))) continue;
                        if (s[j][i + 1] == '?' || s[j][i + 1] - 'a' == p) T |= (1 << j - 1);
                    }
                    (dp[i + 1][T] += dp[i][S]) %= mod;
                }
            }
        }
        long long ans = 0;
        for (int i = 0; i < (1 << n); i++) {
            if (popcnt(i) != k) continue;
            ans += dp[len][i];
        }
        printf("%lld\n", ans % mod);
    }
    return 0;
}