Swapping Brackets

Time limit1.5sMemory limit1024 MB

Summary

Count the nonempty position sets S where rearranging the brackets inside S can turn the sequence into a proper bracket sequence, modulo 998244353.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, String
Solved: No attempts yet

Problem

You are given a bracket sequence with $N$ open brackets and $N$ closed brackets. Let $S$ be a nonempty set of integers from $1$ to $2N$ , inclusive. You can choose two indices in $S$ , not necessarily adjacent, and swap the brackets at those two positions.

Find the number of sets $S$ for which repeatedly applying this operation any number of times turns the sequence into a proper bracket sequence.

Input

The first line contains one integer $N$ .

The second line contains a string of $2N$ brackets, each either ( or ).

Output

Print the number of possible sets $S$ modulo $998\,244\,353$ . The number $998\,244\,353$ is prime.

Constraints

$1 \leq N \leq 3000$
The given bracket sequence contains $N$ open brackets and $N$ closed brackets.

Examples2

Example 1
Input
```
3
())(()
```
Expected output
```
36
```
Example 2
Input
```
6
()))(())()((
```
Expected output
```
1536
```