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
#include <cstdio>
#include <cstdlib>
#include <utility>
#include <cstring>

const int md = 1000000007;

inline void addto(int &a, int b) {
	a = a + b < md ? a + b : a + b - md;
}
inline int add(int a, int b) {
	return a + b < md ? a + b : a + b - md;
}
inline int sub(int a, int b) {
	return a - b < 0 ? a - b + md : a - b;
}
inline int mul(int a, int b) {
	return (long long)a * b % md;
}

const int N = 605;
int n, fwd[N][N][4], bck[N][N][4], len[N], arr[N][4];
char s[N];

void savefwd(char *s, int (*d)[4], int l) {
	int (*prev)[4] = arr, (*cur)[4] = d;
	memset(cur, 0, sizeof arr);
	cur[0][3] = 1;
	for (int i = 0; i < l; ++i) {
		std::swap(prev, cur);
		memset(cur, 0, sizeof arr);
		for (int j = 0; j <= i; ++j) {
			for (int k = 0; k < 4; ++k) {
				if (s[i] && k >> 1 & 1) addto(cur[j + 1][3], prev[j][k]);
				if (!s[i] && k & 1 && j) addto(cur[j - 1][3], prev[j][k]);
				addto(cur[j][k & ~(1 << s[i])], prev[j][k]);
			}
		}
	}
	memcpy(d, cur, sizeof arr);
}

void savebck(char *s, int (*d)[4], int l) {
	int (*prev)[4] = arr, (*cur)[4] = d;
	memset(cur, 0, sizeof cur);
	cur[0][0] = cur[0][1] = cur[0][2] = cur[0][3] = 1;
	for (int i = l; i >= 1; --i) {
		std::swap(prev, cur);
		memset(cur, 0, sizeof arr);
		for (int j = 0; j <= l - i; ++j) {
			for (int k = 0; k < 4; ++k) {
				if (s[i - 1] && k >> 1 & 1 && j) addto(cur[j - 1][k], prev[j][3]);
				if (!s[i - 1] && k & 1) addto(cur[j + 1][k], prev[j][3]);
				if (k >> s[i - 1] & 1 ^ 1) {
					addto(cur[j][k], prev[j][k]);
					addto(cur[j][k | 1 << s[i - 1]], prev[j][k]);
				}
			}
		}
	}
	memcpy(d, cur, sizeof arr);
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%s", s);
		int l;
		for (l = 0; s[l]; ++l) {
			if (s[l] == 'L') s[l] = 1;
			else s[l] = 0;
		}
		savefwd(s, fwd[i], l);
		savebck(s, bck[i], l);
		len[i] = l;
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			int ans = 0;
			for (int k = 0; k <= len[i]; ++k) 
				for (int l = 1; l < 4; ++l) 
					ans = add(ans, mul(fwd[i][k][l], bck[j][k][l]));
			ans = add(ans, fwd[i][0][0]);
			printf("%d ", sub(ans, 1));
		}
		printf("\n");
	}
	return 0;
}