题目描述

Bajtessi 以世界上最出色的足球盘带手（及球员）而闻名。在即将到来的世界杯中，他准备了一份包含 $n$ 个盘带动作的列表，其中每个动作都可以用字母 'L' 和 'P' 组成的序列来描述，分别表示他用左脚和右脚触球的顺序。

如果一名球员在盘带中左脚和右脚触球的次数完全相同，则称该盘带是平衡的 (balanced)。此外，如果对于该盘带的任意前缀，左脚触球的次数都不少于右脚触球的次数，则称其为左侧的 (left-sided)。作为一名左脚球员，Bajtessi 认为一个盘带如果既是平衡的又是左侧的，那么它就是梦幻的 (fantastic)。

世界杯是一项汇聚了顶尖球员的特殊赛事。因此，Bajtessi 需要比他准备的 $n$ 个盘带更多的动作。他决定通过一种简单的方式将动作数量增加到 $n^2$ 个——对于初始列表中的每一对盘带（可能相同），新的盘带将由它们对应字符串的拼接而成。换句话说，他会先按照第一个盘带的描述触球，接着按照第二个盘带的描述触球。

在激烈的比赛中，很容易忘记一些本应进行的触球动作，因此 Bajtessi 最终执行的盘带将是他最初想要执行的盘带的一个非空子序列。换句话说，最终的盘带是通过从他想要执行的盘带描述中删除某些（可能是零个，但不是全部）字母而形成的。剩余字母的顺序必须保持不变。

最终执行的盘带可能会是梦幻的，这会让 Bajtessi 非常高兴。他现在想知道，对于新列表中的每一个盘带，有多少种可能的不同梦幻盘带可以通过这种方式偶然执行出来。由于这个数字可能非常大，Bajtessi 只需要该数字对 $10^9 + 7$ 取模后的结果。

你的任务是帮助 Bajtessi 计算他所需要的这些数值。

注意：请注意，Bajtessi 感兴趣的是可以作为原始盘带子序列得到的不同梦幻盘带的数量，而不是通过删除原始盘带描述中的字母来得到梦幻盘带的方法数。

输入格式

标准输入的第一行包含一个自然数 $n$ ($1 \le n \le 600$)，表示 Bajtessi 准备的盘带数量。

接下来的 $n$ 行包含 Bajtessi 的盘带描述。其中的第 $i$ 行包含一个由字母 'L' 和 'P' 组成的非空字符串，即第 $i$ 个盘带的描述。

每个字符串的长度不超过 600。

输出格式

标准输出应包含 $n$ 行。第 $i$ 行应包含恰好 $n$ 个整数，其中第 $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

说明

样例解释：考虑第三个盘带与第四个盘带拼接的结果。该盘带由字符串 LLPP 描述，它有两个梦幻盘带作为其子序列： 盘带 LP —— 注意，虽然我们可以通过 4 种方式从 LLPP 中选出该子序列，但在计算结果时只计入一次。 盘带 LLPP。

同样考虑第二个盘带与第一个盘带拼接的结果。该盘带由字符串 PPLPLLPLPP 描述，它拥有 8 个梦幻盘带作为其子序列：LP、LLPP、LPLP、LLLPPP、LPLLPP、LPLPLP、LLPLPP 和 LPLLPLPP。