1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
//泥の分際で私だけの大切を奪おうだなん
#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int p=1e9+7;
int qp(int x,int y)
{
	int res=1;
	for(int t=x; y; y>>=1,t=1ll*t*t%p)
		if(y&1) res=1ll*res*t%p;
	return res;
}
int N=read(),M=read(),in=read(),n=N-in;
char s[33];
int C[33][33],a[33],ans[33];
int f[2][33][801][129];
signed main()
{
	while(in--)
	{
		scanf("%s",s+1);
		bool flg=1;int d=0;
		for(int i=1; i<=M; ++i)
			if(flg)
			{
				if(s[i]=='C') ++a[0]; else --a[0];
				if(s[i]!=s[1]) flg=0;
			}
			else
			{
				++d;
				if(s[i]=='C') ++a[d];
				if(s[1]=='N') --a[d];
			}
		if(!flg)
		{
			++d;
			if(s[1]=='C') ++a[d];
			else --a[d];
		}
	}
	for(int i=0; i<=N; ++i)
	{
		C[i][0]=1;
		for(int j=1; j<=i; ++j)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;
	}
	const int X=64,Y=400;
	f[(M-1)&1][0][Y][X]=1;
	for(int d=M-1; d>0; --d)
	{
		int coef=M-d-1;
		memset(f[(d-1)&1],0,sizeof(f[0]));
		for(int m=0; m<=n; ++m)
			for(int a0=-400; a0<=400; ++a0) 
				for(int sum=-64; sum<=64; ++sum) if(f[d&1][m][a0+Y][sum+X])
		{
			int val=f[d&1][m][a0+Y][sum+X];
			f[d&1][m][a0+Y][sum+X]=0;
			for(int i=0; m+i<=n; ++i)
				for(int j=0; m+i+j<=n; ++j)
				{
					if(a0+(i-j)*coef-j<-Y||a0+(i-j)*coef-j>Y) continue;
					int val1=1ll*C[n-m][i+j]*C[i+j][i]%p*val%p;
					for(int k=0; k<=m; ++k)
					{
						int nw=sum+k+i+j+a[d];
						if(nw&1) continue;
						int &A=f[(d-1)&1][m+i+j][a0+(i-j)*coef-j+Y][nw/2+X];
						A=(A+1ll*val1*C[m][k]%p)%p;
					}
				}	
		}
	}
		for(int m=0; m<=n; ++m)
			for(int a0=-400; a0<=400; ++a0) 
				for(int sum=-64; sum<=64; ++sum) 
					if(f[0][m][a0+Y][sum+X])
	{
		for(int i=0; m+i<=n; ++i)
			for(int j=0; m+i+j<=n; ++j)
				if(sum+a0+a[0]+M*i-M*j==0)
					ans[m+i+j]=(ans[m+i+j]
					+1ll*C[n-m][i+j]*C[i+j][i]%p*
					f[0][m][a0+Y][sum+X])%p;
	}
	for(int i=0; i<=n; ++i)
		printf("%lld ",1ll*qp(C[n][i],p-2)*ans[i]%p);
	return 0;
}