B'This is the hard version of this problem. The only difference is the limit of n - the length of the input string. In this version, 1 <= q n <= q 10^6 . Let 's define a correct bracket sequence and its depth as follow: For a (not necessarily correct) bracket sequence s , we define its depth as the maximum depth of any correct bracket sequence induced by removing some characters from s (possibly zero). For example: the bracket sequence s = "())(())" has depth 2 , because by removing the third character we obtain a correct bracket sequence "()(())" with depth 2 . Given a string a consists of only characters '( ', ') ' and '? '. Consider all (not necessarily correct) bracket sequences obtained by replacing all characters '? ' in a by either '( ' or ') '. Calculate the sum of all the depths of all these bracket sequences. As this number can be large, find it modulo 998244353 . Hacks in this problem can be done only if easy and hard versions of this problem was solved. The only line contains a non-empty string consist of only '( ', ') ' and '? '. The length of the string is at most 10^6 . Print the answer modulo 998244353 in a single line. In the first test case, we can obtain 4 bracket sequences by replacing all characters '? ' with either '( ' or ') ': So, the answer is 1 = 0 + 0 + 0 + 1 . In the second test case, we can obtain 4 bracket sequences by replacing all characters '? ' with either '( ' or ') ': So, the answer is 9 = 2 + 2 + 3 + 2 . '...