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
100
101
102
103
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=605;
const int mod=1e9+7;

void add(int &x,int y) {
	x+=y;
	if (x>=mod) {
		x-=mod;
	}
}
int n,m,a[N],dp[N][N],h[N],f[N][N][2],g[N][N][2],e[N][2];
void DP(int i,bool flag) {
	for (int k=0;k<=m;k++) {
		if (!dp[i][k]) {
			continue;
		}
		for (int j=0;j<=1;j++) {
			int to=e[i][j];
			if (0<=to&&to<m) {
				if (a[to]==flag&&!k) {
					continue;
				}
				add(dp[to][k+(a[to]==flag?-1:1)],dp[i][k]);
			}
		}
	}
}

signed main() {
	ios::sync_with_stdio(false),cin.tie(0);
	cout.precision(10),cout.setf(ios::fixed);
	
	cin>>n;
	for (int p=1;p<=n;p++) {
		string s;
		cin>>s;
		m=s.size();
		for (int i=0;i<m;i++) {
			a[i]=s[i]=='P';
		}
		int nxt[2]={m,m};
		for (int i=m-1;i>=0;i--) {
			e[i][0]=nxt[0],e[i][1]=nxt[1];
			nxt[a[i]]=i;
		}
		memset(dp,0,sizeof(dp));
		bool flag=1;
		for (int i=0;i<m;i++) {
			if (flag&&a[i]==0) {
				dp[i][1]++;
				flag=0;
			}
			DP(i,1);
			add(h[p],dp[i][0]);
			for (int k=0;k<=m;k++) {
				if (!dp[i][k]) {
					continue;
				}
				for (int j=0;j<=1;j++) {
					if (e[i][j]==m) {
						add(f[p][k][j],dp[i][k]);
					}
				}
			}
		}
		for (int i=0;i<=1;i++) {
			if (nxt[i]==m) {
				f[p][0][i]++;
			}
		}
		nxt[0]=nxt[1]=-1;
		for (int i=0;i<m;i++) {
			e[i][0]=nxt[0],e[i][1]=nxt[1];
			nxt[a[i]]=i;
		}
		memset(dp,0,sizeof(dp));
		flag=1;
		for (int i=m-1;i>=0;i--) {
			if (flag&&a[i]==1) {
				dp[i][1]++;
				flag=0;
			}
			DP(i,0);
			for (int k=0;k<=m;k++) {
				add(g[p][k][a[i]],dp[i][k]);
			}
		}
	}
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=n;j++) {
			int ans=h[i];
			for (int k=0;k<=600;k++) {
				ans=(ans+1LL*f[i][k][0]*g[j][k][0])%mod;
				ans=(ans+1LL*f[i][k][1]*g[j][k][1])%mod;
			}
			cout<<ans<<" \n"[j==n];
		}
	}
	
	return 0;
}