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
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef vector<lld> vlld;

constexpr int N = 608;
constexpr lld MOD = 1'000'000'007;

int n, mx;
string t[N];
char s[N + N];

void solve(int p) {
	int l1 = t[p].size();
	int l = l1 + mx;
	auto dp = vector<vlld>(l, vlld((l + 4) / 2, 0));
	lld ret = 0, ret1 = 0;
	bool started = false, started1 = false;
	
	for (int i = 0; i < l1; ++i) {
		s[i] = t[p][i];
	}
	
	for (int i = 0; i < l1; ++i) {
		if (!started) {
			if (s[i] == 'L') {
				dp[i][1] = 1;
				started = true;	
			}
			continue;
		}
		
		int d = s[i] == 'L' ? 1 : -1;
		
		int j = i;
		do {
			--j;
			for (int k = max(d, 0); k <= min(i + 1, l - i - 1); ++k) {
				dp[i][k] += dp[j][k - d];
			}
			
		} while (j > 0 && s[j] != s[i]);
		
		for (int k = 0; k <= min(i + 1, l - i - 1); ++k)
			dp[i][k] %= MOD;
		
		ret += dp[i][0];
	}
	
	ret1 = ret;
	started1 = started;
	
	for (int q = 0; q < n; ++q) {
		ret = ret1;
		started = started1;
		int l2 = t[q].size();
		for (int i = 0; i < l2; ++i) {
			s[l1 + i] = t[q][i];
		}
		
		
		
		for (int i = l1; i < l1 + l2; ++i) {
			if (!started) {
				if (s[i] == 'L') {
					dp[i][1] = 1;
					started = true;	
				}
				continue;
			}
			
			int d = s[i] == 'L' ? 1 : -1;
			
			for (int k = 0; k <= min(i + 1, l - i - 1); ++k)
				dp[i][k] = 0;
				
			int j = i;
			do {
				--j;
				for (int k = max(d, 0); k <= min(i + 1, l - i - 1); ++k) {
					dp[i][k] += dp[j][k - d];
				}
				
			} while (j > 0 && s[j] != s[i]);
			
			for (int k = 0; k <= min(i + 1, l - i - 1); ++k)
				dp[i][k] %= MOD;
			
			ret += dp[i][0];
		}
		
		cout << ret % MOD << " ";
	}
	
	// wyzeruj dp
	
	//return ret % MOD;
}


int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> t[i];
		mx = max(mx, (int)t[i].size());
	}
	
	// cout << solve(s[0]);
	for (int i = 0; i < n; ++i) {
		//for (int j = 0; j < n; ++j) {
			solve(i);
		//}
		cout << "\n";
	}
	
	
	return 0;
}