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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 600 + 5;
const int mod = 1e9 + 7;

inline void add_mod(int &a,int b){ a+=b; if(a>=mod) a-=mod;}

struct Data
{
	char s[MAXN];
	int len, f[MAXN][2], g[MAXN][2], ans;
	
	void init(void)
	{
		scanf("%s",s+1);
		len = strlen(s+1);
		
		static int nxt[MAXN][2];
		nxt[len+1][0] = len+1; nxt[len+1][1] = len+2;
		for(int i=len; i>=1; --i)
		{
			nxt[i][0] = nxt[i+1][0];
			nxt[i][1] = nxt[i+1][1];
			nxt[i][s[i] == 'P'] = i;
		}
		
		static int dp[MAXN][MAXN];
		memset(dp, 0, sizeof(dp));
		dp[ nxt[1][0] ][1] = 1;
		
		for(int i=1; i<=len; ++i)
		{
			add_mod(ans, dp[i][0]);
			for(int j=0; j<=i; ++j) if(dp[i][j])
			{
				add_mod(dp[ nxt[i+1][0] ][j+1], dp[i][j]);
				if(j) add_mod(dp[ nxt[i+1][1] ][j-1], dp[i][j]);
			}
		}
		
		for(int i=0; i<=len; ++i)
		{
			f[i][0] = dp[len+1][i+1];
			if(i) f[i][1] = dp[len+2][i-1];
		}
		
		static int pre[MAXN][2];
		pre[0][0] = pre[0][1] = 0;
		for(int i=1; i<=len; ++i)
		{
			pre[i][0] = pre[i-1][0];
			pre[i][1] = pre[i-1][1];
			pre[i][s[i] == 'P'] = i;
		}
		
		memset(dp, 0, sizeof(dp));
		dp[pre[len][1]][1] = 1;
		for(int i=len; i>=1; --i)
		{
			for(int j=0; j<=len-i+1; ++j) if(dp[i][j])
			{
				add_mod(dp[ pre[i-1][1] ][j+1], dp[i][j]);
				if(j) add_mod(dp[ pre[i-1][0] ][j-1], dp[i][j]);
				
				add_mod(g[j][s[i] == 'P'], dp[i][j]);
			}
		}
	}
	
	int getres(const Data &oth) const
	{
		int res = ans;
		for(int i=0; i<=len && i<=oth.len; ++i)
		{
			res = (res + (ll)f[i][0] * oth.g[i][0] + (ll)f[i][1] * oth.g[i][1]) %mod;
		}
		return res;
	}
}dat[MAXN];

int main(void)
{
#ifdef He_Ren
	freopen("b.in","r",stdin);
	freopen("b.out","w",stdout);
#endif
	
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; ++i)
		dat[i].init();
	
	for(int i=1; i<=n; ++i, printf("\n"))
		for(int j=1; j<=n; ++j)
			printf("%d ",dat[i].getres(dat[j]));
	return 0;
}