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 2ドルN,ドル 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 2ドルN$ 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.

힌트