#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
struct llm {
  long long value = 0;
  llm(long long val = 0) { this->value = val % (long long)998244353; }
  llm(int val) { this->value = val % (long long)998244353; }
  llm inv() {
    long long a = 1;
    long long b = this->value;
    for (long long m = (long long)998244353 - 2; m > 0; m /= 2) {
      if (m & 1) {
        a = a * b % (long long)998244353;
      }
      b = b * b % (long long)998244353;
    }
    return llm(a);
  }
  llm& operator++();
  llm operator++(int);
  llm& operator--();
  llm operator--(int);
  llm& operator+=(const llm&);
  llm& operator-=(const llm&);
  llm& operator*=(const llm&);
};
llm operator+(const llm& a, const llm& b) {
  return llm((a.value + b.value) % (long long)998244353);
}
llm operator-(const llm& a, const llm& b) {
  return llm((a.value - b.value + (long long)998244353) % (long long)998244353);
}
llm operator*(const llm& a, const llm& b) {
  return llm((a.value * b.value) % (long long)998244353);
}
llm& llm::operator++() {
  *this = *this + 1;
  return *this;
}
llm llm::operator++(int) {
  llm tmp = *this;
  ++*this;
  return tmp;
}
llm& llm::operator--() {
  *this = *this - 1;
  return *this;
}
llm llm::operator--(int) {
  llm tmp = *this;
  --*this;
  return tmp;
}
llm& llm::operator+=(const llm& a) {
  *this = *this + a;
  return *this;
}
llm& llm::operator-=(const llm& a) {
  *this = *this - a;
  return *this;
}
llm& llm::operator*=(const llm& a) {
  *this = *this * a;
  return *this;
}
long long toll(llm a) { return a.value; }
long long Sn;
char S[1010101];
llm Fa[1010101], iFa[1010101];
llm cs[2][1010101];
long long qn = 0;
long long i, j, k;
llm ans;
llm calc(long long a, long long b, long long c, bool typ) {
  long long bca = b + c - a;
  if (qn < bca) bca = qn;
  if (typ) {
    bca--;
  }
  if (bca < 0) return 0;
  return cs[typ][bca];
}
int main() {
  scanf("%s", S);
  Sn = strlen(S);
  Fa[0] = 1;
  for (i = 0; i < Sn; i++) {
    Fa[i + 1] = Fa[i] * (i + 1);
  }
  iFa[Sn] = Fa[Sn].inv();
  for (i = Sn - 1; i >= 0; i--) {
    iFa[i] = iFa[i + 1] * (i + 1);
  }
  long long a = 0, b = 0, c = 0;
  for (i = 0; i < Sn; i++) {
    if (S[i] == ')') b++;
    if (S[i] == '?') c++;
  }
  qn = c;
  if (qn == 0) {
    long long ans = 0;
    for (i = 0; i < Sn; i++) {
      if (S[i] == '(') {
        a++;
      }
      if (S[i] == ')') {
        b--;
      }
      if (ans < min(a, b)) {
        ans = min(a, b);
      }
    }
    printf("%lld", ans);
    return 0;
  }
  cs[0][0] = cs[1][0] = 1ll;
  for (i = 0; i < c; i++) {
    cs[0][i + 1] = cs[0][i] + Fa[c] * iFa[c - i - 1] * iFa[i + 1];
  }
  for (i = 0; i < c - 1; i++) {
    cs[1][i + 1] = cs[1][i] + Fa[c - 1] * iFa[c - i - 2] * iFa[i + 1];
  }
  ans = 0;
  for (i = 0; i < Sn; i++) {
    if (S[i] == ')') {
      b--;
    }
    if (S[i] == '(') {
      a++;
      ans += calc(a, b, c, false);
    }
    if (S[i] == '?') {
      c--;
      ans += calc(a, b, c, true);
    }
  }
  printf("%lld", toll(ans));
  return 0;
}

### Prompt

Please formulate a Cpp solution to the following problem:

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 ≤ n ≤ 10^6.

Let's define a correct bracket sequence and its depth as follow:

  * An empty string is a correct bracket sequence with depth 0. 
  * If "s" is a correct bracket sequence with depth d then "(s)" is a correct bracket sequence with depth d + 1. 
  * If "s" and "t" are both correct bracket sequences then their concatenation "st" is a correct bracket sequence with depth equal to the maximum depth of s and t. 



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.

Input

The only line contains a non-empty string consist of only '(', ')' and '?'. The length of the string is at most 10^6.

Output

Print the answer modulo 998244353 in a single line.

Examples

Input


??


Output


1


Input


(?(?))


Output


9

Note

In the first test case, we can obtain 4 bracket sequences by replacing all characters '?' with either '(' or ')':

  * "((". Its depth is 0; 
  * "))". Its depth is 0; 
  * ")(". Its depth is 0; 
  * "()". Its depth is 1. 



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 ')':

  * "(((())". Its depth is 2; 
  * "()()))". Its depth is 2; 
  * "((()))". Its depth is 3; 
  * "()(())". Its depth is 2. 



So, the answer is 9 = 2 + 2 + 3 + 2.

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
struct llm {
  long long value = 0;
  llm(long long val = 0) { this->value = val % (long long)998244353; }
  llm(int val) { this->value = val % (long long)998244353; }
  llm inv() {
    long long a = 1;
    long long b = this->value;
    for (long long m = (long long)998244353 - 2; m > 0; m /= 2) {
      if (m & 1) {
        a = a * b % (long long)998244353;
      }
      b = b * b % (long long)998244353;
    }
    return llm(a);
  }
  llm& operator++();
  llm operator++(int);
  llm& operator--();
  llm operator--(int);
  llm& operator+=(const llm&);
  llm& operator-=(const llm&);
  llm& operator*=(const llm&);
};
llm operator+(const llm& a, const llm& b) {
  return llm((a.value + b.value) % (long long)998244353);
}
llm operator-(const llm& a, const llm& b) {
  return llm((a.value - b.value + (long long)998244353) % (long long)998244353);
}
llm operator*(const llm& a, const llm& b) {
  return llm((a.value * b.value) % (long long)998244353);
}
llm& llm::operator++() {
  *this = *this + 1;
  return *this;
}
llm llm::operator++(int) {
  llm tmp = *this;
  ++*this;
  return tmp;
}
llm& llm::operator--() {
  *this = *this - 1;
  return *this;
}
llm llm::operator--(int) {
  llm tmp = *this;
  --*this;
  return tmp;
}
llm& llm::operator+=(const llm& a) {
  *this = *this + a;
  return *this;
}
llm& llm::operator-=(const llm& a) {
  *this = *this - a;
  return *this;
}
llm& llm::operator*=(const llm& a) {
  *this = *this * a;
  return *this;
}
long long toll(llm a) { return a.value; }
long long Sn;
char S[1010101];
llm Fa[1010101], iFa[1010101];
llm cs[2][1010101];
long long qn = 0;
long long i, j, k;
llm ans;
llm calc(long long a, long long b, long long c, bool typ) {
  long long bca = b + c - a;
  if (qn < bca) bca = qn;
  if (typ) {
    bca--;
  }
  if (bca < 0) return 0;
  return cs[typ][bca];
}
int main() {
  scanf("%s", S);
  Sn = strlen(S);
  Fa[0] = 1;
  for (i = 0; i < Sn; i++) {
    Fa[i + 1] = Fa[i] * (i + 1);
  }
  iFa[Sn] = Fa[Sn].inv();
  for (i = Sn - 1; i >= 0; i--) {
    iFa[i] = iFa[i + 1] * (i + 1);
  }
  long long a = 0, b = 0, c = 0;
  for (i = 0; i < Sn; i++) {
    if (S[i] == ')') b++;
    if (S[i] == '?') c++;
  }
  qn = c;
  if (qn == 0) {
    long long ans = 0;
    for (i = 0; i < Sn; i++) {
      if (S[i] == '(') {
        a++;
      }
      if (S[i] == ')') {
        b--;
      }
      if (ans < min(a, b)) {
        ans = min(a, b);
      }
    }
    printf("%lld", ans);
    return 0;
  }
  cs[0][0] = cs[1][0] = 1ll;
  for (i = 0; i < c; i++) {
    cs[0][i + 1] = cs[0][i] + Fa[c] * iFa[c - i - 1] * iFa[i + 1];
  }
  for (i = 0; i < c - 1; i++) {
    cs[1][i + 1] = cs[1][i] + Fa[c - 1] * iFa[c - i - 2] * iFa[i + 1];
  }
  ans = 0;
  for (i = 0; i < Sn; i++) {
    if (S[i] == ')') {
      b--;
    }
    if (S[i] == '(') {
      a++;
      ans += calc(a, b, c, false);
    }
    if (S[i] == '?') {
      c--;
      ans += calc(a, b, c, true);
    }
  }
  printf("%lld", toll(ans));
  return 0;
}

```