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
#include "bits/stdc++.h" // Ignacy Boehlke
using namespace std;     // XIII LO Szczecin
template<class A,class B>ostream&operator<<(ostream&os,pair<A,B>p){return os<<'{'<<p.first<<", "<<p.second<<'}';}
template<class T>auto operator<<(ostream&os,T v)->decltype(v.end(),os){os<<'{';int i=0;for(auto e:v)os<<(", ")+2*!i++<<e;return os<<'}';}
#ifdef DEBUG
#define LOG(x...)cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<'\n';}(x)
#else
#define LOG(...)(void)0
#endif
#define ssize(x)((int)x.size())
#define FOR(a,b,c)for(int a=(b);a<=(c);a++)
#define REP(a,b)FOR(a,0,(b)-1)
#define ALL(x)(x).begin(), (x).end()
#define fi first
#define se second
using ll=long long;

constexpr int MOD = 1000000007;
int add(int a, int b) {return a + b < MOD ? a + b : a + b - MOD;}
int add(int a, int b, int c, int d) {return add(add(a, b), add(c, d));}
void addto(int& a, int b) {a = add(a, b);}
int mul(int a, int b) {return (int)((ll)a * b % MOD);}
using TTT = array<array<array<int, 2>, 2>, 2>;// [i][j][k] -> i - last, j - is ( forbidden, k - is ) forbidden
TTT ST, NXT;

void count(const string& s, vector<TTT>& vec) {
	vec = {NXT};
	for (char c : s) {
		vector<TTT> sec(vec.size());

		REP(d, ssize(sec)) REP(i, 2) REP(j, 2) REP(k, 2)
			addto(sec[d][i][j || (c == 'L')][k || (c == 'P')], vec[d][i][j][k]);

		if (c == 'L') {
			FOR(d, 1, ssize(sec) - 1) {
				addto(sec[d][0][0][0], add(vec[d - 1][0][0][0],
							   vec[d - 1][0][0][1],
							   vec[d - 1][1][0][0],
							   vec[d - 1][1][0][1]));
			}
			sec.push_back(NXT);
		} else {
			REP(d, ssize(sec) - 1) {
				addto(sec[d][1][0][0], add(vec[d + 1][0][0][0],
							   vec[d + 1][0][1][0],
							   vec[d + 1][1][0][0],
							   vec[d + 1][1][1][0]));
			}
		}
		swap(sec, vec);
	}
}

int main() {
	NXT[0][0][0] = 1;
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	vector<array<int, 2>> has(n);
	vector<vector<TTT>> pre(n);
	vector<vector<array<int, 2>>> suf(n);
	REP(i, n) {
		string s;
		cin >> s;
		if (s.find('L') != string::npos) has[i][0] = true;
		if (s.find('R') != string::npos) has[i][1] = true;

		count(s, pre[i]);
		reverse(ALL(s));
		for (char& c : s) c = (c == 'L' ? 'P' : 'L');
		vector<TTT> tmp;
		count(s, tmp);
		suf[i].resize(tmp.size());
		REP(j, ssize(suf[i])) {
			REP(k, 2) REP(l, 2) REP(p, 2)
				addto(suf[i][j][k], tmp[j][k][l][p]);
		}
		LOG(i); LOG(pre[i]); LOG(suf[i]);
	}

	vector<vector<array<int, 3>>> ps(n);
	vector<vector<int>> ss(n);
	REP(i, n) {
		ps[i].resize(pre[i].size());
		REP(d, ssize(pre[i])) {
			const auto& p = pre[i][d];
			ps[i][d] = {add(p[0][0][0], p[1][0][0]),
				    add(p[0][0][1], p[1][0][1]),
				    add(p[0][1][0], p[1][1][0])};
		}
		ss[i].resize(suf[i].size());
		REP(d, ssize(suf[i])) ss[i][d] = suf[i][d][0] + suf[i][d][1];
	}
	REP(i, n) {
		REP(j, n) {
			int res = 0, c = min(ssize(pre[i]), ssize(suf[j]));
			{
			const auto& p = pre[i][0];
			const auto& s = suf[j][0];
			res = add(res, add(p[1][1][1],
					   p[1][0][0],
					   p[1][0][1],
					   p[1][1][0]));
			addto(res, mul(p[1][0][0], s[1]));
			addto(res, mul(p[1][0][1], s[1]));
						       
			if (!has[i][0]) addto(res, s[1]);
			}
			FOR(d, 1, c - 1) {
				const auto& p = ps[i][d];
				const auto& s = suf[j][d];

				addto(res, mul(p[0], ss[j][d]));
				addto(res, mul(p[1], s[1]));
				addto(res, mul(p[2], s[0]));
			}
			cout << res << ' ';
		}
		cout << '\n';
	}
}