Menji is playing a multiplayer puzzle game.

In this game, there are $n$ players standing in order at positions $1, 2, 3, \dots, n$ on a number line. The $i$-th player faces a direction $d_i$, which is either left or right.

Each player has a shrink gun. Players take turns according to a permutation $p$. When it is player $x$'s turn to act: If the player has already been shrunk, they do not perform any action. Otherwise, they fire a bullet in the direction they are facing. The bullet hits the first un-shrunk player in that direction (if there are no players in that direction, it hits no one). The player who is hit is immediately shrunk.

Due to the chaotic situation, in the actual game, $p$ is chosen uniformly at random from all $n!$ possible permutations.

Menji wants to know, for each $1 \le k \le n$, how many permutations result in exactly $k$ players remaining un-shrunk.

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

Input

The input is read from standard input. The first line contains an integer $n$ ($2 \le n \le 500$). The next line contains a string $s$ of length $n$. Here $s_i \in \{L, R\}$. If $s_i = L$, the $i$-th player faces left (the direction of player $1$); if $s_i = R$, the $i$-th player faces right (the direction of player $n$).

Output

Output to standard output. Output a single line containing $n$ integers, where the $i$-th number represents the number of permutations that result in exactly $i$ players remaining.

Examples

Input 1

2
RL

Output 1

2 0

Input 2

4
LLRR

Output 2

0 24 0 0

Input 3

10
LRLRLLRRRR

Output 3

0 0 0 604800 3024000 0 0 0 0 0