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<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=605,M=N*2,P=1000000007;
int n,m,sz,len,i,j,k,ans,f[N][M],g[N][M],cur[M];char s[N][N];
inline void up(int&a,int b){a=a+b<P?a+b:a+b-P;}
int main(){
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%s",s[i]);
		m=max(m,(int)strlen(s[i]));
	}
	sz=m*2+1;
	/*
	0     1
	1     '(',1
	i     '(',i
	m     '(',m
	m+1   ')',0
	m+1+i ')',i
	m+m ')',m-1
	*/
	for(i=0;i<n;i++){
		len=strlen(s[i]);
		
		for(j=0;j<sz;j++)cur[j]=0;
		cur[0]=1;
		for(j=0;j<len;j++){
			if(s[i][j]=='L'){
				/*
				nxt['(',j]=pre['(',j-1]+pre[')',j-1]
				nxt[')',j]=pre[')',j]
				*/
				for(k=m;k;k--){
					cur[k]=cur[k-1];
					up(cur[k],cur[k+m]);
				}
			}else{
				/*
				nxt[')',j]=pre[')',j+1]+pre['(',j+1]
				nxt['(',j]=pre['(',j]
				*/
				for(k=0;k<m;k++){
					cur[k+m+1]=cur[k+1];
					if(k+1<m)up(cur[k+m+1],cur[k+m+2]);
				}
			}
		}
		for(j=0;j<sz;j++)f[i][j]=cur[j];//from state('1') to j

		for(j=0;j<sz;j++)cur[j]=0;
		cur[m+1]=1;
		for(j=len-1;~j;j--){
			if(s[i][j]=='L'){
				up(cur[0],cur[1]);
				for(k=1;k<=m;k++){
					up(cur[k+m],cur[k]);
					cur[k]=k<m?cur[k+1]:0;
				}
			}else{
				for(k=m-1;~k;k--){
					up(cur[k+1],cur[k+m+1]);
					if(k+1<m)cur[k+m+2]=cur[k+m+1];
				}
				cur[m+1]=0;
			}
		}
		for(j=0;j<sz;j++)g[i][j]=cur[j];//from j to state(')',0)
		//printf("%d %d\n",f[i][m+1],g[i][0]);
	}
	for(i=0;i<n;i++)for(j=0;j<n;j++){
		ans=0;
		for(k=0;k<sz;k++)ans=(ans+1LL*f[i][k]*g[j][k])%P;
		printf("%d%c",ans,j+1<n?' ':'\n');
	}
}