AT_arc194_d [ARC194D] Reverse Brackets

满足以下任一条件的字符串定义为**合法括号序列**： - 空字符串 - 存在某个正确括号序列 $A$，将 `(`、$A$、`)` 按此顺序连接形成的字符串 - 存在非空的正确括号序列 $A$ 和 $B$，将 $A$ 和 $B$ 按此顺序连接形成的字符串 给定一个长度为 $N$ 的合法括号序列 $S$。你可以进行任意次以下操作： - 选择 $S$ 的一个连续子字符串（该子字符串本身必须是合法括号序列），将其 _反転_ 。 这里，将 $S$ 的第 $l$ 到第 $r$ 个字符组成的连续子字符串 _反転_ 的定义如下： - 对于满足 $l \leq i \leq r$ 的所有整数 $i$，同时将 $S_i$ 替换为：若 $S_{l+r-i}$ 是 `(` 则替换为 `)`，若 $S_{l+r-i}$ 是 `)` 则替换为 `(`。（注意：此处的 _反転_ 定义与通常的 _反转_ 不同） 请计算操作结束后可能存在的不同 $S$ 的数量，结果对 $998244353$ 取模。

输入通过标准输入给出，格式如下： > $N$ $S$

输出答案。

### 约束条件 - $1 \leq N \leq 5000$ - $|S|=N$ - $S$ 是正确括号序列 ### 样例解释 1 例如，通过以下操作可以将 $S$ 变为 `()(())`： - 选择 $S$ 的第 $1$ 到第 $6$ 个字符作为连续子字符串（这是一个合法括号序列）。此时 $S$ 变为 `()(())`。 其他可以生成的 $S$ 只有 `(())()`。因此答案为 $2$。 翻译由 DeepSeek R1 完成