30302번 - Swapping Brackets 다국어

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

Find the number of $S$ that can result in a proper bracket sequence by repeatedly applying this operation arbitrary number of times.

The first line contains one integer $N$.

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

Print the number of all possible $S$ in modulo $998\, 244\, 353$. $998\, 244\, 353$ is a prime number.

• $1\leq N\leq 3000$
• Given bracket sequence contains $N$ open brackets and $N$ closed brackets.