题目背景

永远亭是迷途森林里的不可思议的屋子。

为了躲避月之使者的到来，也是为了防御，永远亭内被布下了一条无尽的长廊。困在其中的对手无法触及到真实，陷入到永远与须臾的陷阱里去。

不过，无尽的长廊 $S$ 毕竟只是单一有限走廊 $S_0$ 的无限循环，其本质是永远亭的主人蓬莱山辉夜及八意永琳设下的圈套。正因该长廊是通过辉夜的能力实现的，因此辉夜可以通过修改该「有限长的」走廊 $S_0$，进而作用于「无限长的」长廊 $S$。这意味着有限的修改可以创造出无限的变动。

光秃秃的长廊显得单调，也难以起到掩人耳目的目的。辉夜决定在长廊上绘制象征着月初的「上弦月」和象征着月末的「下弦月」，以达到图案交错重叠的目的。为了方便起见，「上弦月」可以被近似认为是左括号，而「下弦月」可以被近似认为是右括号。作为优雅的月之都的公主，当然会有不少条条框框——轮到你帮助辉夜满足她的要求了。

题目描述

辉夜希望创造一个无限长的括号序列 $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$（一个大质数）取模后的结果。

输入格式

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

输出格式

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

4
(???

3

8
(???))??

10

提示

样例 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!?!$ 三种字符。