「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$ 取模的结果。

输入输出样例

输入样例 #1

3 1
(()

输出样例 #1

6

输入样例 #2

3 2
(()

输出样例 #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