There are $n$ participants, numbered $1, 2, \dots, n$. The strength of participant $i$ is $i$. All participants are divided into two teams, red and blue, where the team of participant $i$ is described by the character $s_i$. If $s_i$ is 'R', they are on the red team; if $s_i$ is 'B', they are on the blue team.

Now, all participants are arranged in a circle. Every pair of adjacent participants who belong to different teams will have a match. The participant with the higher strength wins, and the score of their team increases by one.

However, the blue team has colluded with the referee: if a red team participant wins a match and they are in the clockwise direction of a blue team participant, this match does not count towards the score.

You want to know, for each $k = -n, \dots, -1, 0, 1, \dots, n$, how many ways there are to arrange the participants such that the red team's score is exactly $k$ greater than the blue team's score. Two arrangements are considered different if and only if there exists some participant whose clockwise neighbor is different in the two arrangements.

Since the answer can be very large, you only need to output the answer modulo $998,244,353$.

Input

The first line contains an integer $n$, representing the number of participants. The second line contains a string $s_1s_2 \dots s_n$ of length $n$, representing the team of each participant.

Output

Output a single line containing $2n + 1$ integers, representing the number of ways for $k = -n, \dots, 0, \dots, n$ modulo $998,244,353$.

Examples

Input 1

3
BRB

Output 1

0 0 1 1 0 0 0

Note 1

As shown in the figure, there are two possible arrangements.

In the first arrangement, although participant 2 wins the match between participant 1 and 2, they belong to the red team and are in the clockwise direction of participant 1, so this match does not count towards the score. The match between participant 2 and 3 is won by the blue team. Therefore, the red team's score is 0, and the blue team's score is 1.

In the second arrangement, two matches take place, and both count towards the score. Both the red team's score and the blue team's score are 1.

Input 2

5
RBBRR

Output 2

0 0 0 0 8 8 8 0 0 0 0

Input 3

See 3.in and 3.ans in the problem directory.

Subtasks

For all data, $3 \le n \le 3,000$, and $s$ is a string consisting of 'B' and 'R'.