如题

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

914852
0
0
871234
67018

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

const int P=1000003;

int T;

int n,m,ans;

char str[20][55];

int f[55][32770],g[55][30],len[20];

inline void upd(int &x,int y)

{

	x+=y;

	if(x>P)	x-=P;

}

inline void work()

{

	scanf("%d%d",&n,&m),ans=0;

	register int i,j,k,x,y;

	for(i=0;i<n;i++)	scanf("%s",str[i]+1),len[i]=strlen(str[i]+1);

	memset(f,0,sizeof(f));

	f[0][(1<<n)-1]=1;

	for(j=1;j<=50;j++)

	{

		for(k=0;k<26;k++)

		{

			g[j][k]=0;

			for(i=0;i<n;i++)	g[j][k]|=(str[i][j]=='?'||str[i][j]==k+'a')<<i;

		}

	}

	for(i=0;i<50;i++)	for(x=0;x<(1<<n);x++)

	{

		for(j=0;j<26;j++)	upd(f[i+1][x&g[i+1][j]],f[i][x]);

		for(y=j=0;j<n;j++)	if(((x>>j)&1)&&i==len[j])	y++;

		if(y==m)	upd(ans,f[i][x]);

	}

	for(x=0;x<(1<<n);x++)

	{

		for(y=j=0;j<n;j++)	if(((x>>j)&1)&&i==len[j])	y++;

		if(y==m)	upd(ans,f[50][x]);

	}

	printf("%d\n",ans);

}

int main()

{

	//freopen("bz1879.in","r",stdin);

	scanf("%d",&T);

	while(T--)	work();

	return 0;

}