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
#include <bits/stdc++.h>

using namespace std;
using ull = unsigned long long;

ull modul = 1000 * 1000 * 1000 + 7;

vector<string> words;
vector<map<pair<int, int>, ull>> memos;

vector<int> nextc(string &s, char c) {
    int n = s.size();
    vector<int> ans(n + 1);
    ans[n] = n;
    for (int i = n - 1; i >= 0; i--) {
        ans[i] = s[i] == c ? i : ans[i + 1];
    }
    return ans;
}

ull go(string &s, map<pair<int, int>, ull> &memo, vector<int> &nextop, vector<int> &nextcl, int ix, int opencnt, int offset) {
    auto it = memo.find({ix + offset, opencnt});
    // cout << s << endl;
    // cout << "{" << ix << "," << opencnt << "}\n";
    if (it != memo.end()) {
        return it->second;
    }
    
    ull ans = opencnt == 0;

    int n = s.size();
    if (ix + 1 < n) {
        int i = nextop[ix + 1]; 
        if (i < n) {
            ans += go(s, memo, nextop, nextcl, i + offset, opencnt + 1, offset);
            if (ans >= modul) ans -= modul;
        }
        if (opencnt > 0) {
            i = nextcl[ix + 1];
            if (i < n) {
                ans += go(s, memo, nextop, nextcl, i + offset, opencnt - 1, offset);
                if (ans >= modul) ans -= modul;
            }
        }
    }
    memo[{ix, opencnt}] = ans;
    return ans;
}

void solve() {
    int n;
    cin >> n;
    words.reserve(n);
    memos.reserve(n);
    for (int i = 0; i < n; i++) {
        words.emplace_back();
        cin >> words.back();
        memos.emplace_back();
        // go(words.back(), memos.back(), -1, 0);
    }    
    for (int fh = 0; fh < n; fh++) {
        for (int sh = 0; sh < n; sh++) {
            string word = words[fh] + words[sh];
            map<pair<int, int>, ull> memo;
            vector<int> nextop = nextc(word, 'L'), nextcl = nextc(word, 'P');
            cout << (go(word, memo, nextop, nextcl, -1, 0, 0) + modul - 1) % modul << ' ';
        }
        cout << '\n';
    }

    // for (int sh = 0; sh < n; sh++) {
    //     map<pair<int, int>, ull> memo;
    //     go(words[sh], memo, -1, 0, 0);
    //     for (int fh = 0; fh < n; fh++) {
    //         map<pair<int, int>, ull> new_memo(memo);
    //         ull ans = 0;
    //         int maxcnt = words[sh].size();
    //         for (int opencnt = -maxcnt; opencnt <= maxcnt; opencnt++) {
    //             ans += go(words[sh], new_memo, -1, opencnt, maxcnt);
    //         }
    //         cout << ans % modul << ' ';
    //     }
    //     cout << '\n';
    // }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

// #ifdef LOCAL
//     int t; cin >> t; while (t--)
// #endif

    solve();

    cout.flush();
}