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

const unsigned MOD = 1000000007;

char dryb[601][601];
unsigned DPB[1202][2];
unsigned DPL[1202][2];
unsigned DPP[1202][2];
int cur;
int prev;

unsigned DPB_copy[1202][2];
unsigned DPL_copy[1202][2];
unsigned DPP_copy[1202][2];
int cur_copy;
int prev_copy;

void backup() {
    memcpy(DPB_copy, DPB, sizeof(DPB));
    memcpy(DPL_copy, DPL, sizeof(DPL));
    memcpy(DPP_copy, DPP, sizeof(DPP));
    cur_copy = cur;
    prev_copy = prev;
}

void restore() {
    memcpy(DPB, DPB_copy, sizeof(DPB));
    memcpy(DPL, DPL_copy, sizeof(DPL));
    memcpy(DPP, DPP_copy, sizeof(DPP));
    cur = cur_copy;
    prev = prev_copy;
}

void clear() {
    memset(DPB, 0, sizeof(DPB));
    memset(DPL, 0, sizeof(DPL));
    memset(DPP, 0, sizeof(DPP));

    cur = 1;
    prev = 0;
}

int calc(const char *str, int begin) {
    int L = strlen(str);

    for (int i=begin; i<L; ++i) {
        for (int k=0; k<=i+1 && (k<=L-i+5 || begin==0); k++) {
            if (str[i]=='L') {
                DPL[k][cur] = (k-1>=0?DPB[k-1][prev]:0);
                DPP[k][cur] = DPP[k][prev];
                DPB[k][cur] = ((k-1>=0?DPB[k-1][prev]:0) + DPP[k][prev]) % MOD;
                if (k==1) {
                    DPL[k][cur]++;
                    DPB[k][cur]++;
                    DPL[k][cur] %= MOD;
                    DPB[k][cur] %= MOD;
                }
            } else {
                DPL[k][cur] = DPL[k][prev];
                DPP[k][cur] = DPB[k+1][prev];
                DPB[k][cur] = (DPL[k][prev] + DPB[k+1][prev]) % MOD;
            }
        }

        cur = !cur;
        prev = !prev;
    }

    return DPB[0][prev];
}

int main() {
    int N;

    scanf("%d\n", &N);
    for (int i=0; i<N; ++i) {
        scanf("%s\n", dryb[i]);
    }

    for (int i=0; i<N; ++i) {
        clear();
        calc(dryb[i], 0);
        backup();

        for (int j=0; j<N; ++j) {
            char sum[1201];
            memcpy(sum, dryb[i], strlen(dryb[i]));
            memcpy(sum+strlen(dryb[i]), dryb[j], strlen(dryb[j])+1);
            restore();
            printf("%d ", calc(sum, strlen(dryb[i])));
        }
        printf("\n");
    }

    return 0;
}