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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include <bits/stdc++.h>
#define dbg(x) " [" << #x << ": " << (x) << "] "
using namespace std;
template<typename A, typename B>
ostream& operator<<(ostream& out, const pair<A,B>& p) {
    return out << "(" << p.first << ", " << p.second << ")";
}
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& c) {
    out << "{";
    for(auto it = c.begin(); it != c.end(); it++) {
        if(it != c.begin()) out << ", ";
        out << *it;
    }
    return out << "}";
}
const int mod = 1e9 + 7;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int nn;
    cin >> nn;
    vector<string> ss(nn);
    int mx_size = 0;
    for(int i = 0; i < nn; i++) {
        cin >> ss[i];
        mx_size = max(mx_size, (int)ss[i].length());
    }
    for(int ii = 0; ii < nn; ii++) {
        string s = ss[ii];
        int n = s.length();
        vector<vector<int>> dp(n + mx_size);
        for(int i = 0; i < dp.size(); i++) {
            dp[i].resize(min(i + 2, (int)dp.size() / 2 + 2));
        }
        int i = 0;
        while(i < n && s[i] == 'P') i++;
        bool ok = i < n;
        if(ok) {
            dp[i][1] = 1;
            i++;
        }
        int f_l = i - 1;
        int f_p = 0;
        int lst_l = i - 1;
        int lst_p = -1;
        int ans = 0;
        if(ok) {
            while(i < n) {
                if(s[i] == 'L') {
                    for(int j = 0; j + 1 < min(dp[lst_l].size() + 1, dp[i].size()); j++) {
                        dp[i][j + 1] = dp[lst_l][j];
                    }
                    if(s[i - 1] == 'P') {
                        for(int k = f_p; k <= lst_p; k++) {
                            for(int j = 1; j < min(dp[k].size() + 1, dp[i].size()); j++) {
                                dp[i][j] = (dp[i][j] + dp[k][j - 1]) % mod;
                            }
                        }
                    }
                    lst_l = i;
                    if(s[i - 1] == 'P') f_l = i;
                } else {
                    if(lst_p != -1) {
                        for(int j = 0; j + 1 < dp[lst_p].size(); j++) {
                            dp[i][j] = dp[lst_p][j + 1];
                        }
                    }
                    if(s[i - 1] == 'L') {
                        for(int k = f_l; k <= lst_l; k++) {
                            for(int j = 0; j + 1 < dp[k].size(); j++) {
                                dp[i][j] = (dp[i][j] + dp[k][j + 1]) % mod;
                            }
                        }
                    }
                    lst_p = i;
                    if(s[i - 1] == 'L') f_p = i;
                }
                ans = (ans + dp[i][0]) % mod;
                i++;
            }
        }
        int my_ans = ans;
        int my_lst_l = lst_l;
        int my_lst_p = lst_p;
        int my_f_l = f_l;
        int my_f_p = f_p;
        for(int jj = 0; jj < nn; jj++) {
            ans = my_ans;
            string s2 = s + ss[jj];
            n = s2.length();
            i = s.length();
            f_l = my_f_l;
            f_p = my_f_p;
            lst_l = my_lst_l;
            lst_p = my_lst_p;
            if(!ok) {
                while(i < n && s2[i] == 'P') i++;
                if(i == n) {
                    if(jj) cout << " ";
                    cout << ans;
                    continue;
                }
                dp[i][0] = 0;
                dp[i][1] = 1;
                for(int j = 2; j < dp[i].size(); j++) dp[i][j] = 0;
                i++;
                f_l = i - 1;
                lst_l = i - 1;
            }
            while(i < n) {
                if(s2[i] == 'L') {
                    dp[i][0] = 0;
                    for(int j = 0; j + 1 < min(dp[lst_l].size() + 1, dp[i].size()); j++) {
                        dp[i][j + 1] = dp[lst_l][j];
                    }
                    for(int j = dp[lst_l].size() + 1; j < dp[i].size(); j++) {
                        dp[i][j] = 0;
                    }
                    if(s2[i - 1] == 'P') {
                        for(int k = f_p; k <= lst_p; k++) {
                            for(int j = 1; j < min(dp[k].size() + 1, dp[i].size()); j++) {
                                dp[i][j] = (dp[i][j] + dp[k][j - 1]) % mod;
                            }
                        }
                    }
                    lst_l = i;
                    if(s2[i - 1] == 'P') f_l = i;
                } else {
                    if(lst_p != -1) {
                        for(int j = 0; j + 1 < dp[lst_p].size(); j++) {
                            dp[i][j] = dp[lst_p][j + 1];
                        }
                        for(int j = (int)dp[lst_p].size() - 1; j < dp[i].size(); j++) {
                            dp[i][j] = 0;
                        }
                    } else {
                        for(int j = 0; j < dp[i].size(); j++) dp[i][j] = 0;
                    }
                    if(s2[i - 1] == 'L') {
                        for(int k = f_l; k <= lst_l; k++) {
                            for(int j = 0; j + 1 < dp[k].size(); j++) {
                                dp[i][j] = (dp[i][j] + dp[k][j + 1]) % mod;
                            }
                        }
                    }
                    lst_p = i;
                    if(s2[i - 1] == 'L') f_p = i;
                }
                ans = (ans + dp[i][0]) % mod;
                i++;
            }
            if(jj) cout << " ";
            cout << ans;
        }
        cout << '\n';
    }
    return 0;
}