题目背景

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$		$3$
$2$	$5\times 10^3$	$1$	$10$
$3$	$10^6$		$12$
$4$	$10^2$		$10$
$5$	$5\times10^3$	$5\times 10^3$	$20$
$6$	$10^6$		$45$

对于 $100\%$ 的数据，$1 \le N,K \le 10^6$。

---

原 idea：WAPER420