#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PII pair<int, int>

#define PLI pair<LL, int>

#define ull unsigned long long

using namespace std;

const int N = ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = ;

int n, k, m, Pow[N], num[ << ], C[N][N];

char s[][];

char t[];

void init() {

    Pow[] = ;

    for(int i = ; i < N; i++) Pow[i] = Pow[i-] *  % mod;

    for(int i = ; i < N; i++) {

        for(int j = ; j <= i; j++) {

            if(!j || i == j) C[i][j] = ;

            else C[i][j] = (C[i-][j] + C[i-][j-]) % mod;

        }

    }

}

int cal(int state) {

    memset(t, '#', sizeof(t));

    for(int j = ; j < n; j++) {

        if((state>>j)&) {

            for(int i = ; i < m; i++) {

                if(s[j][i] != '?') {

                    if(t[i] == '#') t[i] = s[j][i];

                    else if(t[i] != s[j][i]) return ;

                }

            }

        }

    }

    int cnt = ;

    for(int i = ; i < m; i++)

        if(t[i] == '#') cnt++;

    return Pow[cnt];

}

int solve(int k) {

    if(k == -) return ;

    int ans = ;

    for(int s = ; s < (<<n); s++) {

        if(s) num[s] = num[s-(s&-s)] + ;

        if(num[s] > k) {

            int val = cal(s);

            if((num[s] - k)&) ans = (ans + 1ll*C[num[s]-][k]*val) % mod;

            else ans = (ans - 1ll*C[num[s]-][k]*val) % mod;

        }

    }

    return (Pow[m] - ans + mod) % mod;

}

int main() {

    init();

    int T; scanf("%d", &T);

    while(T--) {

        scanf("%d%d", &n, &k);

        for(int i = ; i < n; i++)

            scanf("%s", s[i]);

        m = strlen(s[]);

        printf("%d\n", (solve(k) - solve(k-) + mod) % mod);

    }

    return ;

}

/*

*/