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

#define MOD 1000000007
class Sequence {
    int mem[1448][1448] = {{0}};
    int NL[1448], NP[1448], len;
    Sequence *next = nullptr;
  public:
    Sequence(string S, Sequence *next) {
        this->next = next;
        len = S.length();
        int CP = len, CL = len;
        NL[len]=NP[len]=len;
        for (int j = len - 1; j>=0; j--) {
            if (S[j] == 'P') CP = j; else CL=j;
            NL[j] = CL; NP[j] = CP;
        }
    }
    int run(int last, int cnt) {
        // cout << last << " " << cnt << endl;
        if (last >= 0 && mem[last][cnt] > 0) return mem[last][cnt]-1;
        int ret = cnt ? 0 : 1;
        int nidx = NL[last + 1];
        if (nidx < len) { 
            ret = (ret + run(nidx, cnt + 1)) % MOD;
        } else if (next != nullptr) {
            nidx = next->NL[0];
            if (nidx < next->len) ret = (ret + next->run(nidx, cnt + 1)) % MOD;
        }

        if (cnt > 0) {
            nidx = NP[last + 1];
            if (nidx < len) {
                ret = (ret + run(nidx, cnt - 1)) % MOD;
            } else if (next != nullptr) {
                nidx = next->NP[0];
                if (nidx < next->len) ret = (ret + next->run(nidx, cnt - 1)) % MOD;
            }
        }
        if (last>=0) mem[last][cnt] = ret + 1;
        return ret;
    }
};

int main() {
    string SS[1000];
    Sequence *ST[1000];
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> SS[i];
        ST[i] = new Sequence(SS[i], nullptr);
    }
    Sequence *foo = new Sequence(SS[0], ST[0]);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            Sequence *foo = new Sequence(SS[i], ST[j]);
            cout << (foo->run(-1,0)-1);
            if (j < N -1) cout << " ";
            delete foo;
        }
        cout << endl;
    }
    return 0;
}