Count Excellent Dribbling Subsequences

Bytessi, known as the world’s best striker, originally devised n dribbling patterns. Each pattern is described by a string made up of the characters L and P, representing touches by the left and right foot respectively.

A dribbling pattern is balanced if it contains an equal number of L and P. In addition, a pattern is said to be left‐favoring if in every prefix the number of L is at least the number of P. A pattern that is both balanced and left‐favoring is called excellent (these are exactly the classic Dyck words).

For the upcoming World Cup, Bytessi expands his repertoire by forming a new list of n² dribbling patterns obtained by concatenating every ordered pair (possibly the same) of his original patterns. However, during a game it is easy to accidentally omit some touches; thus, the final performed dribbling routine is not the entire intended concatenation, but a non‐empty subsequence of it (obtained by deleting some letters while preserving the order).

Your task is: for each dribbling pattern in this new list, compute the number of distinct excellent dribbling patterns that can be obtained as a subsequence of it. Since the answer might be very large, output it modulo \(10^9+7\).

inputFormat

The first line contains a single integer n, the number of original dribbling patterns.

Each of the next n lines contains a string consisting solely of the characters L and P describing a dribbling pattern.

outputFormat

Output n lines, each containing n space‐separated integers. The j-th integer in the i-th line represents the number of distinct excellent dribbling subsequences (modulo \(10^9+7\)) that can be obtained from the concatenation of the i-th and j-th original dribbling patterns.

sample

2
LP
L

0 1
1 0