У Чию есть скобочная последовательность\(^\dagger\) \(s\) длины \(n\). Пусть \(k\) равно минимальному числу символов, которое Чию должна удалить из \(s\), чтобы сделать \(s\) правильной\(^\ddagger\).
Теперь Косия хочет, чтобы вы посчитали количество способов удалить \(k\) символов из \(s\) так, чтобы \(s\) стала правильной, по модулю \(998\,244\,353\).
Обратите внимание, что два способа удалить символы считаются различными, если и только если множества удаленных индексов различаются.
\(^\dagger\) Скобочной последовательностью называется строка, состоящая только из символов «(» и «)».
\(^\ddagger\) Скобочная последовательность называется правильной, если ее можно превратить в корректное математическое выражение, добавляя только символы + и 1. Например, последовательности (())(), (), (()(())) и пустая строка являются правильными, а )(, (() и (()))( — нет.
Выходные данные
Выведите одно целое число — количество способов удалить \(k\) символов из \(s\) так, чтобы \(s\) стала правильной, по модулю \(998\,244\,353\).
Примечание
В первом примере можно показать, что минимальное количество символов, которое нужно удалить, равно \(2\). Есть \(4\) способа удалить \(2\) символа так, чтобы \(s\) стала правильной, как показано ниже. Удаленные символы показаны красным.
- \(\texttt{(} \color{Red}{\texttt{)}} \texttt{)} \color{Red}{\texttt{(}} \texttt{(} \texttt{)}\),
- \(\texttt{(} \texttt{)} \color{Red}{\texttt{)}} \color{Red}{\texttt{(}} \texttt{(} \texttt{)}\),
- \(\texttt{(} \color{Red}{\texttt{)}} \texttt{)} \texttt{(} \color{Red}{\texttt{(}} \texttt{)}\),
- \(\texttt{(} \texttt{)} \color{Red}{\texttt{)}} \texttt{(} \color{Red}{\texttt{(}} \texttt{)}\).
Во втором примере единственный способ сделать \(s\) сбалансированной — удалить единственную скобку, чтобы получить пустую скобочную последовательность, которая считается сбалансированной.