Migrated from Lutece 3243 无括号，不 CP

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

没有括号题的比赛不是一场好比赛，所以理所当然的就有了这道括号题。

首先还是一个总所周知的合法括号序列的定义——在本题中，我们称一个序列 $S$ 是合法的括号序列当且仅当一下四个条件中任意一个成立：

1. $S=\epsilon$，即 $S$ 是空序列；
2. $\exists\ T\text{ s.t. }S=\texttt{(}+T+\texttt{)}$ 且 $T$ 是合法的括号序列；
3. $\exists\ T\text{ s.t. }S=\texttt{[}+T+\texttt{]}$ 且 $T$ 是合法的括号序列；
4. $\exists\ T, U \text{ s.t. }S=T+U$ 且 $T$ 和 $U$ 是合法的括号序列；

现在你有一个只包含 $\texttt ($ 和 $\texttt )$ 的括号序列 $S$，你可以挑选这个序列中任意多个 $\texttt ($，并对于每一个 $\texttt ($，选择将其变为 $\texttt [$ 或者 $\texttt ]$。请问有多少种方案能够使得将 $S$ 变为一个合法的括号序列（输出对 998244353 $10^9+9$ 取模后的结果即可）。

请注意：

1. 两种方案不同当切仅当最终得到的合法的括号序列不同，与如何得到这一序列的操作方法与顺序无关；
2. 不进行任何操作也是一种方案。

Input

第一行输入一个整数 $n$，表示括号序列 $S$ 的长度。

第二场为括号序列 $S$。

Output

输出一行一个整数，表示将 $S$ 通过如上操作变为合法括号序列的方案数。

Samples

8
((((((()

14

2
()

1

10
(())(()))(

0

Constraints

$2\le n=|S|\le 3\times10^4$ 且 $2\ |\ n$

$S$ 中只包含 $\texttt{(}$ 和 $\texttt{)}$