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

#define ll long long
#define fors(u, n, s) for(ll u=(s); u < (n); u++)
#define foru(u, n) fors(u, n, 0)
#define ir(a, b, x) (((a) <= (x)) && ((x) <= (b)))
#define vec vector
#define pb push_back

using namespace std;

#define N 605
#define M 1000000007
int n;

vec<bool> naw[N];

ll dp1[N][N][2]; /// number of ways to get here, [NR. NAW][H][must_take]
ll dp2[N][N][2]; /// number of ways to finish this, [NR. NAW][H][next]

ll dp[N][2]; ///[H]
ll alt_dp[N][2]; ///[H]

void calc_dp1(int x){ /// number of ways to get here, [NR. NAW][H][must_take]
    foru(i, N) dp[i][0] = 0;
    foru(i, N) dp[i][1] = 0;
    dp[0][1]=1;
    dp[0][0]=1;
    foru(i, naw[x].size()){///i is the naw we filling

        foru(j, N) foru(b, 2){
            alt_dp[j][b]=0;

            int new_j = j-2*naw[x][i]+1;
            if(0<=new_j && new_j<N) alt_dp[j][b] += dp[new_j][naw[x][i]];

            if(naw[x][i] != b) alt_dp[j][b] += dp[j][b];

            alt_dp[j][b]=alt_dp[j][b]%M;
        }

        swap(alt_dp, dp);
    }
    foru(i, N) foru(b, 2) dp1[x][i][b]=dp[i][b];
}

/*int dp1(int h, int x, bool must_take){ ///number of ways to get here
    if(x==-1) return (h==0);
    if(h<0) return 0;

    int ans=0;

    ///case include
    ans += dp1(h-2*naw1[x]+1, x-1, naw1[x]);

    ///case exclude
    if(naw1[x]!=must_take){
        ans += dp1(h, x-1, must_take);
    }
    return ans;
}*/

 void calc_dp2(int x){ /// number of ways of finishing this, [NR. NAW][H][next]
    foru(i, N) dp[i][0] = 0;
    foru(i, N) dp[i][1] = 0;
    for(int i=naw[x].size()-1; i>=0; i--){///i is the naw we filling

        foru(j, N) foru(b, 2){
            if(naw[x][i]==b){
                alt_dp[j][b]=(j+2*b-1==0);
                if(ir(0, N-1, j+2*b-1)) alt_dp[j][b]+= dp[j+2*b-1][0] + dp[j+2*b-1][1];
            }else{
                alt_dp[j][b]=dp[j][b];
            }
            alt_dp[j][b]=alt_dp[j][b]%M;
        }

        swap(alt_dp, dp);
    }
    foru(i, N) foru(b, 2) dp2[x][i][b]=dp[i][b];
}

/*int dp2(int h, int x, bool next){ ///number of ways of finishing this
    if(h<0) return 0;
    if(x==n2) return 0;
    if(naw2[x]==next){
        h += 2*next-1;
        return dp2(h, x+1, 0) + dp2(h, x+1, 1) + (h==0);
    }else{
        return dp2(h, x+1, next);
    }
}*/

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    foru(i, n){
        string str; cin >> str;
        for(auto c : str) naw[i].pb(c=='L');
    }

    foru(i, n) {calc_dp1(i); calc_dp2(i);}

    foru(i, n) {
        foru(j, n){
            ll ans = 0;
            foru(h, N) foru(b, 2) {ans += dp1[i][h][b]*dp2[j][h][b]; ans=ans%M;}
            ans += dp2[i][0][1];
            ans=ans%M;
            cout << ans << " ";
        }
        cout << endl;
    }

    return 0;
}