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

const int P = 1000000000 + 7;

const int N = 600 + 9;
const int N2 = N + N + 9;
int mlen[N];
char messi[N][N];

int fst;
char s[N2];
int prevl[N2];
int prevp[N2];

int myStrLen(char *s) {
	int res = 0;
	while (s[res]) ++res;
	return res;
}

int myStrNCpy(char *dst, char *src, int n) {
	for (int i=0; i<n; ++i) dst[i] = src[i];
}

int memCur;
int memVer[N2][N2];
int memVal[N2][N2];
void memClear() { ++memCur; }
int memCount(int i, int h) { return memVer[i][h] == memCur ? 1 : 0; }
int memGet(int i, int h) { return memVal[i][h]; }
void memSet(int i, int h, int v) { memVer[i][h] = memCur; memVal[i][h] = v; }

int solve(int i, int h) {
	if (i <= fst) return ((i == fst) && (h == 1)) ? 1 : 0;
	if (h < 0) return 0;
	if (memCount(i, h) > 0) return memGet(i, h);
	int res = solve(i - 1, h);
	if (s[i] == 'L') {
		res += solve(i - 1, h - 1);
		res -= solve(prevl[i] - 1, h - 1);
	} else {
		res += solve(i - 1, h + 1);
		res -= solve(prevp[i] - 1, h + 1);
	}
	if (res < 0) res += P;
	if (res >= P) res -= P;
	memSet(i, h, res);
	return res;
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i=0; i<n; ++i) {
		scanf("%s", messi[i]);
		mlen[i] = myStrLen(messi[i]);
	}

	s[0] = 'a';
	s[1] = 'a';
	prevl[0] = prevp[0] = prevl[1] = prevp[1] = 1;
	for (int i=0; i<n; ++i) {
		int off = 2;
		myStrNCpy(s + off, messi[i], mlen[i]);
		off += mlen[i];
		for (int k=2; k<=off; ++k) {
			prevl[k] = prevl[k-1];
			prevp[k] = prevp[k-1];
			if (s[k-1] == 'L') prevl[k] = k - 1;
			if (s[k-1] == 'P') prevp[k] = k - 1;
		}
		for (int j=0; j<n; ++j) {
			myStrNCpy(s + off, messi[j], mlen[j]);
			int len = off + mlen[j];
			for (int k=off+1; k<len; ++k) {
				prevl[k] = prevl[k-1];
				prevp[k] = prevp[k-1];
				if (s[k-1] == 'L') prevl[k] = k - 1;
				if (s[k-1] == 'P') prevp[k] = k - 1;
			}
			for (fst=2; fst<len; ++fst) if (s[fst] == 'L') break;

			int res = 0;
			if (fst < len) {
				memClear();
				res = solve(len - 1, 0);
			}
			printf("%d%s", res, j+1<n ? " " : "\n");
		}
	}

	return 0;
}