AT_agc071_b.[AGC071B] Maximum Bracket Subsequence

给定整数 $N, K$ 以及一个由 ( 和 ) 组成的长度为 $K$ 的合法括号序列 $S$。

请统计满足以下所有条件的长度为 $N$ 的 ( 和 ) 组成的字符串 $T$ 的数量，结果对 $998244353$ 取模：

• $T$ 中存在一个长度为 $K$ 的合法括号子序列
• 在 $T$ 的所有长度为 $K$ 的合法括号子序列中，字典序最大的那个等于 $S$

此处定义 ( 的字典序小于 )。

合法括号序列的定义
合法括号序列是指可以通过 $0$ 次或多次删除 () 这样的子串最终得到空字符串的序列。

子序列的定义
字符串 $S$ 的子序列是指通过删除 $S$ 中 $0$ 个或多个字符（不改变剩余字符顺序）得到的字符串。

字典序的定义
字符串 $S = S_1S_2\ldots S_{|S|}$ 比字符串 $T = T_1T_2\ldots T_{|T|}$ 字典序小，当且仅当满足以下任一条件（其中 $|S|, |T|$ 分别表示字符串 $S, T$ 的长度）：

1. $|S| < |T|$ 且 $S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}$。
2. 存在整数 $1 \leq i \leq \min\{ |S|, |T| \}$ 满足：
   • $S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1}$
   • $S_i$ 的字典序小于 $T_i$

输入从标准输入按以下格式给出：

$N$ $K$ $S$

输出答案。

约束条件

• $K \leq N \leq 10^7$
• $2 \leq K \leq 5 \times 10^5$
• $N, K$ 为整数
• $S$ 是由 ( 和 ) 组成的长度为 $K$ 的合法括号序列

样例解释 #1

例如当 $T=$ ((()))) 时，$T$ 中长度 $4$ 的合法括号子序列只有 (())，这与 $S$ 相等，因此满足条件。
当 $T=$ ((())() 时，$T$ 中存在两个长度 $4$ 的合法括号子序列 ()() 和 (())，其中字典序最大的 ()() 不等于 $S$，因此不满足条件。

翻译由 DeepSeek R1 完成