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
#include <iostream>
#include <map>
#include <vector>

const int MAX = 601;
const int32_t MOD = 1000000007;

std::string s;
// std::map<std::tuple<int16_t,int16_t,int16_t>, int32_t> D;
// int32_t D[2*MAX][MAX][MAX];

std::vector<int32_t> D;

int pP[2*MAX];
int pL[2*MAX];

int cc=0;

int KK, LL, PP;
int index(int K, int L, int P) {
    return PP*LL*K+PP*L+P;
}

int32_t Solve(int K, int L, int P) {
    if (K<=-1) return 0;
    if (L==0 && P==0) return 1;
    if (P+L > K) return 0;
    if (L < P) return 0;
    if (K < 0) return 0;
    if (L < 0) return 0;
    if (P < 0) return 0;
    // // auto it = D.find({K,L,P});
    // // if (it != D.end()) return it->second;
    // int32_t sum = Solve(pP[K]-1, L, P-1) + Solve(pL[K]-1, L-1, P);
    // // std::clog << " ## " << K << " " << pP[K]-1 << " / " << pL[K]-1 << std::endl;
    // sum %= MOD;
    // D[{K,L,P}] = sum;
    
    // ++cc;
    // if (cc % 100000 == 0) std::clog << D.size() << std::endl;
    // // std::clog << K << " " << L << " " << P << " = " << sum << std::endl;
    // return sum;
    return D[index(K,L,P)];//D[K][L][P];
}

void Solve2(int K, int L, int P) {
    for (int k=0;k<=K;++k) {
        for (int p=0;p<=P;++p) {
            for (int l=p;p+l<=k && l<=L;++l) {
                //D[k][l][p] = (Solve(pP[k]-1, l, p-1) + Solve(pL[k]-1, l-1, p))%MOD;
                D[index(k,l,p)] = (Solve(pP[k]-1, l, p-1) + Solve(pL[k]-1, l-1, p))%MOD;
                //(D[pP[k]-1][l][p-1] + D[pL[k]-1][l-1][p]) % MOD;
            }
        }
    }
}

std::string S[MAX];
int n;

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin >> n;
    for (int i=0;i<n;++i) std::cin >> S[i];

    LL = 0;
    for (int i=0;i<n;++i) {
        for (int j=0;j<n;++j) {
            LL = std::max(LL, int(S[i].length()+S[j].length()));
        }
    }
    KK = LL+1;
    ++LL;
    LL/=2;
    ++LL;
    PP = LL;
    D.resize(KK*LL*PP, 0);


    for (int i=0;i<n;++i) {
        for (int j=0;j<n;++j) {
            // std::clog << i << " " << j << std::endl;
            s = S[i] +S[j];
            // pP[0] = 0;
            // pL[0] = 0;
            for (int k=1;k<=s.length();++k) {
                pP[k] = (s[k-1] == 'P' ? k : pP[k-1]);
                pL[k] = (s[k-1] == 'L' ? k : pL[k-1]);
            }
            // D.clear();
            Solve2(s.length(), s.length()/2, s.length()/2);
            // for (int k=0;k<=s.length();++k) std::clog << " :: " << pP[k] << " / " << pL[k] << std::endl;
            int32_t sum = 0;
            for (int k=2;k<=s.length();k+=2) {
                sum += Solve(s.length(), k/2, k/2);
                // std::clog << k << " :: " << Solve(s.length(), k/2, k) << std::endl;
                sum %= MOD;
            }
            std::cout << sum << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}