题目描述

题目译自 PA 2022 Runda 3 Drybling Bajtessiego

Bytessi 因是世界足坛最好的锋线（和球员）而广为人知。为了即将到来的世界杯，他编制了一份 $n$ 种运球方式的清单，其中每次运球可以用一串字母 L 和 P 来描述，表示他用左脚和右脚触球的顺序。

如果一个球员用左脚和右脚触球次数相等，我们就称这种运球方式是平衡的。此外，如果对于给定的这种运球方式，任意一个初始部分（前缀），满足左脚触球次数不少于右脚触球次数，就称这种运球方式是左利脚的。由于 Bytessi 是左利脚，他认为如果一种运球方式即平衡又左利脚，那么这种运球方式是极佳的。

世界杯是一个特殊的比赛，世界上最好的球员都会来参赛。出于这个原因，Bytessi 需要准备更多的运球方式。他决定使用一种简单的方式把运球方式增加到 $n^2$ 种——对于初始列表中每一对运球方式（可以相同），新的运球方式用这两种运球方式直接相连来描述。换句话说，他会先使用第一种运球方式运球，然后接着用第二种运球方式运球。

在激烈的比赛中，很容易忘记一些本应进行的触球，所以 Bytessi 最后的运球方式将是他最初想的运球方式的一个非空的子序列。换句话说，最后的运球方式将通过删除他想进行的运球方式中的一些（也许没有，但不是全部）字母来得到。其余字母的顺序必须保持不变。

最终采用的运球方式将是极佳的，如果这样的话 Bytessi 会非常高兴。他现在想知道，对于新清单中的每一种运球方式，他可以意外地进行多少种可能的极佳运球方式。由于这个数字可能非常大，Bytessi 只需要知道将这个数字除以 $10^9+7$ 的余数。请帮 Bytessi 解决这个问题。

注意：Bytessi 感兴趣的是其原始运球方式的子序列可以得到多少种不同的极佳运球，而不是从原始运球的描述中划掉字母而得到极佳运球的方法的数量。

输入格式

第一行一个整数 $n$ ($1 \le n \le 600$)，表示 Bytessi 准备的运球方式种数。

接下来 $n$ 行描述 Bytessi 的运球方式。第 $i$ 行包含一个由 L 和 P 组成的非空串，描述第 $i$ 种运球方式。每种运球方式的长度不超过 $600$。

输出格式

输出 $n$ 行，每行 $n$ 个整数。第 $i$ 行第 $j$ 个整数表示如果把第 $i$ 种和第 $j$ 种运球方式相连，新的运球方式中有多少子序列是极佳的，结果对 $10^9+7$ 取模。

4
LLPLPP
PPLP
LLP
P

29 9 8 5
8 2 2 1
11 4 3 2
4 1 1 0

数据规模与约定

对于所有数据，保证：

$1 \le n \le 600$

每种运球方式的长度不超过 $600$

样例解释：

考虑将第三和第四种运球方式相连，得到 LLPP，其中有 $2$ 种极佳的子序列：

LP：注意即使我们可以从 LLPP 中选出四个这样的串，但是我们只计算一次。

LLPP

考虑将第二和第一种运球方式相连，得到 PPLPLLPLPP，有 $8$ 种极佳的运球子序列：LP，LLPP，LPLP，LLLPPP，LPLLPP，LPLPLP，LLPLPP 和 LPLLPLPP。