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
#include <cstdio>
#include <cstring>
#include <algorithm>
#define scanf(...) scanf(__VA_ARGS__)?:0

using namespace std;

#define MOD 1000000007

int n, l[600];
char s[600][605], s1[1205];

int wynik[1205][605], wys[1205];

int licz(const char *s, int n) {
	wynik[0][0] = 1;
	wys[0] = 0;
	int ol = 0, op = 0;
	for (int i = 1; i <= n; i++) {
		if (s[i] == 'L') {
			wys[i] = min(wys[i-1] + 1, n/2);
			for (int j = 0; j <= wys[i]; j++) wynik[i][j] = 0;
			for (int j = 0; j <= wys[i-1]; j++) {
				wynik[i][j] = (wynik[i][j] + wynik[i-1][j]) % MOD;
				wynik[i][j+1] = (wynik[i-1][j] - (ol > 0 && wys[ol-1] >= j ? wynik[ol-1][j] : 0) + MOD) % MOD;
			}
			ol = i;
		} else {
			wys[i] = wys[i-1];
			for (int j = 0; j <= wys[i]; j++) wynik[i][j] = 0;
			for (int j = wys[i-1]; j > 0; j--) {
				wynik[i][j] = (wynik[i][j] + wynik[i-1][j]) % MOD;
				wynik[i][j-1] = (wynik[i-1][j] - (op > 0 && wys[op-1] >= j ? wynik[op-1][j] : 0) + MOD) % MOD;
			}
			wynik[i][0] = (wynik[i][0] + wynik[i-1][0]) % MOD;
			op = i;
		}
		//for (int j = 0; j <= wys[i]; j++) printf("%d ", wynik[i][j]);
		//puts("");
	}
	return (wynik[n][0] + MOD - 1) % MOD;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf(" %s", s[i]);
		l[i] = strlen(s[i]);
	}
	for (int i = 0; i < n; i++) {
		memcpy(s1 + 1, s[i], l[i]);
		for (int j = 0; j < n; j++) {
			memcpy(s1 + l[i] + 1, s[j], l[j]);
			s1[l[i] + l[j] + 1] = 0;
			printf("%d ", licz(s1, l[i] + l[j]));
		}
		puts("");
	}
}