Problem Statement

A correct parenthesis sequence is defined as a string satisfying one of the following conditions.

• It is the empty string.
• There exists a correct parenthesis sequence $A$ such that the string is the concatenation of (, $A$, ) in this order.
• There exist non-empty correct parenthesis sequences $A, B$ such that the string is the concatenation of $A, B$ in this order.

For example, (())() is a correct parenthesis sequence, while ()( and )( are not.

For a positive even number $N$, a type A correct parenthesis sequence of length $N$ is defined as follows.

• For $1 \le i \le N/2$, $S_i$ is (.
• For $N/2+1 \le i \le N$, $S_i$ is ).

For example, (()) and ((((())))) are type A correct parenthesis sequences.

For a positive even number $N$, a type B correct parenthesis sequence of length $N$ is defined as follows.

• If $i$ is odd, $S_i$ is (.
• If $i$ is even, $S_i$ is ).

For example, ()() and ()()()()() are type B correct parenthesis sequences.

You are given a correct parenthesis sequence $S$ of length $N$ that is type A or type B. Find the number of sequences $T$ of length $N$ consisting of $0, 1$ that satisfy the following conditions.

• If there exists an integer $i$ $(1\le i \le N)$ with $T_i = 0$, let $P_1, \cdots, P_k$ be the indices $i$ with $T_i = 0$ in ascending order. Let $X$ be the concatenation of $S_{P_1}, \cdots, S_{P_k}$ in this order; then $X$ is a correct parenthesis sequence.
• If there exists an integer $i$ $(1\le i \le N)$ with $T_i = 1$, let $Q_1, \cdots, Q_l$ be the indices $i$ with $T_i = 1$ in ascending order. Let $Y$ be the concatenation of $S_{Q_1}, \cdots, S_{Q_l}$ in this order; then $Y$ is a correct parenthesis sequence.

Since the answer can be very large, output it modulo $998244353$.

Constraints

• $2 \le N \le 5\times 10^5$
• $N$ is even.
• $S$ is a type A or type B correct parenthesis sequence.

Input

$N$
$S$

Output

Output the answer.

Sample

4
(())

6

4
()()

4

2
()

2

40
(((((((((((((((((((())))))))))))))))))))

88808106