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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <algorithm>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define REP(i,n) FOR(i,0,n)
#define REPD(i,n) FORD(i,0,n)
#define VAR(v,w) __typeof(w) v=(w)
#define FORE(it,c) for(VAR(it,(c).begin());it!=(c).end();++it)
#define PB push_back
#define ALL(c) (c).begin(),(c).end()
#define SIZE(c) ((int)(c).size())
#define INT(x) int x; scanf("%d", &x)
#define STR(n,x) char x[n]; scanf("%s", x)

typedef long long LL;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<VI> VVI;

const int mod = 1000000007;

int r[601][601], ls[601], ps[601];
bool ifl[601], ifp[601];

void go(const string& a, VI& vf, VI& vfl, VI& vfp, int& vflp, VI& vel, VI& vep) {
	int n = SIZE(a);
	ifl[n] = ifp[n] = 0;
	REPD(i,n) {
		ifl[i] = ifl[i + 1] || a[i] == 'L';
		ifp[i] = ifp[i + 1] || a[i] == 'P';
	}
	r[0][0] = ls[0] = ps[0] = 1;
	FOR(j,1,n+1) r[0][j] = ls[j] = ps[j] = 0;
	FOR(i,1,n+1) {
		if (a[i - 1] == 'L') {
			r[i][0] = 0;
			FOR(j,1,n+1) r[i][j] = ls[j - 1];
			REP(j,n+1) ls[j] = r[i][j];
			REP(j,n+1) ps[j] = (ps[j] + r[i][j]) % mod;
		} else {
			REP(j,n) r[i][j] = ps[j + 1];
			r[i][n] = 0;
			REP(j,n+1) ps[j] = r[i][j];
			REP(j,n+1) ls[j] = (ls[j] + r[i][j]) % mod;
		}
	}
	vf.clear();
	vfl.clear();
	vfp.clear();
	vflp = 0;
	vel.clear();
	vep.clear();
	vf.resize(n + 1);
	vfl.resize(n + 1);
	vfp.resize(n + 1);
	vel.resize(n + 1);
	vep.resize(n + 1);
	REP(i,n+1) {
		if (ifl[i] && ifp[i]) {
			vflp = (vflp + r[i][0]) % mod;
		} else if (ifl[i]) {
			REP(j,n+1) vfl[j] = (vfl[j] + r[i][j]) % mod;
		} else if (ifp[i]) {
			REP(j,n+1) vfp[j] = (vfp[j] + r[i][j]) % mod;
		}
		if (i) {
			if (a[i - 1] == 'L') {
				REP(j,n+1) vel[j] = (vel[j] + r[i][j]) % mod;
			} else {
				REP(j,n+1) vep[j] = (vep[j] + r[i][j]) % mod;
			}
		}
	}
	REP(j,n+1) vf[j] = r[n][j];
}

int main() {
	INT(n);
	VS a;
	REP(i,n) {
		STR(601, aa);
		a.PB(aa);
	}
	VVI vf, vfl, vfp;
	VI vflp;
	REP(i,n) {
		VI vf0, vfl0, vfp0, vel0, vep0;
		int vflp0;
		go(a[i], vf0, vfl0, vfp0, vflp0, vel0, vep0);
		vf.PB(vf0);
		vfl.PB(vfl0);
		vfp.PB(vfp0);
		vflp.PB(vflp0);
	}
	REP(i,n) {
		reverse(ALL(a[i]));
		FORE(it,a[i]) *it = 'P' - *it + 'L';
	}
	VVI wel, wep;
	REP(i,n) {
		VI wf0, wfl0, wfp0, wel0, wep0;
		int wflp0;
		go(a[i], wf0, wfl0, wfp0, wflp0, wel0, wep0);
		wel.PB(wel0);
		wep.PB(wep0);
	}
	REP(i,n) {
		const int* vf0 = vf[i].data();
		const int* vfl0 = vfl[i].data();
		const int* vfp0 = vfp[i].data();
		int vflp0 = vflp[i];
		REP(j,n) {
			const int* wel0 = wel[j].data();
			const int* wep0 = wep[j].data();
			if (j) printf(" ");
			int x = min(SIZE(vf[i]), SIZE(wel[j]));
			int res = mod - 1;
			REP(k,x) res = (res + LL(vf0[k] + vfl0[k]) * wel0[k] + LL(vf0[k] + vfp0[k]) * wep0[k]) % mod;
			res = (LL(res) + vf0[0] + vfl0[0] + vfp0[0] + vflp0) % mod;
			printf("%d", res);
		}
		printf("\n");
	}
}