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

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