블랙과 화이트

새로운 지역에서 샘은 양방향 도로로 연결된 $n + 1$개의 도시를 발견했다. 그중 $n$개의 도시는 원 위에 있고, 나머지 하나는 중심에 자리한 수도다. 원 위의 도시는 순회 순서대로 $1$부터 $n$까지 번호를 붙이고, 수도에는 번호 $n + 1$을 준다. 각 도로는 수도와 원 위의 도시를 잇거나, 원 위에서 인접한 두 도시를 잇는다. 즉 도로는 도시 $(n + 1)$과 $v$를 잇거나, 도시 $v$와 $(v \bmod n + 1)$을 잇는다. 여기서 $v \in [1, n]$이다.

각 도로는 화이트 갱단 또는 블랙 갱단 중 하나가 관리한다. 샘은 어느 도시에서든 다른 모든 도시로 갈 수 있도록, 안전하게 확보할 도로의 수를 최소로 고르려 한다. 다시 말해 도시 그래프의 신장 트리를 고른다. 어떤 신장 트리든 정확히 $n$개의 도로를 포함한다.

도로를 확보하려면 그 도로를 관리하는 갱단의 우두머리와 협상해야 한다. 샘은 어느 갱단이 더 협조적일지 아직 알지 못한다. 그래서 각 정수 $k \in [0, n]$에 대해, 白 화이트 갱단이 관리하는 도로가 정확히 $k$개이고 나머지 $n - k$개는 블랙 갱단이 관리하는 신장 트리의 개수를 구해 달라고 부탁했다. 답이 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 구한다.

첫 줄에 정수 $n$ ($3 \le n \le 50\,000$)이 주어진다.

둘째 줄에는 원 위의 도시 사이 도로를 나타내는 길이 $n$의 문자열 $s$가 주어진다. $s_i$가 -이면 도시 $i$와 도시 $(i \bmod n + 1)$ 사이에 도로가 없다. W이면 화이트 갱단이, B이면 블랙 갱단이 관리하는 도로다.

셋째 줄에는 수도와 원 위의 도시 사이 도로를 나타내는 길이 $n$의 문자열 $t$가 주어진다. $t_i$의 의미는 같으며, 수도와 도시 $i$ 사이의 도로를 뜻한다.

$n + 1$개의 정수 $a_k$를 출력한다. $k$번째 정수는 화이트 갱단이 관리하는 도로를 정확히 $k$개 포함하는 신장 트리의 개수다.