Black and White

In a new region, Sam found $n + 1$ cities connected by two-way roads. Exactly $n$ of these cities lie on a circle, and one city is the capital located at the center. Number the cities on the circle from $1$ to $n$ in traversal order, and give the capital number $n + 1$. Each road either connects the capital with a city on the circle, or connects two adjacent cities on the circle. That is, a road connects cities $(n + 1)$ and $v$, or cities $v$ and $(v \bmod n + 1)$, where $v \in [1, n]$.

Each road is controlled by one of two rival gangs: the White gang or the Black gang. Sam wants to choose and secure the minimum number of roads so that every city can reach every other city. In other words, Sam wants to choose a spanning tree of the city graph. Any spanning tree contains exactly $n$ roads.

To secure a road, Sam has to make a deal with the leader of the gang that controls it. Sam does not yet know which gang will be more willing to negotiate, so for each integer $k \in [0, n]$ he asks you to count the number of spanning trees that contain exactly $k$ roads controlled by the White gang, with the remaining $n - k$ roads controlled by the Black gang. Since the answers can be large, output them modulo $998\,244\,353$.

The first line contains one integer $n$ ($3 \le n \le 50\,000$).

The second line contains a string $s$ of length $n$ describing the roads between cities on the circle. If $s_i$ is -, there is no road between city $i$ and city $(i \bmod n + 1)$. If $s_i$ is W, the road is controlled by the White gang. If $s_i$ is B, the road is controlled by the Black gang.

The third line contains a string $t$ of length $n$ describing the roads between the capital and the cities on the circle. If $t_i$ is -, there is no road between the capital and city $i$. If $t_i$ is W, the road is controlled by the White gang. If $t_i$ is B, the road is controlled by the Black gang.

Print $n + 1$ integers $a_k$. The $k$-th of them is the number of spanning trees in which exactly $k$ roads are controlled by the White gang.