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
129
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>

using namespace std;
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

#define int long long
const int MAXN = 609;
const int mod = (int) (1e9 + 7);
int dp[MAXN][MAXN][2];
int mul[MAXN][MAXN][2];
int dpt[MAXN][MAXN][2];
int tmp[MAXN][MAXN][2];

void add(int &x, int y) {
    x += y;
    if (x >= mod)
        x -= mod;
}

void sub(int &x, int y) {
    x -= y;
    if (x < 0)
        x += mod;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    REP(i, n) {
        string s;
        cin >> s;
        int m = (long long) (s.size());
        s = "#" + s;
        REP(j, m + 3) {
            REP(k, m + 3) {
                dpt[j][k][0] = dpt[j][k][1] = 0;
                tmp[j][k][0] = tmp[j][k][1] = 0;
            }
        }

        vector<int> prev(m + 1);
        int pL = 0, pR = 0;
        FOR(j, 1, m) {
            if (s[j] == 'L') {
                prev[j] = pL;
                pL = j;
            }
            else {
                prev[j] = pR;
                pR = j;
            }
        }

        FOR(j, 1, m) {
            REP(k, m + 1) {
                dpt[j][k][0] = dpt[j - 1][k][0];
                dpt[j][k][1] = dpt[j - 1][k][1];
                if (s[j] == 'L' && k != 0) {
                    dpt[j][k][0] += dpt[j - 1][k - 1][0] + dpt[j - 1][k - 1][1];
                    if (k == 1)
                        dpt[j][k][0]++;
                    dpt[j][k][0] %= mod;
                    sub(dpt[j][k][0], dpt[prev[j]][k][0]);
                } else if (s[j] == 'P') {
                    dpt[j][k][1] += dpt[j - 1][k + 1][0] + dpt[j - 1][k + 1][1];
                    dpt[j][k][1] %= mod;
                    sub(dpt[j][k][1], dpt[prev[j]][k][1]);
                }
            }
        }
        
        tmp[m][0][1] = 1;
        for (int j = m; j > 0; j--) {
            REP(k, m + 1) {
                add(tmp[j - 1][k][0], tmp[j][k][0]);
                add(tmp[j - 1][k][1], tmp[j][k][1]);
                if (s[j] == 'L' && k != 0) {
                    add(tmp[j - 1][k - 1][0], tmp[j][k][0]);
                    add(tmp[j - 1][k - 1][1], tmp[j][k][0]);
                    sub(tmp[prev[j]][k][0], tmp[j][k][0]);
                } else if (s[j] == 'P') {
                    add(tmp[j - 1][k + 1][0], tmp[j][k][1]);
                    add(tmp[j - 1][k + 1][1], tmp[j][k][1]);
                    sub(tmp[prev[j]][k][1], tmp[j][k][1]);
                }
            }
        }

        REP(j, m + 2) {
            mul[i][j][0] = tmp[0][j][0];
            mul[i][j][1] = tmp[0][j][1];
            dp[i][j][0] = dpt[m][j][0];
            dp[i][j][1] = dpt[m][j][1];
        }
    }

    REP(i, n) {
        REP(j, n) {
            int ans = 0;
            REP(k, MAXN) {
                if (k == 0) {
                    add(ans, ((LL) (dp[i][k][0] + 1) * (LL) (mul[j][k][0]) + 
                        (LL) (dp[i][k][1]) * (LL) (mul[j][k][1])) % mod);
                }
                else {
                    add(ans, ((LL) (dp[i][k][0]) * (LL) (mul[j][k][0]) + 
                        (LL) (dp[i][k][1]) * (LL) (mul[j][k][1])) % mod);
                }
            }
            cout << ans << ' ';
        }
        cout << '\n';
    }

    return 0;
}