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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, l, r) for (auto i = (l); i <= (r); ++i)
#define REP(i, n) FOR (i, 0, (n)-1)
#define ssize(x) int(x.size())
template<class A, class B>
auto&
operator<<(ostream& o, pair<A, B> p)
{
  return o << "(" << p.first << ", " << p.second << ")";
}
template<class T>
auto
operator<<(ostream& o, T x) -> decltype(x.end(), o)
{
  o << "{";
  int i = 0;
  for (auto e : x) o << (", ") + 2 * !i++ << e;
  return o << "}";
}
#ifdef DEBUG
#define debug(x...)                                                            \
  cerr << "[" #x "]: ", [](auto... $) { ((cerr << $ << "; "), ...); }(x),      \
    cerr << '\n'
#else
#define debug(...)                                                             \
  {                                                                            \
  }
#endif

#define MOD 1000000007
#define MAX_d 600

int
add(int a, int b)
{
  return (a + b >= MOD ? a + b - MOD : a + b);
}

string
opt_seq(string seq)
{
  string rtn = "";
  int l = 0, r = seq.length() - 1;
  while(l < seq.length() && seq[l] == 'P') l++;
  while(r >= l && seq[r] == 'L') r--;
  FOR(i,l,r) rtn += seq[i];
  return rtn;
}

int
calc_score(string orig_seq)
{
  string seq = opt_seq(orig_seq);
  int n = seq.length();
  debug(seq.c_str());
  int maxd = 0;
  REP(i, n)
    if (seq[i] == 'L') maxd++;
  vector<int> dp(maxd + 1), dpo(maxd + 1), dpL(maxd + 1), dpP(maxd + 1);

  // Initial values
  dpo[1] = 1;
  FOR(i, 1, n - 1)
  {
    REP(d, maxd + 1)
    {
      dp[d] = dpo[d];
      if (seq[i] == 'L' && d > 0)
      {
        dp[d] = add(dp[d], add(dpo[d - 1], MOD - dpL[d - 1]));
      } else if (seq[i] == 'P' && d < maxd)
      {
        dp[d] = add(dp[d], add(dpo[d + 1], MOD - dpP[d + 1]));
      }
    }
    if (seq[i] == 'L') swap(dpL, dpo);
    else swap(dpP, dpo);
    swap(dpo, dp);
  }
  return dpo[0];
}

int
main()
{
  cin.tie(0)->sync_with_stdio(0);

  int n;
  cin >> n;
  vector<string> bseqs(n);
  for (auto& str : bseqs) cin >> str;

  REP (first, n)
  {
    REP (second, n)
    {
      string seq = bseqs[first] + bseqs[second];
      cout << calc_score(seq) << " ";
    }
    cout << "\n";
  }

  return 0;
}