Bajtessi is widely known for being the best dribbler (and player) in football in the entire world. For the upcoming world championship, he has prepared a list of $n$ dribbles, where each of them can be described by a sequence of letters 'L' and 'P', which denote the order in which he touches the ball with his left and right foot, respectively.

A dribble is called balanced if the player touches the ball with his left foot exactly as many times as with his right foot. Additionally, it is left-sided if, for any initial fragment (prefix) of the given dribble, the player touches the ball with his left foot at least as many times as he touches it with his right foot. Bajtessi, as a left-footed player, considers a dribble fantastic if it is balanced and left-sided.

The world championship is a unique competition that brings together the best players. For this reason, Bajtessi needs more than the $n$ dribbles he has prepared. He decided that he will easily increase this number to $n^2$ – for every pair of dribbles from the initial list, possibly the same ones, a new dribble will be described by the concatenation of their corresponding sequences. In other words, he will first touch the ball according to the description of the first dribble, and then he will proceed according to the description of the second dribble.

In the heat of the match, it is easy to forget some of the touches on the ball that should have been performed, so the final dribble performed by Bajtessi will be a non-empty subsequence of the dribble he initially intended to perform. In other words, the final dribble will be formed by deleting some (possibly none, but not all) letters from the description of the dribble he intended to perform. The order of the remaining letters must remain unchanged.

It may turn out that the finally performed dribble is fantastic, which will make Bajtessi very happy. He is now wondering, for each dribble from the new list, how many possible fantastic dribbles exist that he could accidentally perform. Since this number can be very large, it is sufficient for Bajtessi to know the remainder of this number divided by $10^9 + 7$.

Your task is to help Bajtessi and calculate the numbers he requested.

Note: Note that Bajtessi is interested in the number of different fantastic dribbles that can be obtained as a subsequence of his original dribble, not the number of ways to delete letters from the description of the original dribble that result in a fantastic dribble.

Input

The first line of standard input contains a single natural number $n$ ($1 \le n \le 600$), denoting the number of dribbles prepared by Bajtessi.

The next $n$ lines contain the descriptions of Bajtessi's dribbles. The $i$-th of these lines contains a non-empty sequence of letters 'L' and 'P', which is the description of the $i$-th dribble.

The length of no sequence exceeds 600 characters.

Output

The standard output should contain $n$ lines. The $i$-th line should contain exactly $n$ integers, and the $j$-th of them should be equal to the remainder of the division by $10^9 + 7$ of the number of fantastic dribbles described in the problem statement that can be performed when attempting to perform the dribble that is the concatenation of the $i$-th and $j$-th dribble from the original list.

Examples

Input 1

4
LLPLPP
PPLP
LLP
P

Output 1

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

Note

Explanation of the example: Let us consider the answer for the concatenation of the third dribble with the fourth. This dribble is described by the sequence 'LLPP', which has 2 fantastic dribbles as its subsequences: Dribble 'LP' – note that although we can choose this dribble as a subsequence of 'LLPP' in 4 ways, we count it only once in the result. Dribble 'LLPP'.

Let us also consider the answer for the concatenation of the second dribble with the first. Such a dribble is described by the sequence PPLPLLPLPP, which has 8 fantastic dribbles as its subsequences: 'LP', 'LLPP', 'LPLP', 'LLLPPP', 'LPLLPP', 'LPLPLP', 'LLPLPP' and 'LPLLPLPP'.