Description

辉夜希望创造一个无限长的括号序列 $S$ 作为永远亭长廊的绘制图案，它由一个长度为 $n$ 的括号序列 $S_0$ 不断重复而成。

我们称一个括号序列 $T$ 是合法的，当且仅当它可以由以下方式生成：

• $\verb!()!$ 是一个合法的括号序列。
• 如果 $A$ 是合法括号序列，那么 $\verb!(!A\verb!)!$ 同样是一个合法括号序列。
• 如果 $A,B$ 都是合法括号序列，那么 $AB$（即 $A,B$ 拼接）同样是一个合法括号序列。

例如，$\verb!(()())!,\verb!()()!,\verb!((()())())!$ 都是合法括号序列；而 $\verb!)(!,\verb!(()!,\verb!())(()!$ 均不是合法括号序列。

现在辉夜已经确定了 $S_0$ 当中一部分的符号。你需要求出，「在剩下来的单元上绘制括号，使得这条无限长的长廊上可以找到无限长的合法括号序列」的方案数。两种方案不同仅当两种方案中有至少一个位置的 ? 被替换成了不同的字符。输出它对 $998,244,353$（一个大质数）取模后的结果。

Input Format

• 第一行有一个正整数 $n$，表示单元总数。
• 接下来一行有 $n$ 个字符。若第 $i$ 个字符是 $\verb!(!$ 或者 $\verb!)!$，则表示第 $i$ 个单元上绘制的括号已经被辉夜所指定；否则若第 $i$ 个字符是 $\verb!?!$，则表示该位置尚未被确定。

Output Format

• 共一行一个整数。表示所有方案数对 $998,244,353$ 取模后的结果。

4
(???

3

8
(???))??

10

Hint

样例 1 解释

符合条件的方案共有三种：$\verb!(())!$、$\verb!()()!$ 和 $\verb!())(!$。

• 第一种方案，$\overbrace{\text{\tt\textcolor{red}{(())}\textcolor{blue}{(())}\texttt{...}\textcolor{red}{(())}\textcolor{blue}{(())}}}^{\text{无穷个}}$ 可以找到无限长的合法括号序列。
• 第二种方案，$\overbrace{\text{\tt\textcolor{red}{()()}\textcolor{blue}{()()}\texttt{...}\textcolor{red}{()()}\textcolor{blue}{()()}}}^{\text{无穷个}}$ 同样可以找到无限长的合法括号序列。
• 第三种方案，$\text{\tt\textcolor{red}{())}}\overbrace{\text{\tt\textcolor{red}{(}\textcolor{blue}{())(}\texttt{...}\textcolor{red}{())(}\textcolor{blue}{())}}}^{\text{无穷个}}\text{\tt\textcolor{blue}{(}}$ 仍然可以找到无穷长的括号序列。

可以证明，不存在其他方案。

数据范围及约定

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n\le } & \textbf{特殊性质} & \textbf{分值} \cr\hline 1 & 20 & - & 20 \cr\hline 2 & 10^5 & \text{A} & 10 \cr\hline 3 & 10^5 & \text{B} & 10 \cr\hline 4 & 10^5 & - & 60 \cr\hline \end{array}$$

特殊性质 $\textbf{A}$：保证字符串里仅出现 $\verb!(!$ 和 $\verb!)!$。
特殊性质 $\textbf{B}$：保证字符串里仅出现 $\verb!?!$。

对于全部数据，满足 $1\le n\le 10^5$，且字符串里仅出现 $\verb!(!,\verb!)!,\verb!?!$ 三种字符。