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
#include <cstdio>
#include <cstdlib>
#include <cstdint>

#include <vector>
#include <string>
#include <utility>

static const uint64_t MODULO = 1000 * 1000 * 1000 + 7;

std::vector<std::string> load_data() {
    int n;
    scanf("%d", &n);

    std::vector<std::string> ret;
    ret.reserve(n);
    
    char tmp[1024];

    for (int i = 0; i < n; i++) {
        scanf("%s", tmp);
        ret.emplace_back(tmp);
    }

    return ret;
}

int solve_for_sequence(const char* ptr, const int len) {
    const int height = len + 1;
    const int width = len / 2 + 3;

    std::vector<uint64_t> mat(width * height, 0);
    mat[0] = 1;

    uint64_t ret = 0;

    int next_l = -1;
    int next_r = -1;

    auto modadd = [] (uint64_t& a, uint64_t b) { a = (a + b) % MODULO; };

    for (int i = 0; i < len; i++) {
        if (next_l < i) {
            do {
                next_l++;
            } while (next_l < len && ptr[next_l] != 'L');
        }

        if (next_r < i) {
            do {
                next_r++;
            } while (next_r < len && ptr[next_r] != 'P');
        }

        if (next_l < len) {
            for (int j = 0; j < width - 1; j++) {
                modadd(mat[width * (next_l + 1) + j + 1], mat[width * i + j]);
            }
        }

        if (next_r < len) {
            for (int j = 1; j < width; j++) {
                modadd(mat[width * (next_r + 1) + j - 1], mat[width * i + j]);
            }
        }
    }

    // Don't count empty dribbling
    for (int i = 1; i <= len; i++) {
        ret = (ret + mat[width * i]) % MODULO;
    }

    return (int)ret;
}

int main() {
    auto data = load_data();

    for (const auto& left : data) {
        for (const auto& right : data) {
            std::string combined = left + right;
            int solution = solve_for_sequence(combined.data(), combined.size());
            printf("%d ", solution);
        }
        putchar('\n');
    }

    return 0;
}