Problem Description

Kame-kun loves playing with strings. Today, he prepared an empty string $s$ and performed the following operation $N$ times:

• Split $s$ into strings $l$ and $r$. Replace $s$ with $l +$ () $ + r$.

Given the value of $s$ after $N$ operations as $T$, find the number of possible ways to perform the operations, modulo $998244353$.

Two operation methods are considered different if and only if there exists a positive integer $k$ ($1 \le k \le N$) such that the pair $(l, r)$ in the $k$-th operation is different.

Also, Kame-kun never lies, so there is always at least one way to perform the operations such that $s = T$.

Input Format

The input is given from the standard input in the following format:

$N$ $T$

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

3
(())()

Sample Output #1

3

Sample Input #2

1
()

Sample Output #2

1

Sample Input #3

7
(()(()(())()))

Sample Output #3

72

Notes/Hints

Constraints

• $1 \le N \le 10^5$
• $T$ is a string of length $2N$ consisting of ( and )
• It is always possible to perform appropriate operations to make $s = T$

Sample Explanation 1

The following operations are possible: In the 1st operation, let $l$ and $r$ be empty strings. $s =$ () results. In the 2nd operation, let $l =$ () and $r$ be an empty string. $s =$ ()() results. In the 3rd operation, let $l =$ ( and $r =$ )(). $s =$ (())() results.

Sample Explanation 3

Original idea: turtle0123__

见题面 Input 部分

见题面 Output 部分