Единственное различие между двумя версиями задачи состоит в том, что в простой версии задачи нет обновлений.

Есть $$$n$$$ катушек, расположенных вокруг круглого стола. Катушки бывают двух цветов: черного и белого.

Любые две катушки одного цвета можно соединить нитью-отрезком того же цвета. Определим соответствие как способ соединить катушки так, что каждая катушка будет соединена ровно с одной другой катушкой.

Раскраска это выбор цветов (белого или черного) для каждой катушки. Раскраска называется возможной, если для нее существует хотя бы одно соответствие. Это равносильно тому, что количества черных и белых катушек четные.

Для соответствия можно посчитать количество раз, которое какая-то белая нить пересекает какую-то черную нить. Мы считаем не количество точек пересечения, а количество пар нитей разных цветов, которые пересекаются, поэтому одна точка пересечения может быть посчитана несколько раз, если несколько пар нитей пересекаются в одной и той же точке. Если $$$c$$$ это возможная раскраска, обозначим за $$$f(c)$$$ минимальное количество пересечений по всем возможным корректным соответствиям для этой раскраски.

Картинка изображает раскраску bwbbbwww. Для нарисованного соответствия есть одно пересечение между нитями разного цвета. Можно показать, что это минимальное возможное количество по всем корректным соответствиям для этой раскраски, поэтому $$$f(\text{bwbbbwww}) = 1$$$.

Вам дана строка $$$s$$$ описывающая незавершенную раскраску с черными, белыми и непокрашенными катушками. Раскраска $$$c$$$ называется $$$s$$$-достижимой, если ее можно получить, раскрасив все непокрашенные катушки в $$$s$$$, не меняя цвета остальных.

Раскраска $$$c$$$ выбирается случайно равновероятно по всем возможным $$$s$$$-достижимым раскраскам. Найдите математическое ожидание $$$f(c)$$$. Вы должны найти его по модулю $$$998244353$$$.

Можно показать, что ответ может быть записан в виде $$$\frac{p}{q}$$$, где $$$p$$$ и $$$q$$$ некоторые взаимно простые целые числа и $$$q\not\equiv 0\pmod{998244353}$$$. Тогда ответ по модулю $$$998244353$$$ будет равен $$$(p\cdot q^{-1})$$$ modulo $$$998244353$$$.