Beautiful Bracket Sequence (easy version)
Contest: Codeforces Round 604 (Div. 1)
Difficulty rating: 2600
Tags: combinatorics, dp, probabilities

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 \leq n \leq 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 format:
The only line contains a non-empty string consist of only '(', ')' and '?'. The length of the string is at most $$$2000$$$.

Output format:
Print the answer modulo $$$998244353$$$ in a single line.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
??

Example output:
1

Example input:
(?(?))

Example output:
9

Editorial:
We calculate the depth of a sequence as follow:
• Let two pointers at each end of the sequence.
• If character at the left pointer is ')', we move the left pointer one position to the right.
• If character at the right pointer is '(', we move the right pointer one position to the left.
• If the character at the left pointer is '(' and the right pointer is ')' we increase our result and move the left pointer to the right and the right one to the left each with one position.
• We repeat while the left one is at the left of the right one.
• $$$dp[l][r] += dp[l + 1][r]$$$ if $$$a_l \ne$$$ '('.
• $$$dp[l][r] += dp[l][r - 1]$$$ if $$$a_r \ne$$$ ')'.
• $$$dp[l][r] -= dp[l + 1][r - 1]$$$ if $$$a_l \ne$$$ '(' and $$$a_r \ne$$$ ')'.
• $$$dp[l][r] += dp[l + 1][r - 1] + 2^k$$$ if $$$a_l \ne$$$ ')' and $$$a_r \ne$$$ '(', where $$$k$$$ is the number of '?' character in $$$s_{l + 1}s_{l + 2}\ldots s_{r - 1}$$$.