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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int mod = 1e9 + 7;

int main(){
    int k; cin >> k;
    vector<string> A(k);
    for(int i=0;i<k;i++)cin >> A[i];
    for(int p=0;p<k;p++){
        for(int q=0;q<k;q++){
            string a = A[p] + A[q];
            int n=a.size();
            vector<int> G(n,0), D(n,0);
            G[0] = 1;
            for(int i=0;i<n;i++){
                if(a[i] == 'L'){
                    for(int j=n-1;j>0;j--){
                    // cout << j <<'\n';
                    G[j] = G[j-1];
                    D[j]+= G[j-1];
                    G[j]%=mod;
                    D[j]%=mod;
                }
                G[0] = 0;
                }
                else{
                    for(int j=0;j<n-1;j++){
                        G[j] += D[j+1];
                        if(j>0)D[j] = D[j+1];
                        else D[j] += D[j+1];
                        G[j]%=mod;
                        D[j]%=mod;
                    }
                }
            }
            cout << D[0] << ' ';
        }
        cout << '\n';
    }
}