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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <cstdio>
#include <string>
#include <vector>
using namespace std;

vector<string> drybles;
int n;
const int modulo = 1000*1000*1000+7;

struct disn {
    int L = 0;
    int P = 0;
};

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

    for(int i = 0; i < n; ++i) {
        char tmp[601];
        scanf("%s", tmp);
        drybles.emplace_back(tmp);
    }

//    for(int i = 0; i < n; ++i) {
//        printf("%zu: %s\n", drybles[i].length(), drybles[i].c_str());
//    }

    for(int i = 0; i < n; ++i) {
        int startidx = 0;
        int maxldiff = 0;
        int dryblen = drybles[i].length();
        while(startidx < dryblen && drybles[i][startidx] == 'P') {
            startidx += 1;
        }

        disn distinct[2][602];

//        for (int j = 0; j < 601; ++j) {
//            for (int k = 0; k < 601; ++k) {
//                if (distinct[0][j].L != 0 || distinct[0][j].P != 0) {
//                    printf("DUPAA NIE MA ZER WTFFFFFFFFFFFF");
//                }
//            }
//        }

        distinct[startidx%2][0].P = 1; // empty string. Will delete at end or sth
        // printf("%d SEQ STARTIDX: %d\n", i, startidx);
        // drybles[i][startidx] is the first 'L' of the sequence
        int realidx = startidx + 1;
        if (startidx != dryblen) {
            // there is an L
            distinct[startidx%2][1].L = 1;
            maxldiff = 1;
        }

        while (realidx < dryblen) {
            int dist_tab = realidx%2;
            int prev_tab = 1-dist_tab;

            if (drybles[i][realidx] == 'L') {
                distinct[dist_tab][0] = distinct[prev_tab][0];
                for (int j = 0; j <= maxldiff; ++j) {
                    distinct[dist_tab][j+1].P = distinct[prev_tab][j+1].P;
                    distinct[dist_tab][j+1].L = (distinct[prev_tab][j].P + distinct[prev_tab][j].L) % modulo;
                }
                maxldiff += 1;
            } else {
                for (int j = 1; j <= maxldiff; ++j) {
                    distinct[dist_tab][j-1].L = distinct[prev_tab][j-1].L;
                    distinct[dist_tab][j-1].P = (distinct[prev_tab][j].P + distinct[prev_tab][j].L) % modulo;
                }
                // handle empty string
                distinct[dist_tab][0].P += 1;
                distinct[dist_tab][maxldiff] = distinct[prev_tab][maxldiff];
            }
            realidx += 1;

//            printf("%d BASE TAB AFTER STEP %d:\n", i, realidx);
//            for(int j = 0; j <= maxldiff; ++j) {
//                printf("%d: %lld %lld\n", j, distinct[dist_tab][j].L, distinct[dist_tab][j].P);
//            }
        }

        int prev_tab_base = 1-realidx%2;
        disn base_tab[602];
        for (int j = 0; j < 602; ++j) {
            base_tab[j] = distinct[prev_tab_base][j];
        }
//        printf("%d BASE TAB:\n", i);
//        for (int j = 0; j < 602; ++j) {
//            if (j <= maxldiff) {
//                printf("%d: %lld %lld\n", j, base_tab[j].L, base_tab[j].P);
//            }
//        }


        for (int dk = 0; dk < n; ++dk) {
            for (int j = 0; j < 602; ++j) {
                distinct[0][j] = disn{0,0};
                distinct[1][j] = base_tab[j];
            }
            int sec_dryblen = drybles[dk].length();
            int sec_maxldiff = maxldiff;

            for (int sec_idx = 0; sec_idx < sec_dryblen; sec_idx++) {
                // max_zeroable_ldiff is max number of remaining Ps
                int max_zeroable_ldiff = sec_dryblen - sec_idx;
                int actual_maxldiff = min(max_zeroable_ldiff, sec_maxldiff);
                int dist_tab = sec_idx%2;
                int prev_tab = 1-dist_tab;

                if (drybles[dk][sec_idx] == 'L') {
                    distinct[dist_tab][0] = distinct[prev_tab][0];
                    for (int j = 0; j <= actual_maxldiff; ++j) {
                        distinct[dist_tab][j+1].P = distinct[prev_tab][j+1].P;
                        distinct[dist_tab][j+1].L = (distinct[prev_tab][j].P + distinct[prev_tab][j].L) % modulo;
                    }
                    if (sec_maxldiff < 600) {
                        sec_maxldiff += 1;
                    }
                } else {
                    for (int j = 1; j <= actual_maxldiff; ++j) {
                        distinct[dist_tab][j-1].L = distinct[prev_tab][j-1].L;
                        distinct[dist_tab][j-1].P = (distinct[prev_tab][j].P + distinct[prev_tab][j].L) % modulo;
                    }
                    // handle empty string
                    distinct[dist_tab][0].P += 1;
                    distinct[dist_tab][actual_maxldiff] = distinct[prev_tab][actual_maxldiff];
                }
            }

            printf("%d ", ((distinct[1-(sec_dryblen%2)][0].P - 1 + modulo)%modulo));
        }
        printf("\n");
    }
    return 0;
}