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

using namespace std;


long long PRIME = 1e9+7;

long long solve(string s){
    // cout<<s<< " ";
    int begin_p_counter = 0;
    while(s[begin_p_counter] == 'P')
        begin_p_counter++;

    s = s.substr(begin_p_counter);

    int l_counter = 0;
    for(int i = 0; i < s.size(); i++)
        if(s[i] == 'L')
            l_counter++;
        
    vector<long long> prev_diffs;
    vector<long long> prev_L;
    vector<long long> prev_P;

    for(int i = 0; i <= l_counter; i++){
        prev_diffs.push_back(0);
        prev_L.push_back(0);
        prev_P.push_back(0);
    }

    int max_height = s.size() - l_counter;
    int current_max_height = 0;
    bool first_L = false;

    long long sum = 0;
    
    for(int i = 0; i < s.size(); i++){
        // cout << s[i] << endl;

        if(s[i] == 'L'){
            if(!first_L){
                first_L = true;
                current_max_height++;
                prev_L[1] = 1;
                prev_diffs[1] = 1;
                continue;
            }
            if(s[i-1] == 'L'){
                for(int j = current_max_height+1; j > 0; j--){
                    prev_diffs[j] = (prev_diffs[j] + prev_L[j-1])%PRIME;
                    prev_L[j] = prev_L[j-1];
                }
            }
            else {
                for(int j = current_max_height+1; j > 0; j--){
                    prev_L[j] = (prev_L[j-1] + prev_diffs[j-1])%PRIME;
                    prev_diffs[j] = prev_L[j];
                }
                prev_diffs[0] = 0;
                prev_L[0] = 0;
            }
            current_max_height = min(current_max_height+1, max_height);
        }
        else {
            if(s[i-1] == 'P'){
                for(int j = 0; j < current_max_height; j++){
                    prev_diffs[j] = (prev_diffs[j] + prev_P[j+1])%PRIME;
                    prev_P[j] = prev_P[j+1];
                }
            }
            else {
                for(int j = 0; j < current_max_height; j++){
                    prev_P[j] = (prev_P[j+1] + prev_diffs[j+1])%PRIME;
                    prev_diffs[j] = prev_P[j];
                }
                prev_diffs[current_max_height] = 0;
            }
            max_height--;
            current_max_height = min(current_max_height, max_height);
            // cout<<prev_P[0]<<endl;
            sum = (sum + prev_P[0])%PRIME;
        }

        // cout << s[i] << endl;
        // cout << "DIFFS: ";
        // for(int j = 0; j <= current_max_height; j++)
        //     cout << prev_diffs[j] << " ";
        // cout << endl;
        // cout << "L:     ";
        // for(int j = 0; j <= current_max_height; j++)
        //     cout << prev_L[j] << " ";
        // cout << endl;
        // cout << "P:     ";
        // for(int j = 0; j <= current_max_height; j++)
        //     cout << prev_P[j] << " ";
        // cout << endl << "=======================" << endl;
    }

    return sum;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    int n;
    cin >> n;

    vector<string> strings;

    for(int i = 0; i < n; i++){
        string input;
        cin >> input;
        strings.push_back(input);
    }

    for(int i = 0; i < n; i++){
        // cout<<i<<endl;
        for(int j = 0; j < n; j++){
            cout << solve(strings[i] + strings[j]) << " ";
            // cout<<solve("LLPP");
        }
        cout << endl;
    }
}