Description

Define the level $0$ deviation value of a bracket string as the minimum number of operations needed to modify this bracket string into a valid bracket sequence. In one operation, you can insert a bracket at some position or delete a bracket at some position.

For $i\ (i>0)$, define the level $i$ deviation value of the string as the sum of the level $i-1$ deviation values over all substrings of this string.

Now you need to compute the level $K$ deviation value of a bracket string $S$ of length $N$. The answer may be very large; output the result modulo $998244353$.

Input Format

The first line contains two integers $N, K$.

The second line contains a string representing the bracket sequence $S$.

Output Format

Output one integer, the answer modulo $998244353$.

3 1
(()

6

3 2
(()

15

Hint

Sample Explanation

For sample $1$, the level $0$ costs of all substrings of $S$ are:

• $\texttt{(}$, cost is $1$.
• $\texttt{(}$, cost is $1$.
• $\texttt{)}$, cost is $1$.
• $\texttt{((}$, cost is $2$.
• $\texttt{()}$, cost is $0$.
• $\texttt{(()}$, cost is $1$.

The total is $1+1+1+2+0+1=6$.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $1 \le N, K \le 10^6$.

Original idea: WAPER420

Translated by ChatGPT 5