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
97
#include <bits/stdc++.h>
#include <time.h>
#define qio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug(x) cerr<<#x<<" "<<x<<endl
#define ll long long 
#define st first
#define nd second
using namespace std;

int n, t, mem[1206][1206], x, mod = 1000000007, nextl[1206], nextr[1206], suf[1206], indeks;
string s[602], z;
pair <int, int> operacje[2000006];

int reszta(int a, int b) {
	if (a + b >= mod) return a + b - mod;
	return a + b;
}

int solve(int last, int o) {
	//cout << last << " " << o << endl;
	if (last != -1 && mem[last][o] != -1) return mem[last][o];
	if (suf[last + 1] < o) {
		return 0;	x++;
	}
	int res;
	if (o == 0 && last != -1) res = 1;
	else res = 0;

	int next = nextl[last + 1];
	if (next < z.size()) res = reszta(res, solve(next, o + 1));

	if (o > 0) {
		next = nextr[last + 1];
		if (next < z.size()) res = reszta(res, solve(next, o - 1));
	}

	if (last != -1) {
		mem[last][o] = res;
		indeks++;
		operacje[indeks] = { last,o };
	}
	return res;
}

int main()
{
	qio;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
	}
	for (int i = 0; i <= 1200; i++) {
		for (int j = 0; j <= 1200; j++) {
			mem[i][j] = -1;
		}
	}
	//clock_t start, end;
	for (int i = 1; i <= n; i++) {
		//start = clock();
		for (int j = 1; j <= n; j++) {
			//start = clock();
			z = s[i] + s[j];
			int aktl = z.size();
			int aktr = z.size();
			suf[z.size()] = 0;
			nextl[z.size()] = z.size();
			nextr[z.size()] = z.size();
			for (int k = z.size() - 1; k >= 0; k--) {
				suf[k] = 0;
				if (z[k] == 'L') aktl = k;
				else {
					aktr = k;
					suf[k]++;
				}
				nextl[k] = aktl;
				nextr[k] = aktr;
				suf[k] += suf[k + 1];
			}
			cout << solve(-1, 0) << " ";
			//end = clock();
			//double tt = double(end - start) / double(CLOCKS_PER_SEC);
			//cout << "Time Taken is: " << fixed << tt << setprecision(5) << endl;
			//start = clock();
			while (indeks) {
				mem[operacje[indeks].st][operacje[indeks].nd] = -1;
				indeks--;
			}
			//end = clock();
			//tt = double(end - start) / double(CLOCKS_PER_SEC);
			//cout << "Time Taken is: " << fixed << tt << setprecision(5) << endl;
		}
		//end = clock();
		//double tt = double(end - start) / double(CLOCKS_PER_SEC);
		//cout << "Time Taken is: " << fixed << tt << setprecision(5) << endl;
		cout << endl;
	}
}