D2. Красивая скобочная последовательность (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия этой задачи. Единственное отличие в ограничении на $$$n$$$ — длине входной строки. В этой версии, $$$1 \leq n \leq 10^6$$$.

Определим правильную скобочную последовательность и ее глубину следующим образом:

  • Пустая строка это правильная скобочная последовательность глубины $$$0$$$;
  • Если «s» это правильная скобочная последовательность глубины $$$d$$$ тогда «(s)» это правильная скобочная последовательность глубины $$$d + 1$$$;
  • Если «s» и «t» это две правильные скобочные последовательности тогда их конкатенация «st» это правильная скобочная последовательность с глубиной равной максимальной из глубин $$$s$$$ и $$$t$$$.

Для (не обязательно правильной) скобочной последовательности $$$s$$$ мы определяем ее глубину как максимальную глубину любой правильной скобочной последовательности, которая может быть получена с помощью удаления некоторых символов из $$$s$$$ (возможно нуля). Например, скобочная последовательность $$$s = $$$«())(())» имеет глубину $$$2$$$, потому что при удалении третьего символа мы получим правильную скобочную последовательность «()(())» глубины $$$2$$$.

Дана строка $$$a$$$, состоящая из символов '(', ')' и '?'. Рассмотрим все (не обязательно правильные) скобочные последовательности, получающиеся заменой всех символов '?' в строке $$$a$$$ на '(' или ')'. Посчитайте сумму глубин всех таких скобочных последовательностей. Так как это число может быть очень большим, найдите его по модулю $$$998244353$$$.

Взломы по этой задачи могут быть сделаны, только если простая и сложная версия этой задачи сданы.

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

Единственная строка содержит непустую строку, состоящую только из символов '(', ')' и '?'. Длина строки не превосходит $$$10^6$$$.

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

Выведите ответ по модулю $$$998244353$$$ в единственной строке.

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

В первом тесте, мы можем получить $$$4$$$ скобочные последовательности меняя все символы '?' на '(' или ')':

  • «((». Ее глубина $$$0$$$;
  • «))». Ее глубина $$$0$$$;
  • «)(». Ее глубина $$$0$$$;
  • «()». Ее глубина $$$1$$$.

Поэтому, ответ равен $$$1 = 0 + 0 + 0 + 1$$$.

Во втором тесте, мы можем получить $$$4$$$ скобочные последовательности меняя все символы '?' на '(' или ')':

  • «(((())». Ее глубина $$$2$$$;
  • «()()))». Ее глубина $$$2$$$;
  • «((()))». Ее глубина $$$3$$$;
  • «()(())». Ее глубина $$$2$$$.

Поэтому, ответ равен $$$9 = 2 + 2 + 3 + 2$$$.