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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <cstdio>
#include <cstring>

#define DBG(X)

char t[1202][1202];

char s[1202];


int dp[1202][1202];

const int MOD = 1000000007;

int main()
{
  
  int n;
  scanf("%d", &n);
  
  for (int i = 0; i < n; i++)
  {
    scanf("%s", t[i]);
  }
  
  
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      
      
      int lsize = strlen(t[i]);
      int rsize = strlen(t[j]);
      for (int k = 0; k < lsize; k++)
      {
        s[k] = t[i][k];
      }
      for (int k = 0; k < rsize; k++)
      {
        s[lsize + k] = t[j][k];
      }

      for (int k = 0; k <= lsize + rsize; k++)
      {
        for (int l = 0; l <= lsize + rsize; l++)
        {
          dp[k][l] = 0;
        }
      }

      
      DBG(printf("%s\n", s);)
      
      int first = -1;
      for (int k = 0; k < lsize + rsize; k++)
      {
        if (first == - 1 && s[k] == 'P') continue;
        
        if (first == -1)
        {
          dp[1][k] = 1;
          first = k;
          continue;
        }

        if (s[k] == 'L')
        {
          int d = k - 1;
          
          if (s[d] == 'L')
          {
            dp[0][k] = 0;
            for (int l = 0; l + 1 < lsize + rsize; l++)
            {
              dp[l + 1][k] = dp[l][d];
            }
          }
          else
          {
            dp[0][k] = 0;
            
            for (int l = 0; l < lsize + rsize; l++)
            {
              int sum = 0;
              d = k - 1;
              while (d >= first && s[d] == 'P')
              {
                sum += dp[l][d];
                sum %= MOD;
                d--;
              }
              if (d >= first)
              {
                sum += dp[l][d];
                sum %= MOD;
              }
              dp[l + 1][k] = sum;
            }
          }
        }
        else
        {
          int d = k - 1;
          
          if (s[d] == 'P')
          {
            for (int l = 0; l + 1 < lsize + rsize; l++)
            {
              dp[l][k] = dp[l + 1][d];
            }
          }
          else
          {
            DBG(printf(" k = %d\n", k);)
            for (int l = 0; l + 1 < lsize + rsize; l++)
            {
              int sum = 0;
              d = k - 1;
              while (d >= first && s[d] == 'L')
              {
                sum += dp[l + 1][d];
                sum %= MOD;
                d--;
              }
              if (d >= first)
              {
                sum += dp[l + 1][d];
                sum %= MOD;
              }
              DBG(printf("sum = %d, k = %d, l = %d\n", sum, k, l);)
              dp[l][k] = sum;
            }
          }
        }
        
        DBG(printf("k = %d\n", k);
        for  (int l = 0; l < lsize + rsize; l++)
        {
          printf("%d\n", dp[l][k]);
        })
        
      }
      
      DBG(for (int k = 0; k <= lsize + rsize; k++)
      {
        for  (int l = 0; l <= lsize + rsize; l++)
        {
          printf("%d ", dp[k][l]);
        }
        printf("\n");
      })
      
      int sum = 0;
      for (int k = 0; k <= lsize + rsize; k++)
      {
        sum += dp[0][k];
        sum %= MOD;
      }
      printf("%d ", sum);
    }
    printf("\n");
  }
  
  
  
  return 0;
}