K-th Order Bias of Parentheses String

We define the 0th order bias of a parentheses string as the minimum number of operations required to transform the string into a valid parentheses string. In one operation, you are allowed to add a parenthesis at any position or delete a parenthesis from any position.

For any integer \(i > 0\), the \(i\)th order bias of a parentheses string is defined as the sum of the \((i-1)\)th order biases of all substrings of the string.

Given a parentheses string \(S\) of length \(N\) and an integer \(K\), compute the \(K\)th order bias of \(S\) modulo \(998244353\).

inputFormat

The first line contains two integers \(N\) and \(K\). The second line contains the parentheses string \(S\) of length \(N\), consisting only of the characters '(' and ')'.

outputFormat

Output a single integer representing the \(K\)th order bias of \(S\) modulo \(998244353\).

sample

3 0
)((

3