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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[601][601][4], dp2[601][601][4][2], dpM[601][601][2];
const ll mod = 1e09+7;
int t[601][601], dl[601];
int main(){
		int n;
		scanf("%d\n", &n);
		for(int i = 1; i <= n; ++i){
				char c = getchar_unlocked();
				int it = 0;
				while(c == 'L' || c == 'P'){
						++it;
						if(c == 'P') t[i][it] = 1;
						c = getchar_unlocked();
				}
				dl[i] = it;
		}
		for(int N = 1; N <= n; ++N){
				int m = dl[N];
				dp[N][0][0] = 1;
				//for(int i = 1; i <= m; ++i) printf("%d ", t[N][i]);
				//printf("\n");
				for(int i = 1; i <= m; ++i){
						if(!t[N][i]){
								for(int j = i; j; --j){
										dp[N][j][0] = (dp[N][j][0] + dp[N][j-1][0] + dp[N][j-1][2]) % mod;
										dp[N][j-1][1] = (dp[N][j-1][1] + dp[N][j-1][0]) % mod;
										dp[N][j-1][3] = (dp[N][j-1][3] + dp[N][j-1][2]) % mod;
										dp[N][j-1][0] = dp[N][j-1][2] = 0;
								}
						} else{
								for(int j = 0; j < i; ++j){
										dp[N][j][0] = (dp[N][j][0] + dp[N][j+1][0] + dp[N][j+1][1]) % mod;
										dp[N][j+1][2] = (dp[N][j+1][2] + dp[N][j+1][0]) % mod;
										dp[N][j+1][3] = (dp[N][j+1][3] + dp[N][j+1][1]) % mod;
										dp[N][j+1][0] = dp[N][j+1][1] = 0;
								}
						}
				}
				dp2[N][0][0][0] = 1;
				for(int i = m; i; --i){
						if(t[N][i]){
								for(int j = m; j; --j){
										dp2[N][j][0][1] = (dp2[N][j][0][1] + dp2[N][j-1][0][0] + dp2[N][j-1][0][1] + dp2[N][j-1][1][0] + dp2[N][j-1][1][1]) % mod;
										dp2[N][j-1][2][0] = (dp2[N][j-1][2][0] + dp2[N][j-1][0][0]) % mod, dp2[N][j-1][2][1] = (dp2[N][j-1][2][1] + dp2[N][j-1][0][1]) % mod;
										dp2[N][j-1][3][0] = (dp2[N][j-1][3][0] + dp2[N][j-1][1][0]) % mod, dp2[N][j-1][3][1] = (dp2[N][j-1][3][1] + dp2[N][j-1][1][1]) % mod;
										dp2[N][j-1][0][0] = dp2[N][j-1][0][1] = dp2[N][j-1][1][0] = dp2[N][j-1][1][1] = 0;
								}
						} else{
								for(int j = 0; j < m; ++j){
										dp2[N][j][0][0] = (dp2[N][j][0][0] + dp2[N][j+1][0][0] + dp2[N][j+1][0][1] + dp2[N][j+1][2][0] + dp2[N][j+1][2][1]) % mod;
										dp2[N][j+1][1][0] = (dp2[N][j+1][1][0] + dp2[N][j+1][0][0]) % mod, dp2[N][j+1][1][1] = (dp2[N][j+1][1][1] + dp2[N][j+1][0][1]) % mod;
										dp2[N][j+1][3][0] = (dp2[N][j+1][3][0] + dp2[N][j+1][2][0]) % mod, dp2[N][j+1][3][1] = (dp2[N][j+1][3][1] + dp2[N][j+1][2][1]) % mod;
										dp2[N][j+1][0][0] = dp2[N][j+1][0][1] = dp2[N][j+1][2][0] = dp2[N][j+1][2][1] = 0;
								}
						}
				}
				for(int j = 0; j <= m; ++j){
						dpM[N][j][0] = (dp2[N][j][0][0] + dp2[N][j][1][0] + dp2[N][j][2][0] + dp2[N][j][3][0]) % mod;
						dpM[N][j][1] = (dp2[N][j][0][1] + dp2[N][j][1][1] + dp2[N][j][2][1] + dp2[N][j][3][1]) % mod;
				} dpM[N][0][0] = (dpM[N][0][0] + mod - 1) % mod;
				
				//for(int j = 0; j <= m; ++j) printf("%d %lld %lld\n", j, dpM[N][j][0], dpM[N][j][1]);
				//ll wynik = -1;
				//for(int j = 0; j <= m; ++j) wynik += (dp2[N][j][0][0] + dp2[N][j][1][0] + dp2[N][j][2][0] + dp2[N][j][3][0] + dp2[N][j][0][1] + dp2[N][j][1][1] + dp2[N][j][2][1] + dp2[N][j][3][1]) % mod;
				//printf("%lld\n", wynik);
		}
		for(int N = 1; N <= n; ++N){
				for(int M = 1; M <= n; ++M){
						int m = min(dl[N], dl[M]);
						ll wynik = 0;
						for(int j = 0; j <= m; ++j) wynik = (wynik + dpM[M][j][0] * (dp[N][j][0] + dp[N][j][2]) + dpM[M][j][1] * (dp[N][j][0] + dp[N][j][1])) % mod;
						wynik = (wynik + dp[N][0][0] + dp[N][0][1] + dp[N][0][2] + dp[N][0][3] + mod - 1) % mod;
						printf("%lld ", wynik);
				}
				printf("\n");
		}
		
		return 0;
}