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 完成