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
#include "bits/stdc++.h" // Tomasz Nowak
using namespace std;     // University of Warsaw
using LL = long long;
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
#define ssize(x) int(x.size())
template<class A, class B> auto& operator<<(ostream &o, pair<A, B> p) {
	return o << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &o, T x) -> decltype(x.end(), o) {
	o << '{'; int i = 0; for(auto e : x) o << (", ")+2*!i++ << e; return o << '}';
}
#ifdef DEBUG
#define debug(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n'
#else
#define debug(...) {}
#endif

constexpr int mod = int(1e9) + 7;

#ifdef DEBUG
constexpr int max_bil = 10;
#else
constexpr int max_bil = 600;
#endif
using A = array<LL, max_bil + 1>;

int mod_val(LL x) {
	int ret = int(x % mod);
	if(ret < 0)
		ret += mod;
	return ret;
}
void mod_arr(A &a) {
	for(LL &x : a)
	   x = mod_val(x);
}
void mod_tuple(A &ans, A &last0, A &last1) {
	mod_arr(ans);
	mod_arr(last0);
	mod_arr(last1);
}

tuple<A, A, A> dp_left(const vector<bool> &in) {
	A ans;
	fill(ans.begin(), ans.end(), 0);
	A last0 = ans;
	A last1 = ans;
	ans[0] = 1;

	REP(i, ssize(in)) {
		A new_ans = ans;
		if(in[i]) {
			FOR(bil, 0, i)
				new_ans[bil + 1] += ans[bil] - last1[bil];
			last1 = ans;
		}
		else {
			FOR(bil, 0, i)
				new_ans[bil] += ans[bil + 1] - last0[bil + 1];
			last0 = ans;
		}
		ans = new_ans;
		if(i % 15 == 0)
			mod_tuple(ans, last0, last1);
	}
	mod_tuple(ans, last0, last1);
	return tuple(ans, last0, last1);
}

LL dp_right(const vector<bool> &in, const tuple<A, A, A> &init) {
	auto [ans, last0, last1] = init;

	REP(i, ssize(in)) {
		A new_ans = ans;
		if(in[i]) {
			FOR(bil, 0, max_bil - 1 - i)
				new_ans[bil + 1] += ans[bil] - last1[bil];
			last1 = ans;
		}
		else {
			FOR(bil, 0, max_bil - 1 - i)
				new_ans[bil] += ans[bil + 1] - last0[bil + 1];
			last0 = ans;
		}
		ans = new_ans;
		if(i % 15 == 0)
			mod_tuple(ans, last0, last1);
	}
	return mod_val(ans[0] - 1);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n;
	cin >> n;
	vector<vector<bool>> in(n);
	for(auto &s_bools : in) {
		string s;
		cin >> s;
		s_bools.resize(ssize(s));
		REP(i, ssize(s))
			if(s[i] == 'L')
				s_bools[i] = true;
	}
	debug(n, in);

	vector<tuple<A, A, A>> left_parts(n);
	REP(i, n)
		left_parts[i] = dp_left(in[i]);

	vector ans(n, vector<LL>(n));
	REP(i, n)
		REP(j, n)
			ans[i][j] = dp_right(in[j], left_parts[i]);

	REP(i, n) {
		REP(j, n)
			cout << ans[i][j] << ' ';
		cout << '\n';
	}
}