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
#include <iostream>
using namespace std;

const int M = 1000000007;

int dp[1207][1207];

//int second[607][607]; // [slowo][otwarte]
//int first[607][607];

char reverse(char c) {
	if (c == 'L') return 'P';
	else return 'L';
}

string reverse(string s) {
	int i = 0, j = s.length() - 1;
	while (i <= j) {
		swap(s[i], s[j]);		
		i++;
		j--;
	}
	for (i = 0; i < s.length(); i++) {
		s[i] = reverse(s[i]);
	}
	return s;
}

void compute(string s) {
	int n = s.length();
	s = "#" + s;

	int nextL = -1, nextR = -1;
	
	for (int last = n; last >= 0; last--) {
		
		for (int o = 0; o <= n; o++) {
			if (o == 0) dp[last][o] = 1;
			else dp[last][o] = 0;
			
			if (o < n && nextL != -1) dp[last][o] += dp[nextL][o + 1];
			dp[last][o] %= M;
			
			if (o > 0 && nextR != -1) dp[last][o] += dp[nextR][o - 1];
			dp[last][o] %= M;
		}
		
		if (s[last] == 'L') nextL = last;
		else nextR = last;
	}
	
	cout << dp[0][0] - 1 << " ";
}

string words[607];

int main() {
	int n;
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		cin >> words[i];
		
//		compute(words[i]);
//		for (int o = 0; o <= words[i].length(); o++) {
//			second[i][o] = dp[0][o];
//		}
//		compute(reverse(words[i]));
//		for (int o = 0; o <= words[i].length(); o++) {
//			first[i][o] = dp[0][o];
//		}
	}
	
	int ile = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			string s = words[i] + words[j];
			compute(s);
			// cout << dp[0][0] << " ";			
//			int ile = 0;
//			for (int k = 0; k <= min(words[i].size(), words[j].size()); k++) {
//				ile += ((first[i][k] * second[j][k]) % M);
//				ile %= M;
//			}
//			cout << ile << " ";
		}
		cout << "\n";
	}

}