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

using namespace std;

const int MOD = 1e9 + 7;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<string> in(n);
	for (int i = 0; i <n; i++) cin >> in[i];
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			string d = in[i] + in[j];
			int k = d.size();
			vector<vector<int>> dp(k);
			int offset = k+1;
			for (int i = 0; i < k; i++) dp[i].assign(2*offset + 5, 0);
			bool dupa = false;
			int lastl, lastr;
			lastl = lastr = -1;
			if (d[0] == 'L')
			{
				dp[0][offset+1] = 1;
				dupa =true;
				lastl = 0;
			}
			else
			{
				lastr = 0;
			}
			for (int p = 1; p < k; p++)
			{
				for (int l = 0; l < 2*offset; l++)
				{
					if (d[p] == 'L' && l != 2*offset - 1)
					{
						dp[p][l + 1] += dp[p-1][l];
						dp[p][l+1] %= MOD;
						if (lastl > 0)
						{
							dp[p][l+1] -= dp[lastl - 1][l] - MOD;
							dp[p][l+1] %= MOD;
						}
					}
					else if (l - offset > 0)
					{
						dp[p][l - 1] += dp[p-1][l];
						dp[p][l-1] %= MOD;
						if (lastr > 0)
						{
							dp[p][l-1] -= dp[lastr - 1][l] - MOD;
							dp[p][l-1] %= MOD;
						}
					}
					dp[p][l] += dp[p-1][l];
					dp[p][l] %= MOD;
				}
				if (!dupa && d[p] == 'L')
				{
					dp[p][offset+1]++;
					dp[p][offset+1] %= MOD;
					dupa = true;
				}
				if (d[p] == 'L') lastl = p;
				else lastr = p;
			}
			cout << dp[k - 1][offset] << " ";
		}
		cout << '\n';
	}
}