Задача . D2. Красивая скобочная последовательность (сложная версия)

Это сложная версия этой задачи. Единственное отличие в ограничении на \(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\).

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