28746번 - Блэк & Уайт 다국어

В новом регионе Сэм обнаружил $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$).

Во второй строке дана строка $s$, состоящая из $n$ символов, описывающая дороги между городами на окружности. Если $s_i$ равно <<->>, дорога между городами $i$ и $(i \bmod n + 1)$ отсутствует, если <<W>> --- дорога контролируется бандой Уайта, и если <<B>> --- бандой Блэка.

В третьей строке дана строка $t$, состоящая из $n$ символов, описывающая дороги между столицей и городами на окружности. Если $t_i$ равно <<->>, дорога между столицей и городом $i$ отсутствует, если <<W>> --- дорога контролируется бандой Уайта, и если <<B>> --- бандой Блэка.

Выведите $n + 1$ целое число $a_k$ --- $k$-е из них должно равняться количеству остовных деревьев графа городов, в которых ровно $k$ дорог контролируются бандой Уайта.