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
#include<cstdio>
#include<algorithm>
#include<iostream>

#define S 607
using namespace std;
typedef long long ll;
int mod = 1000000007;

ll F[S][S][2];
ll B[S][S][2];

int T[S][S][2];
int T2[S][S][2];
ll biases[S];


int main(void){
    int n;
    scanf("%d",&n);

    for(int i = 1; i <= n;i++){
        string s;

        cin >> s;

        for(int j = 0; j <= 600;j++)
            T[0][j][0] = T[0][j][1] = 0;
        for(int j = 1; j <= s.size();j++){
            for(int k = 0; k <= j;k++){
                T[j][k][0] = T[j-1][k][0];
                T[j][k][1] = T[j-1][k][1];
                if(s[j-1] == 'L' && k != 0){
                    T[j][k][0] = T[j-1][k-1][0] + T[j-1][k-1][1];
                    if(k == 1)
                        T[j][k][0]++;
                }else if(s[j-1] == 'P'){
                    T[j][k][1] = T[j-1][k+1][0] + T[j-1][k+1][1];
                }
                while(T[j][k][0] >= mod)
                    T[j][k][0] -= mod;
                while(T[j][k][1] >= mod)
                    T[j][k][1] -= mod;
            }
        }
        for(int j = 0; j <= 600;j++){
            F[i][j][0] = T[s.size()][j][0];
            F[i][j][1] = T[s.size()][j][1];
        }

        for(int j = 0 ; j <= 600;j++){
            T2[s.size()][j][0] = T2[s.size()][j][1] = 0;
            T2[0][j][0] = T2[0][j][1] = 0;
        }
        T2[s.size()][0][1] = 1;
        int bias = 0;
        for(int j = s.size(); j >= 1;j--){
            for(int k = 0; k <= (s.size()-j+3);k++)
                T2[j-1][k][0] = T2[j-1][k][1] = 0;
            if(s[j-1] == 'L'){
                for(int k = 0; k <= (s.size()-j+1);k++){
                    T2[j-1][k][1] += T2[j][k][1];
                    if(k != 0){
                        T2[j-1][k-1][0] += T2[j][k][0];
                        T2[j-1][k-1][1] += T2[j][k][0];
                    }
                    if(k == 1)
                        bias += T2[j][k][0];
                }
            }else{
                for(int k = 0; k <= (s.size()-j+1);k++){
                    T2[j-1][k][0] += T2[j][k][0];
                    T2[j-1][k+1][0] += T2[j][k][1];
                    T2[j-1][k+1][1] += T2[j][k][1];
                }
            }
            for(int k = 0; k <= (s.size()-j+1);k++){
                while(T2[j-1][k][0] >= mod)
                    T2[j-1][k][0] -= mod;
                while(T2[j-1][k][1] >= mod)
                    T2[j-1][k][1] -= mod;
            }
            while(bias >= mod)
                bias -= mod;
        }

        for(int j = 0; j <= 600;j++){
            B[i][j][0] = T2[0][j][0];
            B[i][j][1] = T2[0][j][1];
        }
        biases[i] = bias;
    }
    for(int i = 1; i <= n;i++){
        for(int j = 1; j <= n;j++){
            ll p = 0;
            for(int k = 0; k <= 600;k++){
                p += F[i][k][0] * B[j][k][0] + F[i][k][1] * B[j][k][1];
                p %= mod;
            }
            p += biases[j];
            p %= mod;
            printf("%lld ",p);
        }
        printf("\n");
    }

    return 0;
}


/*
2 2 1 8
17 6 5 32
1 2 0 7
22 16 10 66
*/