#include<bits/stdc++.h>
#define N 17
#define M 52
#define mod 1000003
#define int long long 
using namespace std;

bool v[1<<N];
char s[1<<N][M];
int t,n,m,len,cnt,now,num,mi[M],c[N][N],ans[N];

inline int read(){
	int x=0,w=0; char ch=0;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return w?-x:x;
}

signed main(){
	mi[0]=1;
	t=read();
	for(int i=1;i<=50;++i){
		mi[i]=mi[i-1]*26;
		mi[i]%=mod;
	}
	for(int i=0;i<=15;++i){
		for(int j=0;j<=i;++j){
			if(!j) c[i][j]=1;
			else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
		}
	}
	while(t--){
		for(int i=0;i<(1<<n);++i) v[i]=0;
		for(int i=0;i<=n;++i) ans[i]=0;
		now=1;
		n=read(),m=read();
		for(int i=0;i<n;++i) cin>>s[1<<i];
		len=strlen(s[1]);
		for(int i=1;i<(1<<n);++i){
			if(i==now){
				now<<=1;
				continue;
			}
			num=0;
			for(int j=0;j<n;++j){
				if(!(i&(1<<j))) continue;
				num++;
				if(num>1) continue;
				if(v[i^(1<<j)]||v[1<<j]){
					v[i]=1;
					break;
				}
				cnt=0; 
				for(int k=0;k<len;++k){
					if(s[i^(1<<j)][k]=='?'&&s[1<<j][k]=='?') cnt++,s[i][k]='?';
					else if(s[i^(1<<j)][k]=='?') s[i][k]=s[1<<j][k];
					else if(s[1<<j][k]=='?') s[i][k]=s[i^(1<<j)][k];
					else if(s[i^(1<<j)][k]==s[1<<j][k]) s[i][k]=s[1<<j][k];
					else{
						v[i]=1;
						break;
					}
				}
			}
			if(!v[i]) ans[num]=(ans[num]+mi[cnt])%mod;
		}
		for(int i=n;i>=m;--i){
			for(int j=i+1;j<=n;++j){
				ans[i]-=(ans[j]*c[j][i])%mod;
				if(ans[i]<0) ans[i]+=mod;
			}
		}
		printf("%lld\n",ans[m]);
	}
	return 0;
}