G. Кохиа и скобки
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Чию есть скобочная последовательность$$$^\dagger$$$ $$$s$$$ длины $$$n$$$. Пусть $$$k$$$ равно минимальному числу символов, которое Чию должна удалить из $$$s$$$, чтобы сделать $$$s$$$ правильной$$$^\ddagger$$$.

Теперь Косия хочет, чтобы вы посчитали количество способов удалить $$$k$$$ символов из $$$s$$$ так, чтобы $$$s$$$ стала правильной, по модулю $$$998\,244\,353$$$.

Обратите внимание, что два способа удалить символы считаются различными, если и только если множества удаленных индексов различаются.

$$$^\dagger$$$ Скобочной последовательностью называется строка, состоящая только из символов «(» и «)».

$$$^\ddagger$$$ Скобочная последовательность называется правильной, если ее можно превратить в корректное математическое выражение, добавляя только символы + и 1. Например, последовательности (())(), (), (()(())) и пустая строка являются правильными, а )(, (() и (()))( — нет.

Входные данные

Первая строка содержит строку $$$s$$$ ($$$1 \leq |s| \leq 5 \cdot {10}^5$$$) — скобочную последовательность.

Гарантируется, что $$$s$$$ содержит только символы «(» и «)».

Выходные данные

Выведите одно целое число — количество способов удалить $$$k$$$ символов из $$$s$$$ так, чтобы $$$s$$$ стала правильной, по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
())(()
Выходные данные
4
Входные данные
(
Выходные данные
1
Примечание

В первом примере можно показать, что минимальное количество символов, которое нужно удалить, равно $$$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$$$ сбалансированной — удалить единственную скобку, чтобы получить пустую скобочную последовательность, которая считается сбалансированной.