不开O2只有70,开O2才满分...所以见标题. 复杂度也是O($50\times2^{15}\times 26$) 代码如下：

//不等,不问,不犹豫,不回头.
//历经千辛万苦我终于看懂这道题的题解了.....
//首先看到一共的字符串长度为15,就知道要对个数进行状压了.
//考虑到我们光知道和哪些串进行匹配,好像不能转移..
//那对串一个一个填(这也是一个套路吧)...设f[i][j]表示填了前i位且匹配的状态为j的字符串个数.
//考虑怎么转移.我们枚举第i位填哪个字母.考虑当前位的影响,这里有两种想法,一种是在原来的基础上加上当前位合法的.
//但,考虑真正匹配的当前位合法的,之前的一定也合法啊,也就是说要加的东西一定已经在之前的状态了.
//那就考虑将当前位不合法的去掉.这里&一下就行了.
//f[i][j&t]+=f[i-1][j]
#include<bits/stdc++.h>
#define _ 0
#define ls p<<1
#define db double
#define rs p<<1|1
#define RE register
#define P 1e6+3
#define ll long long
#define INF 1000000000
#define get(x) x=read()
#define PLI pair<ll,int>
#define PII pair<int,int>
#define pb(x) push_back(x)
#define ull unsigned long long
#define put(x) printf("%d\n",x)
#define putl(x) printf("%lld\n",x)
#define rep(x,y,z) for(RE int x=y;x<=z;++x)
#define fep(x,y,z) for(RE int x=y;x>=z;--x)
#define go(x) for(RE int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y)
using namespace std;
const int N=1<<15,M=52;
int f[M][N],n,T,k,mast[M][30],m; 
char c[17][M];

char *fs,*ft,buf[1<<15];
//inline char getc() {return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int read()
{
	int x=0,ff=1;
	char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
	while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*ff;
}

inline void init()
{
	get(n);get(k);
	rep(i,1,n) scanf("%s",c[i]+1);
	m=strlen(c[1]+1);
}

inline bool check(int x)
{
	int cnt=0;
	rep(i,0,14) if(x&1<<i) ++cnt;
	return (cnt==k);
}

inline void run()
{
	memset(f,0,sizeof(f));f[0][(1<<n)-1]=1;
	memset(mast,0,sizeof(mast));
	rep(i,1,m) //枚举位数 
	{
		rep(j,0,25) //枚举这一位填的字符. 
			rep(k,1,n) if(c[k][i]=='?'||c[k][i]-'a'==j) mast[i][j]|=1<<k-1;
	}
	rep(i,1,m) //枚举填的位数
	{
		rep(j,0,(1<<n)-1)//枚举状态. 
		{
			rep(k,0,25) //枚举这一位填的字符. 
			{
				int t=j&mast[i][k];
				f[i][t]+=f[i-1][j];
				if(f[i][t]>=P) f[i][t]-=P; 
			}
		}
	} 
	int ans=0;
	rep(j,0,(1<<n)-1) 
	{
		if(check(j)) 
		{
			ans+=f[m][j];
			if(ans>=P) ans-=P;	
		}	
	}
	put(ans);
}

int main()
{
	//freopen("1.in","r",stdin);
	get(T);
	while(T--) init(),run();
	return (0^_^0);
}
//以吾之血,铸吾最后的亡魂.