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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(1); 
const ll mod=1000000007;
const ll mod2=mod*mod;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=610;
int n,nxt[N][2];
ll dp[N][N],l[N][N][2],r[N][N][2],sgn[N];
char s[N];
int main() {
	scanf("%d",&n);
	rep(id,0,n) {
		scanf("%s",s);
		int m=strlen(s);
		nxt[m][0]=nxt[m][1]=m;
		per(i,0,m) {
			nxt[i][0]=nxt[i+1][0];
			nxt[i][1]=nxt[i+1][1];
			if (s[i]=='L') nxt[i][0]=i;
			else nxt[i][1]=i;
		}
		rep(i,0,m+1) rep(j,0,m+1) dp[i][j]=0;
		dp[0][0]=1;
		rep(i,0,m) rep(j,0,m) if (dp[i][j]) {
			dp[i][j]%=mod;
			rep(k,0,2) if (nxt[i][k]!=m&&j+1-2*k>=0)
				dp[nxt[i][k]+1][j+1-2*k]+=dp[i][j];
		}
		rep(i,1,m+1) sgn[id]+=dp[i][0];
		sgn[id]%=mod;
		rep(i,0,m+1) rep(j,0,m+1) if (dp[i][j])	rep(k,0,2) {
			if (nxt[i][k]==m&&j+1-2*k>=0) {
				//printf("??? %d %d %d %d %lld\n",id,i,j,k,dp[i][j]);
				l[id][j][k]+=dp[i][j];
			}
		}
		nxt[m][0]=nxt[m][1]=m;
		per(i,0,m) {
			nxt[i][0]=nxt[i+1][0];
			nxt[i][1]=nxt[i+1][1];
			if (s[m-i-1]=='P') nxt[i][0]=i;
			else nxt[i][1]=i;
		}
		rep(i,0,m+1) rep(j,0,m+1) dp[i][j]=0;
		dp[0][0]=1;
		rep(i,0,m) rep(j,0,m) if (dp[i][j]) {
			dp[i][j]%=mod;
			rep(k,0,2) if (nxt[i][k]!=m&&j+1-2*k>=0)
				dp[nxt[i][k]+1][j+1-2*k]+=dp[i][j];
		}
		rep(i,1,m+1) rep(j,0,m+1) {
			int w=s[m-i]=='L'?0:1;
			r[id][j][w]+=dp[i][j];
		}
		rep(j,0,m+1) rep(k,0,2) {
			l[id][j][k]%=mod;
			r[id][j][k]%=mod;
		}
	}
	rep(i,0,n) rep(j,0,n) {
		ll ans=sgn[i];
		rep(k,0,601) rep(c,0,2) {
			ans=(ans+l[i][k][c]*r[j][k][c]);
			if (ans>=mod2) ans-=mod2;
		}
		ans%=mod;
		printf("%lld%c",ans," \n"[j==n-1]);
	}
}