Problem Description

This problem is translated from PA 2022 Round 3 Drybling Bajtessiego.

Bytessi is widely known as the best striker (and player) in world football. For the upcoming World Cup, he prepared a list of $n$ dribbling patterns. Each dribbling pattern can be described by a string consisting of the letters L and P, which represent the order in which he touches the ball with his left foot and right foot.

If a player touches the ball the same number of times with the left and the right foot, we call such a dribbling pattern balanced. Moreover, for a given dribbling pattern, if every initial part (prefix) satisfies that the number of left-foot touches is not less than the number of right-foot touches, we call such a dribbling pattern left-footed. Since Bytessi is left-footed, he considers a dribbling pattern that is both balanced and left-footed to be excellent.

The World Cup is a special tournament where the best players in the world participate. For this reason, Bytessi needs to prepare more dribbling patterns. He decides to increase the number of patterns to $n^2$ in a simple way: for every pair of dribbling patterns from the initial list (they may be the same), the new dribbling pattern is described by concatenating these two patterns. In other words, he will first dribble using the first pattern, and then continue dribbling using the second pattern.

In intense matches, it is easy to forget some touches that were supposed to be made, so Bytessi’s final dribbling pattern will be a non-empty subsequence of the dribbling pattern he originally intended. In other words, the final dribbling pattern is obtained by deleting some letters (possibly none, but not all) from the intended pattern. The order of the remaining letters must stay unchanged.

The finally performed dribbling pattern will be excellent, and if that happens, Bytessi will be very happy. Now he wants to know, for each new dribbling pattern in the new list, how many different excellent dribbling patterns he could accidentally perform. Since this number can be very large, Bytessi only needs the remainder when it is divided by $10^9+7$. Please help Bytessi solve this problem.

Note: Bytessi is interested in how many different excellent dribbling patterns can be obtained as subsequences of the original pattern, not in the number of ways to cross out letters in the original description to obtain an excellent pattern.

Input Format

The first line contains an integer $n$, the number of dribbling patterns prepared by Bytessi.

The next $n$ lines describe Bytessi’s dribbling patterns. The $i$-th line contains a non-empty string consisting of L and P, describing the $i$-th dribbling pattern.

Output Format

Output $n$ lines, each containing $n$ integers. The $j$-th integer in the $i$-th line denotes the number of excellent subsequences in the new dribbling pattern obtained by concatenating the $i$-th and the $j$-th patterns, taken modulo $10^9+7$.

4
LLPLPP
PPLP
LLP
P

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

Hint

For $100\%$ of the testdata, the following constraints hold:

$1\le n\le 600$.

The length of each dribbling pattern is at most $600$.

Translated by ChatGPT 5