Background

Daily life in the MCOI q group ……

A little bookworm: If I can’t mine diamonds, I’m going to cry (lol).
WAPER420: But we clearly mine diamonds every time (confused).
A little bookworm: (a friendly smile).
7KByte: Why do you all like adding brackets so much (staring blankly).
A little bookworm: (laugh).
WAPER420: (laugh).
Kagamine Rin: (laugh).
7KByte: (laugh).

In this problem, a valid bracket sequence is defined as follows:

1. The empty string is a valid bracket sequence.
2. If A is a valid bracket sequence, then (A) is a valid bracket sequence.
3. If A, B are valid bracket sequences, then AB is a valid bracket sequence.

In this problem, a substring is defined as follows:

A substring of a string $S$ is a string formed by any consecutive characters in $S$. A substring of $S$ can be represented by a starting position $l$ and an ending position $r$, denoted as $S(l,r)$ ($1 \leq l \leq r \leq |S|$, where $|S|$ denotes the length of S).

Problem 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