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
#include<bits/stdc++.h>

using namespace std;

const int N = 32, M = 24, Mod = 1e9 + 7, S = N * M, W = 2 * N;

inline void upd(int &x, int dx){
	x += dx;
	if(x >= Mod) x -= Mod;
}

int n = 0, m = 0, k = 0, d[M + 1] = {}, c[N + 1][N + 1] = {}, z[N + 1][N + 1][2 * N + 1] = {};
int tot = 0, id[N + 1][N + 1] = {};
int f[(N + 1) * (N + 2) / 2][2 * N * M + 1][2 * N + 1] = {}, g[(N + 1) * (N + 2) / 2][2 * N * M + 1][4 * N + 1] = {}, h[4 * N + 1] = {}, ans[N + 1] = {};
char str[M + 1] = {};

int main(){
	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]) % Mod;
	}
	for(int i = 0 ; i <= N ; i ++) for(int j = 0 ; i + j <= N ; j ++) for(int x = 0 ; x <= i ; x ++) for(int y = 0 ; y <= j ; y ++) z[i][j][N + x - y] = (z[i][j][N + x - y] + 1ll * c[i][x] * c[j][y]) % Mod;
	scanf("%d %d %d", &n, &m, &k); n -= k;
	for(int a = 0 ; a <= n ; a ++) for(int b = 0 ; a + b <= n ; b ++) id[a][b] = tot ++;
	for(int i = 0 ; i < k ; i ++){
		scanf("%s", str);
		int t = 1, w = (str[0] == 'C') ? 1 : -1;
		while(t < m && str[t - 1] == str[t]) t ++;
		if(t < m){
			d[1] += (t - 1) * w;
			for(int j = t + 1 ; j <= m ; j ++) if(j == m || str[j] == str[0]) d[j - t + 1] += w;
		}
		else d[1] += t * w;
	}
	f[0][S][N] = 1;
	for(int i = m ; i >= 2 ; i --){
		memset(g, 0, sizeof(g));
		for(int a = 0 ; a <= n ; a ++) for(int b = 0 ; a + b <= n ; b ++) for(int s = -b * (m - i) ; s <= a * (m - i) ; s ++){
			memset(h, 0, sizeof(h));
			for(int w = -(n + k) ; w <= (n + k) ; w ++) if(f[id[a][b]][S + s][N + w]) for(int x = -b ; x <= a ; x ++) upd(h[W + w + x + d[i]], 1ll * f[id[a][b]][S + s][N + w] * z[a][b][N + x] % Mod);
			for(int w = -2 * (n + k) ; w <= 2 * (n + k) ; w ++) if(h[W + w]) for(int x = 0 ; a + b + x <= n ; x ++) upd(g[id[a + x][b]][S + s + x * (m - i)][W + w + x], 1ll * h[W + w] * c[a + b + x][x] % Mod);
		}
		memset(f, 0, sizeof(f));
		for(int a = 0 ; a <= n ; a ++) for(int b = 0 ; a + b <= n ; b ++) for(int s = -b * (m - i) ; s <= a * (m - i) ; s ++) for(int w = -2 * (n + k) ; w <= 2 * (n + k) ; w ++) if(g[id[a][b]][S + s][W + w]) for(int x = abs(w) & 1 ; a + b + x <= n ; x += 2) upd(f[id[a][b + x]][S + s - x * (m - i)][N + (w - x) / 2], 1ll * g[id[a][b]][S + s][W + w] * c[a + b + x][x] % Mod);
	}
	for(int a = 0 ; a <= n ; a ++) for(int b = 0 ; a + b <= n ; b ++) for(int s = -b * m ; s <= a * m ; s ++) for(int w = -(n + k) ; w <= (n + k) ; w ++) if(f[id[a][b]][S + s][N + w]){
		int r = abs(s + w + d[1]);
		if(r % m == 0){
			r /= m;
			for(int x = 0 ; 2 * x + r <= n ; x ++) upd(ans[a + b + 2 * x + r], 1ll * f[id[a][b]][S + s][N + w] * c[a + b + 2 * x + r][2 * x + r] % Mod * c[2 * x + r][x] % Mod);
		}
	}
	for(int x = 0 ; x <= n ; x ++) printf("%d ", ans[x]);
	return 0;
}