「MCOI-03」括号

MCOI q 群的日常 …… > 一只书虫仔：挖不到钻石，我要哭了（笑） > WAPER420：我们分明次次挖到钻石啊（疑惑） > 一只书虫仔：（友善的笑容） > 7KByte：为什么你们都喜欢加括号啊（呆呆地望着） > 一只书虫仔：（笑） > WAPER420：（笑） > 鏡音リン：（笑） > 7KByte：（笑） --- 本题中 **合法括号串** 的定义如下： 1. 空串是合法括号串。 2. 如果 ```A``` 是合法括号串，则 ```(A)``` 是合法括号串。 3. 如果 ```A```，```B``` 是合法括号串，则 ```AB``` 是合法括号串。 本题中 **子串** 的定义如下： 字符串 $S$ 的子串是 $S$ 中连续的任意个字符组成的字符串。$S$ 的子串可用起始位置 $l$ 与终止位置 $r$ 来表示，记为 $S(l,r)$（$1 \leq l \leq r \leq |S|$，$|S |$ 表示 ```S``` 的长度）。

定义一个括号串的 $0$ 级偏值为将该括号串修改为 **合法括号串** 需要的最小操作数。一次操作你可以在一个位置 **添加** 一个括号或者 **删除** 一个位置的括号。 定义一个括号串的 $i\ (i>0)$ 级偏值为该串 **所有子串** 的 $i-1$ 级偏值之和。 现在你需要求出一个长度为 $N$ 的括号串 $S$ 的 $K$ 级偏值。答案可能很大，输出对 $998244353$ 取模后的结果。

第一行包括两个整数 $N,K$。 第二行一个字符串代表括号序列 $S$。

一行一个整数代表答案对 $998244353$ 取模的结果。

3 1
(()

6

3 2
(()

15

#### 样例说明 对于样例 $1$，$S$ 的所有子串的 $0$ 级代价为： - $\texttt{(}$，代价为 $1$ - $\texttt{(}$，代价为 $1$ - $\texttt{)}$，代价为 $1$ - $\texttt{((}$，代价为 $2$ - $\texttt{()}$，代价为 $0$ - $\texttt{(()}$，代价为 $1$ 总和为 $1+1+1+2+0+1=6$。 #### 数据规模与约定 **本题采用捆绑测试。** | 子任务编号 | $N\le$ | $K\le$ | 分值 | | :----------: | :----------: | :----------: | :----------: | | $1$ | $5$ | $5$ | $3$ | | $2$ | $5\times 10^3$ | $1$ | $10$ | | $3$ | $10^6$ | $1$ | $12$ | | $4$ | $10^2$ | $10^2$ | $10$ | | $5$ | $5\times10^3$ | $5\times 10^3$ | $20$ | | $6$ | $10^6$ | $10^6$ | $45$ | 对于 $100\%$ 的数据，$1 \le N,K \le 10^6$。 --- 原 idea：WAPER420