#include <bits/stdc++.h>
#pragma warning(disable : 4996)
using namespace std;
using ld = long double;
template <class T>
using Table = vector<vector<T>>;
const ld eps = 1e-9;
template <class S, class T>
ostream &operator<<(ostream &os, const pair<S, T> v) {
  os << "( " << v.first << ", " << v.second << ")";
  return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for (int i = 0; i < v.size(); i++) {
    if (i > 0) {
      os << " ";
    }
    os << v[i];
  }
  return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v) {
  for (int i = 0; i < v.size(); i++) {
    if (i > 0) {
      os << endl;
    }
    os << v[i];
  }
  return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<set<T>> &v) {
  for (int i = 0; i < v.size(); i++) {
    if (i > 0) {
      os << endl;
    }
    os << v[i];
  }
  return os;
}
template <class T>
ostream &operator<<(ostream &os, const map<T, T> &v) {
  int i = 0;
  for (auto it : v) {
    if (i > 0) {
      os << ' ';
    }
    os << it.first << ' ' << it.second;
    i++;
  }
  return os;
}
using ll = long long;
const int mod = 998244353;
struct Mod {
 public:
  int num;
  Mod() : Mod(0) { ; }
  Mod(long long int n) : num((n % mod + mod) % mod) {
    static_assert(mod < INT_MAX / 2,
                  "mod is too big, please make num 'long long int' from 'int'");
  }
  Mod(int n) : Mod(static_cast<long long int>(n)) { ; }
  operator int() { return num; }
};
Mod operator+(const Mod a, const Mod b) { return Mod((a.num + b.num) % mod); }
Mod operator+(const long long int a, const Mod b) { return Mod(a) + b; }
Mod operator+(const Mod a, const long long int b) { return b + a; }
Mod operator++(Mod &a) { return a + Mod(1); }
Mod operator-(const Mod a, const Mod b) {
  return Mod((mod + a.num - b.num) % mod);
}
Mod operator-(const long long int a, const Mod b) { return Mod(a) - b; }
Mod operator--(Mod &a) { return a - Mod(1); }
Mod operator*(const Mod a, const Mod b) {
  return Mod(((long long)a.num * b.num) % mod);
}
Mod operator*(const long long int a, const Mod b) { return Mod(a) * b; }
Mod operator*(const Mod a, const long long int b) { return Mod(b) * a; }
Mod operator*(const Mod a, const int b) { return Mod(b) * a; }
Mod operator+=(Mod &a, const Mod b) { return a = a + b; }
Mod operator+=(long long int &a, const Mod b) { return a = a + b; }
Mod operator-=(Mod &a, const Mod b) { return a = a - b; }
Mod operator-=(long long int &a, const Mod b) { return a = a - b; }
Mod operator*=(Mod &a, const Mod b) { return a = a * b; }
Mod operator*=(long long int &a, const Mod b) { return a = a * b; }
Mod operator*=(Mod &a, const long long int &b) { return a = a * b; }
Mod operator^(const Mod a, const int n) {
  if (n == 0) return Mod(1);
  Mod res = (a * a) ^ (n / 2);
  if (n % 2) res = res * a;
  return res;
}
Mod mod_pow(const Mod a, const long long n) {
  if (n == 0) return Mod(1);
  Mod res = mod_pow((a * a), (n / 2));
  if (n % 2) res = res * a;
  return res;
}
Mod inv(const Mod a) { return a ^ (mod - 2); }
Mod operator/(const Mod a, const Mod b) {
  assert(b.num != 0);
  return a * inv(b);
}
Mod operator/(const long long int a, const Mod b) { return Mod(a) / b; }
Mod operator/=(Mod &a, const Mod b) { return a = a / b; }
Mod fact[1024000], factinv[1024000];
void init(const int amax = 1024000) {
  fact[0] = Mod(1);
  factinv[0] = 1;
  for (int i = 0; i < amax - 1; ++i) {
    fact[i + 1] = fact[i] * Mod(i + 1);
    factinv[i + 1] = factinv[i] / Mod(i + 1);
  }
}
Mod comb(const int a, const int b) {
  return fact[a] * factinv[b] * factinv[a - b];
}
using Value = pair<Mod, Mod>;
const Value ini = make_pair(Mod(1), Mod(0));
Value connect(Value al, const Value ar) {
  return make_pair(al.first * ar.first, al.second * ar.first + ar.second);
}
Value dat[800001];
struct segtree {
  int N;
  segtree() {}
  segtree(int n) {
    N = 1;
    while (N < n) N *= 2;
    for (int x = 0; x < N; ++x) {
      { dat[x + N - 1] = ini; }
    }
    for (int x = N - 2; x >= 0; --x) {
      dat[x] = connect(dat[x * 2 + 1], dat[x * 2 + 2]);
    }
  }
  void update(int k, const Value &a) {
    k += N - 1;
    dat[k] = a;
    while (k > 0) {
      k = (k - 1) >> 1;
      dat[k] = connect(dat[k * 2 + 1], dat[k * 2 + 2]);
    }
  }
  Value query(int a, int b) { return query(a, b, 0, 0, N); }
  Value query(int a, int b, int k, int l, int r) {
    if (r <= a or b <= l) return ini;
    if (a <= l and r <= b) return dat[k];
    const int m = (l + r) / 2;
    return connect(query(a, b, k * 2 + 1, l, m), query(a, b, k * 2 + 2, m, r));
  }
};
pair<Mod, Mod> dp[2010][2010];
int flag[2010][2010];
string st;
pair<Mod, Mod> solve(int l, int r) {
  if (flag[l][r]) {
    return dp[l][r];
  }
  flag[l][r] = true;
  if (l == r) {
    return dp[l][r] = make_pair(Mod(st[l] == '?' ? 2 : 1), Mod(0));
  } else if (l - 1 == r) {
    return dp[l][r] = make_pair(Mod(1), Mod(0));
  }
  if (st[l] == '(') {
    if (st[r] == '(') {
      dp[l][r] = solve(l, r - 1);
    } else if (st[r] == '?') {
      auto ap = solve(l + 1, r - 1);
      auto bp = solve(l, r - 1);
      dp[l][r] =
          make_pair(ap.first + bp.first, ap.second + bp.second + ap.first);
    } else {
      auto ap = solve(l + 1, r - 1);
      dp[l][r] = make_pair(ap.first, ap.second + ap.first);
    }
  } else if (st[l] == ')') {
    dp[l][r] = solve(l + 1, r);
  } else {
    if (st[r] == '(') {
      dp[l][r] = solve(l, r - 1);
    } else if (st[r] == '?') {
      auto ap = solve(l + 1, r - 1);
      auto bp = solve(l, r - 1);
      auto cp = solve(l + 1, r);
      auto ep = solve(l + 1, r - 1);
      ap.second += ap.first;
      dp[l][r].first += ap.first + bp.first + cp.first - ep.first;
      dp[l][r].second += ap.second + bp.second + cp.second - ep.second;
    } else {
      auto ap = solve(l + 1, r - 1);
      ap.second += ap.first;
      auto bp = solve(l + 1, r);
      dp[l][r] = make_pair(ap.first + bp.first, ap.second + bp.second);
    }
  }
  return dp[l][r];
}
int main() {
  ios::sync_with_stdio(false);
  cin >> st;
  auto answer = solve(0, int(st.size()) - 1);
  cout << answer.second << endl;
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

This is the easy version of this problem. The only difference is the limit of n - the length of the input string. In this version, 1 ≤ n ≤ 2000. The hard version of this challenge is not offered in the round for the second division. 

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 in the first division 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 2000.

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 warning(disable : 4996)
using namespace std;
using ld = long double;
template <class T>
using Table = vector<vector<T>>;
const ld eps = 1e-9;
template <class S, class T>
ostream &operator<<(ostream &os, const pair<S, T> v) {
  os << "( " << v.first << ", " << v.second << ")";
  return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for (int i = 0; i < v.size(); i++) {
    if (i > 0) {
      os << " ";
    }
    os << v[i];
  }
  return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v) {
  for (int i = 0; i < v.size(); i++) {
    if (i > 0) {
      os << endl;
    }
    os << v[i];
  }
  return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<set<T>> &v) {
  for (int i = 0; i < v.size(); i++) {
    if (i > 0) {
      os << endl;
    }
    os << v[i];
  }
  return os;
}
template <class T>
ostream &operator<<(ostream &os, const map<T, T> &v) {
  int i = 0;
  for (auto it : v) {
    if (i > 0) {
      os << ' ';
    }
    os << it.first << ' ' << it.second;
    i++;
  }
  return os;
}
using ll = long long;
const int mod = 998244353;
struct Mod {
 public:
  int num;
  Mod() : Mod(0) { ; }
  Mod(long long int n) : num((n % mod + mod) % mod) {
    static_assert(mod < INT_MAX / 2,
                  "mod is too big, please make num 'long long int' from 'int'");
  }
  Mod(int n) : Mod(static_cast<long long int>(n)) { ; }
  operator int() { return num; }
};
Mod operator+(const Mod a, const Mod b) { return Mod((a.num + b.num) % mod); }
Mod operator+(const long long int a, const Mod b) { return Mod(a) + b; }
Mod operator+(const Mod a, const long long int b) { return b + a; }
Mod operator++(Mod &a) { return a + Mod(1); }
Mod operator-(const Mod a, const Mod b) {
  return Mod((mod + a.num - b.num) % mod);
}
Mod operator-(const long long int a, const Mod b) { return Mod(a) - b; }
Mod operator--(Mod &a) { return a - Mod(1); }
Mod operator*(const Mod a, const Mod b) {
  return Mod(((long long)a.num * b.num) % mod);
}
Mod operator*(const long long int a, const Mod b) { return Mod(a) * b; }
Mod operator*(const Mod a, const long long int b) { return Mod(b) * a; }
Mod operator*(const Mod a, const int b) { return Mod(b) * a; }
Mod operator+=(Mod &a, const Mod b) { return a = a + b; }
Mod operator+=(long long int &a, const Mod b) { return a = a + b; }
Mod operator-=(Mod &a, const Mod b) { return a = a - b; }
Mod operator-=(long long int &a, const Mod b) { return a = a - b; }
Mod operator*=(Mod &a, const Mod b) { return a = a * b; }
Mod operator*=(long long int &a, const Mod b) { return a = a * b; }
Mod operator*=(Mod &a, const long long int &b) { return a = a * b; }
Mod operator^(const Mod a, const int n) {
  if (n == 0) return Mod(1);
  Mod res = (a * a) ^ (n / 2);
  if (n % 2) res = res * a;
  return res;
}
Mod mod_pow(const Mod a, const long long n) {
  if (n == 0) return Mod(1);
  Mod res = mod_pow((a * a), (n / 2));
  if (n % 2) res = res * a;
  return res;
}
Mod inv(const Mod a) { return a ^ (mod - 2); }
Mod operator/(const Mod a, const Mod b) {
  assert(b.num != 0);
  return a * inv(b);
}
Mod operator/(const long long int a, const Mod b) { return Mod(a) / b; }
Mod operator/=(Mod &a, const Mod b) { return a = a / b; }
Mod fact[1024000], factinv[1024000];
void init(const int amax = 1024000) {
  fact[0] = Mod(1);
  factinv[0] = 1;
  for (int i = 0; i < amax - 1; ++i) {
    fact[i + 1] = fact[i] * Mod(i + 1);
    factinv[i + 1] = factinv[i] / Mod(i + 1);
  }
}
Mod comb(const int a, const int b) {
  return fact[a] * factinv[b] * factinv[a - b];
}
using Value = pair<Mod, Mod>;
const Value ini = make_pair(Mod(1), Mod(0));
Value connect(Value al, const Value ar) {
  return make_pair(al.first * ar.first, al.second * ar.first + ar.second);
}
Value dat[800001];
struct segtree {
  int N;
  segtree() {}
  segtree(int n) {
    N = 1;
    while (N < n) N *= 2;
    for (int x = 0; x < N; ++x) {
      { dat[x + N - 1] = ini; }
    }
    for (int x = N - 2; x >= 0; --x) {
      dat[x] = connect(dat[x * 2 + 1], dat[x * 2 + 2]);
    }
  }
  void update(int k, const Value &a) {
    k += N - 1;
    dat[k] = a;
    while (k > 0) {
      k = (k - 1) >> 1;
      dat[k] = connect(dat[k * 2 + 1], dat[k * 2 + 2]);
    }
  }
  Value query(int a, int b) { return query(a, b, 0, 0, N); }
  Value query(int a, int b, int k, int l, int r) {
    if (r <= a or b <= l) return ini;
    if (a <= l and r <= b) return dat[k];
    const int m = (l + r) / 2;
    return connect(query(a, b, k * 2 + 1, l, m), query(a, b, k * 2 + 2, m, r));
  }
};
pair<Mod, Mod> dp[2010][2010];
int flag[2010][2010];
string st;
pair<Mod, Mod> solve(int l, int r) {
  if (flag[l][r]) {
    return dp[l][r];
  }
  flag[l][r] = true;
  if (l == r) {
    return dp[l][r] = make_pair(Mod(st[l] == '?' ? 2 : 1), Mod(0));
  } else if (l - 1 == r) {
    return dp[l][r] = make_pair(Mod(1), Mod(0));
  }
  if (st[l] == '(') {
    if (st[r] == '(') {
      dp[l][r] = solve(l, r - 1);
    } else if (st[r] == '?') {
      auto ap = solve(l + 1, r - 1);
      auto bp = solve(l, r - 1);
      dp[l][r] =
          make_pair(ap.first + bp.first, ap.second + bp.second + ap.first);
    } else {
      auto ap = solve(l + 1, r - 1);
      dp[l][r] = make_pair(ap.first, ap.second + ap.first);
    }
  } else if (st[l] == ')') {
    dp[l][r] = solve(l + 1, r);
  } else {
    if (st[r] == '(') {
      dp[l][r] = solve(l, r - 1);
    } else if (st[r] == '?') {
      auto ap = solve(l + 1, r - 1);
      auto bp = solve(l, r - 1);
      auto cp = solve(l + 1, r);
      auto ep = solve(l + 1, r - 1);
      ap.second += ap.first;
      dp[l][r].first += ap.first + bp.first + cp.first - ep.first;
      dp[l][r].second += ap.second + bp.second + cp.second - ep.second;
    } else {
      auto ap = solve(l + 1, r - 1);
      ap.second += ap.first;
      auto bp = solve(l + 1, r);
      dp[l][r] = make_pair(ap.first + bp.first, ap.second + bp.second);
    }
  }
  return dp[l][r];
}
int main() {
  ios::sync_with_stdio(false);
  cin >> st;
  auto answer = solve(0, int(st.size()) - 1);
  cout << answer.second << endl;
  return 0;
}

```