记录编号	15933	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] Bill的挑战	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	C++	运行时间	1.445 s
提交时间	2010-04-13 09:45:00	内存使用	14.05 MiB

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>

using namespace std;

int f[55][1 << 16],ok[55][200];
char s[18][55];

int n,k,T,len;

inline bool match(char a,char b)
{
	return (a=='?' || b=='?' || a==b);
}

void init()
{
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++)
	{
		scanf("%s",s[i]+1);
	}
	len=strlen(s[1]+1);
	memset(f,0,sizeof(f));
	memset(ok,0,sizeof(ok));
}

void mo(int &a)
{
	while (a>1000003) a -= 1000003;
}

void dp()
{
	f[0][(1<<n)-1] = 1;
	
	for (int i=1;i<=len;i++)
	{
		for (char c='a';c<='z';c++)
		{
			for (int j=1;j<=n;j++)
			{
				if (match(s[j][i],c)) ok[i][(int)c] += (1<<(j-1));
			}
		}
	}
	
	
	for (int i=0;i<len;i++)
	{
		for (int j=1;j<(1<<n);j++)
		{
			if (f[i][j])
			for (char c='a';c<='z';c++)
			{
				if ((ok[i+1][(int)c] & j))
				{
					f[i+1][ok[i+1][(int)c] & j] += f[i][j];
					mo(f[i+1][ok[i+1][(int)c] & j]);
				}
			}
		}
	}
}

void print()
{
	int ans=0;
	for (int i=1;i<(1<<n);i++)
	{
		int count=0;
		for (int j=0;j<n;j++)
			count += ((i>>j) & 1);
		if (count == k) 
		{	
			ans+=f[len][i];
			mo(ans);
		}
	}
	printf("%d\n",ans);
}

int main()
{
	freopen("set.in","r",stdin);
	freopen("set.out","w",stdout);
	scanf("%d",&T);
	for (int i=1;i<=T;i++)
	{
		init();
		dp();
		print();
	}
	return 0;
}