#include <bits/stdc++.h>
using namespace std;
const int dx44[6] = {0, -1, -1, 1, 1};
const int dy44[6] = {0, -1, 1, -1, 1};
const int dx4[6] = {0, 1, 0, -1};
const int dy4[6] = {1, 0, -1, 0};
const int dx8[9] = {0, -1, 0, 1, 0, 1, 1, -1, -1};
const int dy8[9] = {0, 0, 1, 0, -1, 1, -1, 1, -1};
const int dx82[9] = {0, -1, -1, 1, 1, 2, 2, -2, -2};
const int dy82[9] = {0, 2, -2, 2, -2, 1, -1, 1, -1};
void update(long long &x, long long v) {
  if (x == -1)
    x = v;
  else if (x > v)
    x = v;
}
long long po(long long a, long long b, long long mod) {
  long long res = 1;
  a %= mod;
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
long long gcd(long long a, long long b) {
  if (a == 0) {
    return b;
  } else {
    return gcd(b % a, a);
  }
}
void extgcd(long long a, long long b, long long &d, long long &x,
            long long &y) {
  if (!b) {
    d = a;
    x = 1;
  } else {
    extgcd(b, a % b, d, y, x);
    y -= x * (a / b);
  }
}
long long inverse(long long a, long long n) {
  long long d, x, y;
  extgcd(a, n, d, x, y);
  return d == 1 ? (x + n) % n : -1;
}
const int maxn = 5e3 + 15;
const double PI = acos(-1.0);
const long long mod = 998244353;
const int MOD = 119 << 23 | 1;
int fpow(int a, int k) {
  int r = 1, t = a;
  while (k) {
    if (k & 1) r = (long long)r * t % MOD;
    t = (long long)t * t % MOD;
    k >>= 1;
  }
  return r;
}
void solve() {
  string s;
  cin >> s;
  int n = s.size();
  vector<vector<int>> dp(n, vector<int>(n));
  vector<int> f(n + 1);
  for (int i = 0; i < n; i++) {
    f[i + 1] = f[i];
    f[i + 1] += s[i] == '?';
  }
  for (int len = 2; len <= n; len++) {
    for (int i = 0; i < n - len + 1; i++) {
      int j = i + len - 1;
      if (s[i] != '(') {
        dp[i][j] += dp[i + 1][j];
        dp[i][j] %= MOD;
      }
      if (s[j] != ')') {
        dp[i][j] += dp[i][j - 1];
        dp[i][j] %= MOD;
      }
      if (s[i] != '(' && s[j] != ')') {
        dp[i][j] -= dp[i + 1][j - 1];
        dp[i][j] %= MOD;
        dp[i][j] += MOD;
        dp[i][j] %= MOD;
      }
      if (s[i] != ')' && s[j] != '(') {
        dp[i][j] += dp[i + 1][j - 1];
        dp[i][j] %= MOD;
        dp[i][j] += fpow(2, f[j] - f[i + 1]);
        dp[i][j] %= MOD;
      }
    }
  }
  cout << dp[0][n - 1] << "\n";
}
int main() {
  solve();
  return 0;
}

### Prompt

Please formulate a cpp solution to the following problem:

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>
using namespace std;
const int dx44[6] = {0, -1, -1, 1, 1};
const int dy44[6] = {0, -1, 1, -1, 1};
const int dx4[6] = {0, 1, 0, -1};
const int dy4[6] = {1, 0, -1, 0};
const int dx8[9] = {0, -1, 0, 1, 0, 1, 1, -1, -1};
const int dy8[9] = {0, 0, 1, 0, -1, 1, -1, 1, -1};
const int dx82[9] = {0, -1, -1, 1, 1, 2, 2, -2, -2};
const int dy82[9] = {0, 2, -2, 2, -2, 1, -1, 1, -1};
void update(long long &x, long long v) {
  if (x == -1)
    x = v;
  else if (x > v)
    x = v;
}
long long po(long long a, long long b, long long mod) {
  long long res = 1;
  a %= mod;
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
long long gcd(long long a, long long b) {
  if (a == 0) {
    return b;
  } else {
    return gcd(b % a, a);
  }
}
void extgcd(long long a, long long b, long long &d, long long &x,
            long long &y) {
  if (!b) {
    d = a;
    x = 1;
  } else {
    extgcd(b, a % b, d, y, x);
    y -= x * (a / b);
  }
}
long long inverse(long long a, long long n) {
  long long d, x, y;
  extgcd(a, n, d, x, y);
  return d == 1 ? (x + n) % n : -1;
}
const int maxn = 5e3 + 15;
const double PI = acos(-1.0);
const long long mod = 998244353;
const int MOD = 119 << 23 | 1;
int fpow(int a, int k) {
  int r = 1, t = a;
  while (k) {
    if (k & 1) r = (long long)r * t % MOD;
    t = (long long)t * t % MOD;
    k >>= 1;
  }
  return r;
}
void solve() {
  string s;
  cin >> s;
  int n = s.size();
  vector<vector<int>> dp(n, vector<int>(n));
  vector<int> f(n + 1);
  for (int i = 0; i < n; i++) {
    f[i + 1] = f[i];
    f[i + 1] += s[i] == '?';
  }
  for (int len = 2; len <= n; len++) {
    for (int i = 0; i < n - len + 1; i++) {
      int j = i + len - 1;
      if (s[i] != '(') {
        dp[i][j] += dp[i + 1][j];
        dp[i][j] %= MOD;
      }
      if (s[j] != ')') {
        dp[i][j] += dp[i][j - 1];
        dp[i][j] %= MOD;
      }
      if (s[i] != '(' && s[j] != ')') {
        dp[i][j] -= dp[i + 1][j - 1];
        dp[i][j] %= MOD;
        dp[i][j] += MOD;
        dp[i][j] %= MOD;
      }
      if (s[i] != ')' && s[j] != '(') {
        dp[i][j] += dp[i + 1][j - 1];
        dp[i][j] %= MOD;
        dp[i][j] += fpow(2, f[j] - f[i + 1]);
        dp[i][j] %= MOD;
      }
    }
  }
  cout << dp[0][n - 1] << "\n";
}
int main() {
  solve();
  return 0;
}

```