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
#include <iostream>
#include <cstring>

using namespace std;

long long preL[600][602], preP[600][602], sufL[600][602], sufP[600][602];
long long pm[600], sm[600];
const long long  b = 1000000007;
long long n,k,q,i,ps,mm,m,j;
char s[603];

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	cin >> n;
	for (k = 0; k < n; k++) {
		cin >> s;
		q = strlen(s);
		pm[k] = 1;
		sm[k] = 1;
		for (j = 0; j <= q + 1; j++) {
			preL[k][j] = 0;
			preP[k][j] = 0;
			sufL[k][j] = 0;
			sufP[k][j] = 0;
		}
		preL[k][0] = 1;
		sufP[k][0] = 1;
		for (j = 0; j < q; j++) {
			if (s[j] == 'L') {
				for (i = pm[k] - 1; i >= 0; i--) preL[k][i + 1] = (preL[k][i] + preP[k][i]) % b;
				pm[k] += 1;
			}
			else {
				for (i = 0; i < pm[k] - 1; i++) preP[k][i] = (preL[k][i + 1] + preP[k][i + 1]) % b;
			}
		}
		for (j = q - 1; j >= 0; j--) {
			if (s[j] == 'L') {
				for (i = 0; i < sm[k] - 1; i++) sufL[k][i] = (sufL[k][i + 1] + sufP[k][i + 1]) % b;
			}
			else {
				for (i = sm[k] - 1; i >= 0; i--) sufP[k][i + 1] = (sufL[k][i] + sufP[k][i]) % b;
				sm[k] += 1;
			}
		}
	}
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			ps = 0;
			if (pm[i] < sm[j]) mm = pm[i];
			else mm = sm[j];
			for (m = 0; m <= mm; m++) ps += (preL[i][m] + preP[i][m])*(sufP[j][m] + sufL[j][m])%b;
			mm += 1;
			for (m = 0; m <= mm; m++) ps -= (preL[i][m + 1] * sufL[j][m] + preP[i][m] * sufP[j][m + 1])%b;
			ps += 1000 * b - 1;
			printf("%ld ", ps % b);
		}
		printf("\n");
	}
}