В новом регионе Сэм обнаружил $$$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$$$ дорог контролируются бандой Уайта.
3 --- WBW
0 0 1 0
3 WWW BBB
1 6 9 0
5 BWB-B WB-W-
0 2 6 3 0 0
4 ---- ----
0 0 0 0 0