#include <bits/stdc++.h>
template <typename T>
class IntegerIterator {
 public:
  using value_type = T;
  using difference_type = std::ptrdiff_t;
  using pointer = T*;
  using reference = T;
  using iterator_category = std::input_iterator_tag;
  explicit IntegerIterator(T value) : value(value) {}
  IntegerIterator& operator++() {
    ++value;
    return *this;
  }
  IntegerIterator operator++(int) {
    IntegerIterator copy = *this;
    ++value;
    return copy;
  }
  IntegerIterator& operator--() {
    --value;
    return *this;
  }
  IntegerIterator operator--(int) {
    IntegerIterator copy = *this;
    --value;
    return copy;
  }
  T operator*() const { return value; }
  bool operator==(IntegerIterator rhs) const { return value == rhs.value; }
  bool operator!=(IntegerIterator rhs) const { return !(*this == rhs); }

 private:
  T value;
};
template <typename T>
class IntegerRange {
 public:
  IntegerRange(T begin, T end) : begin_(begin), end_(end) { ; }
  IntegerIterator<T> begin() const { return IntegerIterator<T>(begin_); }
  IntegerIterator<T> end() const { return IntegerIterator<T>(end_); }

 private:
  T begin_;
  T end_;
};
template <typename T>
class ReversedIntegerRange {
  using IteratorType = std::reverse_iterator<IntegerIterator<T>>;

 public:
  ReversedIntegerRange(T begin, T end) : begin_(begin), end_(end) { ; }
  IteratorType begin() const {
    return IteratorType(IntegerIterator<T>(begin_));
  }
  IteratorType end() const { return IteratorType(IntegerIterator<T>(end_)); }

 private:
  T begin_;
  T end_;
};
template <typename T>
IntegerRange<T> range(T to) {
  return IntegerRange<T>(0, to);
}
template <typename T>
IntegerRange<T> range(T from, T to) {
  return IntegerRange<T>(from, to);
}
template <typename T>
IntegerRange<T> inclusiveRange(T to) {
  return IntegerRange<T>(0, to + 1);
}
template <typename T>
IntegerRange<T> inclusiveRange(T from, T to) {
  return IntegerRange<T>(from, to + 1);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from) {
  return ReversedIntegerRange<T>(from, 0);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from, T to) {
  return ReversedIntegerRange<T>(from, to);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from) {
  return ReversedIntegerRange<T>(from + 1, 0);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from, T to) {
  return ReversedIntegerRange<T>(from + 1, to);
}
template <bool b, typename T = void>
using enable_if_t = typename std::enable_if<b, T>::type;
template <bool... Bools>
struct Disjunction : std::false_type {};
template <bool First, bool... Others>
struct Disjunction<First, Others...>
    : std::integral_constant<bool, First || Disjunction<Others...>::value> {};
template <typename T, typename... Types>
using IsOneOf = Disjunction<std::is_same<T, Types>::value...>;
template <typename T>
using IsSaneInteger = std::integral_constant<
    bool,
    std::is_integral<T>::value &&
        !IsOneOf<typename std::remove_cv<T>::type, char, signed char,
                 unsigned char, bool, char16_t, char32_t, wchar_t>::value>;
template <typename T, typename = std::true_type>
struct IdentityHelper;
template <typename T>
struct IdentityHelper<T, typename std::is_arithmetic<T>::type> {
  static T identity() { return 1; }
};
template <typename T>
T identity() {
  return IdentityHelper<T>::identity();
}
template <typename T>
T extendedGcd(T a, T b, T& x, T& y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  T d = extendedGcd(b % a, a, y, x);
  x -= (b / a) * y;
  return d;
}
template <typename T>
class Zn {
 public:
  Zn() : value(0) {}
  template <typename U>
  static Zn valueOf(U value) {
    int x = static_cast<int>(value % mod());
    if (x < 0) {
      x += mod();
    }
    return Zn(x);
  }
  static Zn rawValueOf(int value) {
    ;
    return Zn(value);
  }
  template <typename U>
  Zn& operator=(U rhs) {
    return *this = Zn::valueOf(rhs);
  }
  Zn& operator+=(const Zn& rhs) {
    value += rhs.value;
    if (value >= mod()) {
      value -= mod();
    }
    return *this;
  }
  template <typename U>
  Zn& operator+=(U rhs) {
    return *this += Zn::valueOf(rhs);
  }
  Zn& operator-=(const Zn& rhs) {
    value -= rhs.value;
    if (value < 0) {
      value += mod();
    }
    return *this;
  }
  template <typename U>
  Zn& operator-=(U rhs) {
    return *this -= Zn::valueOf(rhs);
  }
  Zn& operator*=(const Zn& rhs) {
    long long result =
        static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
    value = static_cast<int>(result % mod());
    return *this;
  }
  template <typename U>
  Zn& operator*=(U rhs) {
    return *this *= Zn::valueOf(rhs);
  }
  Zn operator-() const {
    if (value == 0) {
      return *this;
    } else {
      return Zn(mod() - value);
    }
  }
  Zn& operator/=(const Zn& rhs) { return *this *= rhs.inversed(); }
  template <typename U>
  Zn& operator/=(U rhs) {
    return *this /= Zn::valueOf(rhs);
  }
  Zn inversed() const {
    ;
    int x, y;
    int gcd = extendedGcd(value, mod(), x, y);
    (void)gcd;
    ;
    if (x < 0) {
      x += mod();
    }
    return Zn(x);
  }
  template <typename U>
  friend std::ostream& operator<<(std::ostream&, const Zn<U>& zn);
  template <typename U>
  friend std::istream& operator>>(std::istream&, Zn<U>& zn);
  template <typename U>
  friend bool operator==(const Zn<U>& lhs, const Zn<U>& rhs);
  int intValue() const { return value; }

 private:
  explicit Zn(int value) : value(value) {}
  int value;
  constexpr static int mod() { return T::value; }
  template <int N = T::value>
  static constexpr bool correct_or_runtime(int) {
    return N > 0 && N <= (1 << 30);
  }
  static constexpr bool correct_or_runtime(...) { return true; }
  static_assert(
      std::is_same<typename std::decay<decltype(T::value)>::type, int>::value,
      "T::value must be int");
  static_assert(correct_or_runtime(0),
                "Mod has to be positive integer up to 1 << 30");
};
template <typename T>
bool operator==(const Zn<T>& lhs, const Zn<T>& rhs) {
  return lhs.value == rhs.value;
}
template <typename T, typename U>
bool operator==(const Zn<T>& lhs, U rhs) {
  return lhs == Zn<T>::valueOf(rhs);
}
template <typename T, typename U>
bool operator==(U lhs, const Zn<T>& rhs) {
  return rhs == lhs;
}
template <typename T>
bool operator!=(const Zn<T>& lhs, const Zn<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(const Zn<T>& lhs, U rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(U lhs, const Zn<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T>
Zn<T> operator+(const Zn<T>& lhs, const Zn<T>& rhs) {
  Zn<T> copy = lhs;
  return copy += rhs;
}
template <typename T, typename U>
Zn<T> operator+(const Zn<T>& lhs, U rhs) {
  Zn<T> copy = lhs;
  return copy += rhs;
}
template <typename T, typename U>
Zn<T> operator+(U lhs, const Zn<T>& rhs) {
  return rhs + lhs;
}
template <typename T>
Zn<T> operator-(const Zn<T>& lhs, const Zn<T>& rhs) {
  Zn<T> copy = lhs;
  return copy -= rhs;
}
template <typename T, typename U>
Zn<T> operator-(const Zn<T>& lhs, U rhs) {
  Zn<T> copy = lhs;
  return copy -= rhs;
}
template <typename T, typename U>
Zn<T> operator-(U lhs, const Zn<T>& rhs) {
  return Zn<T>::valueOf(lhs) - rhs;
}
template <typename T>
Zn<T> operator*(const Zn<T>& lhs, const Zn<T>& rhs) {
  Zn<T> copy = lhs;
  return copy *= rhs;
}
template <typename T, typename U>
Zn<T> operator*(const Zn<T>& lhs, U rhs) {
  Zn<T> copy = lhs;
  return copy *= rhs;
}
template <typename T, typename U>
Zn<T> operator*(U lhs, const Zn<T>& rhs) {
  return rhs * lhs;
}
template <typename T>
Zn<T> operator/(const Zn<T>& lhs, const Zn<T>& rhs) {
  Zn<T> copy = lhs;
  return copy /= rhs;
}
template <typename T, typename U>
Zn<T> operator/(const Zn<T>& lhs, U rhs) {
  Zn<T> copy = lhs;
  return copy /= rhs;
}
template <typename T, typename U>
Zn<T> operator/(U lhs, const Zn<T>& rhs) {
  return Zn<T>::valueOf(lhs) / rhs;
}
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Zn<T>& zn) {
  return stream << zn.value;
}
template <typename T>
std::istream& operator>>(std::istream& stream, Zn<T>& zn) {
  int64_t value;
  stream >> value;
  zn.value = static_cast<int>(value % T::value);
  return stream;
}
template <typename T>
struct IdentityHelper<Zn<T>> {
  static Zn<T> identity() { return Zn<T>::valueOf(1); }
};
template <int m>
using ZnConst = Zn<std::integral_constant<int, m>>;
using Zn7 = ZnConst<1000000007>;
template <typename T, std::size_t N>
struct MakeVector {
  template <typename... Args,
            typename R = std::vector<decltype(MakeVector<T, N - 1>::make_vector(
                std::declval<Args>()...))>>
  static R make_vector(std::size_t first, Args... sizes) {
    auto inner = MakeVector<T, N - 1>::make_vector(sizes...);
    return R(first, inner);
  }
};
template <typename T>
struct MakeVector<T, 1> {
  template <typename R = std::vector<T>>
  static R make_vector(std::size_t size, const T& value) {
    return R(size, value);
  }
};
template <typename T, typename... Args>
auto make_vector(Args... args)
    -> decltype(MakeVector<T, sizeof...(Args) - 1>::make_vector(args...)) {
  return MakeVector<T, sizeof...(Args) - 1>::make_vector(args...);
}
using namespace std;
class D1KrasivayaSkobochnayaPosledovatelnostProstayaVersiya {
 public:
  static constexpr int kStressCount = 0;
  static void generateTest(std::ostream& test) {}
  void solve(std::istream& in, std::ostream& out) {
    using Z = ZnConst<998244353>;
    string s;
    in >> s;
    int n = s.size();
    auto dpL = make_vector<Z>(n + 1, n + 1, Z());
    auto dpLPrecise = make_vector<Z>(n + 1, n + 1, Z());
    dpL[0][0] = 1;
    for (int i : range(n)) {
      for (int k : inclusiveRange(i)) {
        if (s[i] != ')') {
          dpL[i + 1][k + 1] += dpL[i][k];
          dpLPrecise[i + 1][k + 1] += dpL[i][k];
        }
        if (s[i] != '(') {
          dpL[i + 1][k] += dpL[i][k];
        }
      }
    }
    reverse(s.begin(), s.end());
    for (char& c : s) {
      if (c == '(') {
        c = ')';
      } else if (c == ')') {
        c = '(';
      }
    }
    auto dpR = make_vector<Z>(n + 1, n + 1, Z());
    dpR[0][0] = 1;
    for (int i : range(n)) {
      for (int k : inclusiveRange(i)) {
        if (s[i] != ')') {
          dpR[i + 1][k + 1] += dpR[i][k];
        }
        if (s[i] != '(') {
          dpR[i + 1][k] += dpR[i][k];
        }
      }
    }
    int x;
    for (int i : inclusiveRange(n)) {
      for (int j : downrange(n)) {
        dpR[i][j] += dpR[i][j + 1];
      }
    }
    Z ans;
    for (int i : range(n)) {
      for (int j : range(n)) {
        ans += dpLPrecise[i][j] * dpR[n - i][j];
      }
    }
    out << ans << "\n";
  }
};
int main() {
  std::ios_base::sync_with_stdio(false);
  D1KrasivayaSkobochnayaPosledovatelnostProstayaVersiya solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  in.tie(nullptr);
  out << std::fixed;
  out.precision(20);
  solver.solve(in, out);
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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>
template <typename T>
class IntegerIterator {
 public:
  using value_type = T;
  using difference_type = std::ptrdiff_t;
  using pointer = T*;
  using reference = T;
  using iterator_category = std::input_iterator_tag;
  explicit IntegerIterator(T value) : value(value) {}
  IntegerIterator& operator++() {
    ++value;
    return *this;
  }
  IntegerIterator operator++(int) {
    IntegerIterator copy = *this;
    ++value;
    return copy;
  }
  IntegerIterator& operator--() {
    --value;
    return *this;
  }
  IntegerIterator operator--(int) {
    IntegerIterator copy = *this;
    --value;
    return copy;
  }
  T operator*() const { return value; }
  bool operator==(IntegerIterator rhs) const { return value == rhs.value; }
  bool operator!=(IntegerIterator rhs) const { return !(*this == rhs); }

 private:
  T value;
};
template <typename T>
class IntegerRange {
 public:
  IntegerRange(T begin, T end) : begin_(begin), end_(end) { ; }
  IntegerIterator<T> begin() const { return IntegerIterator<T>(begin_); }
  IntegerIterator<T> end() const { return IntegerIterator<T>(end_); }

 private:
  T begin_;
  T end_;
};
template <typename T>
class ReversedIntegerRange {
  using IteratorType = std::reverse_iterator<IntegerIterator<T>>;

 public:
  ReversedIntegerRange(T begin, T end) : begin_(begin), end_(end) { ; }
  IteratorType begin() const {
    return IteratorType(IntegerIterator<T>(begin_));
  }
  IteratorType end() const { return IteratorType(IntegerIterator<T>(end_)); }

 private:
  T begin_;
  T end_;
};
template <typename T>
IntegerRange<T> range(T to) {
  return IntegerRange<T>(0, to);
}
template <typename T>
IntegerRange<T> range(T from, T to) {
  return IntegerRange<T>(from, to);
}
template <typename T>
IntegerRange<T> inclusiveRange(T to) {
  return IntegerRange<T>(0, to + 1);
}
template <typename T>
IntegerRange<T> inclusiveRange(T from, T to) {
  return IntegerRange<T>(from, to + 1);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from) {
  return ReversedIntegerRange<T>(from, 0);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from, T to) {
  return ReversedIntegerRange<T>(from, to);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from) {
  return ReversedIntegerRange<T>(from + 1, 0);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from, T to) {
  return ReversedIntegerRange<T>(from + 1, to);
}
template <bool b, typename T = void>
using enable_if_t = typename std::enable_if<b, T>::type;
template <bool... Bools>
struct Disjunction : std::false_type {};
template <bool First, bool... Others>
struct Disjunction<First, Others...>
    : std::integral_constant<bool, First || Disjunction<Others...>::value> {};
template <typename T, typename... Types>
using IsOneOf = Disjunction<std::is_same<T, Types>::value...>;
template <typename T>
using IsSaneInteger = std::integral_constant<
    bool,
    std::is_integral<T>::value &&
        !IsOneOf<typename std::remove_cv<T>::type, char, signed char,
                 unsigned char, bool, char16_t, char32_t, wchar_t>::value>;
template <typename T, typename = std::true_type>
struct IdentityHelper;
template <typename T>
struct IdentityHelper<T, typename std::is_arithmetic<T>::type> {
  static T identity() { return 1; }
};
template <typename T>
T identity() {
  return IdentityHelper<T>::identity();
}
template <typename T>
T extendedGcd(T a, T b, T& x, T& y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  T d = extendedGcd(b % a, a, y, x);
  x -= (b / a) * y;
  return d;
}
template <typename T>
class Zn {
 public:
  Zn() : value(0) {}
  template <typename U>
  static Zn valueOf(U value) {
    int x = static_cast<int>(value % mod());
    if (x < 0) {
      x += mod();
    }
    return Zn(x);
  }
  static Zn rawValueOf(int value) {
    ;
    return Zn(value);
  }
  template <typename U>
  Zn& operator=(U rhs) {
    return *this = Zn::valueOf(rhs);
  }
  Zn& operator+=(const Zn& rhs) {
    value += rhs.value;
    if (value >= mod()) {
      value -= mod();
    }
    return *this;
  }
  template <typename U>
  Zn& operator+=(U rhs) {
    return *this += Zn::valueOf(rhs);
  }
  Zn& operator-=(const Zn& rhs) {
    value -= rhs.value;
    if (value < 0) {
      value += mod();
    }
    return *this;
  }
  template <typename U>
  Zn& operator-=(U rhs) {
    return *this -= Zn::valueOf(rhs);
  }
  Zn& operator*=(const Zn& rhs) {
    long long result =
        static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
    value = static_cast<int>(result % mod());
    return *this;
  }
  template <typename U>
  Zn& operator*=(U rhs) {
    return *this *= Zn::valueOf(rhs);
  }
  Zn operator-() const {
    if (value == 0) {
      return *this;
    } else {
      return Zn(mod() - value);
    }
  }
  Zn& operator/=(const Zn& rhs) { return *this *= rhs.inversed(); }
  template <typename U>
  Zn& operator/=(U rhs) {
    return *this /= Zn::valueOf(rhs);
  }
  Zn inversed() const {
    ;
    int x, y;
    int gcd = extendedGcd(value, mod(), x, y);
    (void)gcd;
    ;
    if (x < 0) {
      x += mod();
    }
    return Zn(x);
  }
  template <typename U>
  friend std::ostream& operator<<(std::ostream&, const Zn<U>& zn);
  template <typename U>
  friend std::istream& operator>>(std::istream&, Zn<U>& zn);
  template <typename U>
  friend bool operator==(const Zn<U>& lhs, const Zn<U>& rhs);
  int intValue() const { return value; }

 private:
  explicit Zn(int value) : value(value) {}
  int value;
  constexpr static int mod() { return T::value; }
  template <int N = T::value>
  static constexpr bool correct_or_runtime(int) {
    return N > 0 && N <= (1 << 30);
  }
  static constexpr bool correct_or_runtime(...) { return true; }
  static_assert(
      std::is_same<typename std::decay<decltype(T::value)>::type, int>::value,
      "T::value must be int");
  static_assert(correct_or_runtime(0),
                "Mod has to be positive integer up to 1 << 30");
};
template <typename T>
bool operator==(const Zn<T>& lhs, const Zn<T>& rhs) {
  return lhs.value == rhs.value;
}
template <typename T, typename U>
bool operator==(const Zn<T>& lhs, U rhs) {
  return lhs == Zn<T>::valueOf(rhs);
}
template <typename T, typename U>
bool operator==(U lhs, const Zn<T>& rhs) {
  return rhs == lhs;
}
template <typename T>
bool operator!=(const Zn<T>& lhs, const Zn<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(const Zn<T>& lhs, U rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(U lhs, const Zn<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T>
Zn<T> operator+(const Zn<T>& lhs, const Zn<T>& rhs) {
  Zn<T> copy = lhs;
  return copy += rhs;
}
template <typename T, typename U>
Zn<T> operator+(const Zn<T>& lhs, U rhs) {
  Zn<T> copy = lhs;
  return copy += rhs;
}
template <typename T, typename U>
Zn<T> operator+(U lhs, const Zn<T>& rhs) {
  return rhs + lhs;
}
template <typename T>
Zn<T> operator-(const Zn<T>& lhs, const Zn<T>& rhs) {
  Zn<T> copy = lhs;
  return copy -= rhs;
}
template <typename T, typename U>
Zn<T> operator-(const Zn<T>& lhs, U rhs) {
  Zn<T> copy = lhs;
  return copy -= rhs;
}
template <typename T, typename U>
Zn<T> operator-(U lhs, const Zn<T>& rhs) {
  return Zn<T>::valueOf(lhs) - rhs;
}
template <typename T>
Zn<T> operator*(const Zn<T>& lhs, const Zn<T>& rhs) {
  Zn<T> copy = lhs;
  return copy *= rhs;
}
template <typename T, typename U>
Zn<T> operator*(const Zn<T>& lhs, U rhs) {
  Zn<T> copy = lhs;
  return copy *= rhs;
}
template <typename T, typename U>
Zn<T> operator*(U lhs, const Zn<T>& rhs) {
  return rhs * lhs;
}
template <typename T>
Zn<T> operator/(const Zn<T>& lhs, const Zn<T>& rhs) {
  Zn<T> copy = lhs;
  return copy /= rhs;
}
template <typename T, typename U>
Zn<T> operator/(const Zn<T>& lhs, U rhs) {
  Zn<T> copy = lhs;
  return copy /= rhs;
}
template <typename T, typename U>
Zn<T> operator/(U lhs, const Zn<T>& rhs) {
  return Zn<T>::valueOf(lhs) / rhs;
}
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Zn<T>& zn) {
  return stream << zn.value;
}
template <typename T>
std::istream& operator>>(std::istream& stream, Zn<T>& zn) {
  int64_t value;
  stream >> value;
  zn.value = static_cast<int>(value % T::value);
  return stream;
}
template <typename T>
struct IdentityHelper<Zn<T>> {
  static Zn<T> identity() { return Zn<T>::valueOf(1); }
};
template <int m>
using ZnConst = Zn<std::integral_constant<int, m>>;
using Zn7 = ZnConst<1000000007>;
template <typename T, std::size_t N>
struct MakeVector {
  template <typename... Args,
            typename R = std::vector<decltype(MakeVector<T, N - 1>::make_vector(
                std::declval<Args>()...))>>
  static R make_vector(std::size_t first, Args... sizes) {
    auto inner = MakeVector<T, N - 1>::make_vector(sizes...);
    return R(first, inner);
  }
};
template <typename T>
struct MakeVector<T, 1> {
  template <typename R = std::vector<T>>
  static R make_vector(std::size_t size, const T& value) {
    return R(size, value);
  }
};
template <typename T, typename... Args>
auto make_vector(Args... args)
    -> decltype(MakeVector<T, sizeof...(Args) - 1>::make_vector(args...)) {
  return MakeVector<T, sizeof...(Args) - 1>::make_vector(args...);
}
using namespace std;
class D1KrasivayaSkobochnayaPosledovatelnostProstayaVersiya {
 public:
  static constexpr int kStressCount = 0;
  static void generateTest(std::ostream& test) {}
  void solve(std::istream& in, std::ostream& out) {
    using Z = ZnConst<998244353>;
    string s;
    in >> s;
    int n = s.size();
    auto dpL = make_vector<Z>(n + 1, n + 1, Z());
    auto dpLPrecise = make_vector<Z>(n + 1, n + 1, Z());
    dpL[0][0] = 1;
    for (int i : range(n)) {
      for (int k : inclusiveRange(i)) {
        if (s[i] != ')') {
          dpL[i + 1][k + 1] += dpL[i][k];
          dpLPrecise[i + 1][k + 1] += dpL[i][k];
        }
        if (s[i] != '(') {
          dpL[i + 1][k] += dpL[i][k];
        }
      }
    }
    reverse(s.begin(), s.end());
    for (char& c : s) {
      if (c == '(') {
        c = ')';
      } else if (c == ')') {
        c = '(';
      }
    }
    auto dpR = make_vector<Z>(n + 1, n + 1, Z());
    dpR[0][0] = 1;
    for (int i : range(n)) {
      for (int k : inclusiveRange(i)) {
        if (s[i] != ')') {
          dpR[i + 1][k + 1] += dpR[i][k];
        }
        if (s[i] != '(') {
          dpR[i + 1][k] += dpR[i][k];
        }
      }
    }
    int x;
    for (int i : inclusiveRange(n)) {
      for (int j : downrange(n)) {
        dpR[i][j] += dpR[i][j + 1];
      }
    }
    Z ans;
    for (int i : range(n)) {
      for (int j : range(n)) {
        ans += dpLPrecise[i][j] * dpR[n - i][j];
      }
    }
    out << ans << "\n";
  }
};
int main() {
  std::ios_base::sync_with_stdio(false);
  D1KrasivayaSkobochnayaPosledovatelnostProstayaVersiya solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  in.tie(nullptr);
  out << std::fixed;
  out.precision(20);
  solver.solve(in, out);
  return 0;
}

```