Description

定义一个括号串的 $0$ 级偏值为将该括号串修改为 合法括号串 需要的最小操作数。一次操作你可以在一个位置 添加 一个括号或者 删除 一个位置的括号。

定义一个括号串的 $i\ (i>0)$ 级偏值为该串 所有子串 的 $i-1$ 级偏值之和。

现在你需要求出一个长度为 $N$ 的括号串 $S$ 的 $K$ 级偏值。答案可能很大，输出对 $998244353$ 取模后的结果。

Input Format

第一行包括两个整数 $N,K$。

第二行一个字符串代表括号序列 $S$。

Output Format

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

3 1
(()

6

3 2
(()

15

Hint

样例说明

对于样例 $1$，$S$ 的所有子串的 $0$ 级代价为：

• $\texttt{(}$，代价为 $1$
• $\texttt{(}$，代价为 $1$
• $\texttt{)}$，代价为 $1$
• $\texttt{((}$，代价为 $2$
• $\texttt{()}$，代价为 $0$
• $\texttt{(()}$，代价为 $1$

总和为 $1+1+1+2+0+1=6$。

数据规模与约定

本题采用捆绑测试。

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

原 idea：WAPER420