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
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;
const int MOD = 1000000007;
const int N = 605;

int n, i, j, ind1, ind2, ind, plusCount, k, maxx, e, l, A[N][N], U[N][N], R[N][N], res, len[N], tab[2 * N], con[N][N];
string s;
char t[N];

void print(int T[N][N]) {
	for (int i=maxx;i>=0;i--) {
		for (int j=0;j<=i;j++) printf("%d ", T[i][j]);
		printf("\n");
	}
	printf("\n");
}

void print() {
	printf("A\n");
	print(A);
	printf("U\n");
	print(U);
	printf("R\n");
	print(R);
}

int main() {
scanf("%d", &n);
for (i=0;i<n;i++) {
	scanf("%s", t);
	s = t;
	len[i] = s.size();
	for (j=1;j<=len[i];j++) con[i][j] = (s[j - 1] == 'L');
}
for (i=0;i<n;i++) {
	for (j=0;j<n;j++) {
		ind1 = 1;
		while (ind1 <= len[i] && !con[i][ind1]) ind1++;
		ind2 = len[j];
		while (ind2 >= 1 && con[j][ind2]) ind2--;
		ind = 0;
		for (k=ind1;k<=len[i];k++) tab[++ind] = con[i][k];
		for (k=1;k<=ind2;k++) tab[++ind] = con[j][k];		
		plusCount = 0;
		for (k=1;k<=ind;k++) plusCount += tab[k];
		maxx = min(plusCount, ind - plusCount);
		if (maxx == 0) {
			printf("0 ");
			continue;
		}
		//maxx = 2; ind = 5; tab[1] = 1; tab[2] = 0; tab[3] = 1; tab[4] = 1; tab[5] = 0;
		for (k=0;k<=maxx;k++) for (l=0;l<=k;l++) A[k][l] = U[k][l] = R[k][l] = 0;
		A[0][0] = U[0][0] = R[0][0] = 1;
		for (e=1;e<=ind;e++) {
			if (tab[e]) {
				for (k=maxx;k>=1;k--) {
					for (l=0;l<k;l++) {
						A[k][l] = (A[k][l] + U[k - 1][l]) % MOD;
						U[k][l] = U[k - 1][l];
						R[k][l] = (R[k][l] + U[k - 1][l]) % MOD;
					}
					U[k][k] = 0;
				}
				U[0][0] = 0;
			} else {
				for (k=maxx;k>=1;k--) {
					for (l=k;l>=1;l--) {
						A[k][l] = (A[k][l] + R[k][l - 1]) % MOD;
						U[k][l] = (U[k][l] + R[k][l - 1]) % MOD;
						R[k][l] = R[k][l - 1];
					}
					R[k][0] = 0;
				}
				R[0][0] = 0;
			}
			//print();
		}
		res = 0;
		for (k=1;k<=maxx;k++) res = (res + A[k][k]) % MOD;
		printf("%d ", res);
		//return 0;
	}
	printf("\n");
}
return 0;
}