Background

惊觉往事历历已经年。

本题中合法括号串的定义如下：

• $\texttt{()}$ 是合法括号串。
• 如果 $\texttt{A}$ 是合法括号串，则 $\texttt{(A)}$ 是合法括号串。
• 如果 $\texttt{A}$，$\texttt{B}$ 是合法括号串，则 $\texttt{AB}$ 是合法括号串。

Description

小 E 曾拥有一个合法括号串 $s$。时光荏苒，$s$ 如今已变成了一个长度为 $n$ 的不合法括号串 $t$。

然而小 E 却从未失去对括号的热爱。虽然小 E 已经忘记了 $s$ 的具体构成，但他还是试着通过若干次操作将 $t$ 变为一个合法括号串。每次操作，他会选择 $t$ 中任意两个相邻位置，在中间插入一个 $\texttt{(}$ 或一个 $\texttt{)}$ 。

特别地，对于小 E 的每次操作，他同样可以在当前括号串的开头或结尾插入括号。

由于小 E 很懒，因此他会保证从初始括号串 $t$ 到最后得到的合法括号串 $t'$，所用的操作次数最小。但小 E 清楚，依靠这样的操作方式，最终得到 $s$ 的概率微乎其微。于是他转而问你：对于给定的括号串 $t$，按照小 E 的操作方式，最终能够得到多少种本质不同的合法括号串 $t'$。

称两个括号串是本质不同的，当且仅当它们的长度不同，或它们有某一位上的括号不同。由于答案可能很大，你只需要输出其对 $998244353$ 取模后的值。

Format

Input

第一行一个正整数 $n$，表示括号串 $t$ 的长度。

第二行一个长度为 $n$ 的，仅包含 $\texttt{(}$ 或 $\texttt{)}$ 的字符串，描述括号串 $t$。

Output

输出一行一个整数表示答案。

Samples

4
((()

5

见附件中的 memory/memory2.in。

见附件中的 memory/memory2.ans。

见附件中的 memory/memory3.in。

见附件中的 memory/memory3.ans。

见附件中的 memory/memory4.in。

见附件中的 memory/memory4.ans。

Limitation

【样例解释 #1】

小 E 只需要进行 $2$ 次操作就能够使得 $t$ 合法。所有可能的 $t'$ 有：

• $\texttt{()()()}$；
• $\texttt{()(())}$；
• $\texttt{(())()}$；
• $\texttt{(()())}$；
• $\texttt{((()))}$。

【样例解释 #2】

该样例满足测试点 $5 \sim 9$ 的条件限制。

【样例解释 #3】

该样例满足测试点 $15 \sim 16$ 的条件限制。

【样例解释 #4】

该样例满足测试点 $19 \sim 21$ 的条件限制。

【数据范围】

对于所有数据，保证 $1 \leq n \leq 5 \times 10^3$，$t$ 中仅包含 $\texttt{(}$ 或 $\texttt{)}$。

特殊性质 A：保证 $t$ 中仅包含 $\texttt{(}$。
特殊性质 B：保证不存在 $1 \leq i < j \leq n$，满足 $t_i = \texttt{(}$，且 $t_j = \texttt{)}$。