AT_agc071_b [AGC071B] Maximum Bracket Subsequence

[problemUrl]: https://atcoder.jp/contests/agc071/tasks/agc071_b 给定整数 $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 完成