Unique Restoration of a Parentheses Sequence

Consider a valid parentheses sequence S of length (n) (i.e. S is a balanced sequence, where every opening bracket '(' has a corresponding closing bracket ')', and at every prefix the number of '(' is not less than the number of ')').

Now, K is allowed to insert some extra brackets into S (placing them arbitrarily before, between, or after characters of S) so that the resulting colored sequence (T) has total length (m) (with (m\ge n)). The positions corresponding to S are colored black and the newly inserted brackets are colored red. The resulting sequence (T) (which may not be a balanced sequence) must satisfy the following uniqueness property: if one deletes some of its brackets so as to obtain a sequence of length (n) that is balanced, then the only possibility is to recover S (i.e. the extraction must take all the black brackets, and no alternative valid extraction using any red bracket is allowed).

K wishes to count the number of ways to insert exactly (m-n) extra brackets (each extra bracket can be either '(' or ')', but the choice in each gap is forced by the following rule) so that the uniqueness property holds. In fact, one may prove that in order to avoid any alternative balanced subsequence different from S, the extra brackets inserted in each gap must all be of a predetermined type. More precisely, suppose we break the final sequence (T) into (n+1) gaps [ T = R_0 ; S_1 ; R_1 ; S_2 ; \cdots ; S_n ; R_n, ] where (S = S_1S_2\cdots S_n) is the original valid sequence (each (S_i) is either '(' or ')') and (R_i) (possibly empty) is a string of inserted (red) brackets. Then, for every gap (i) with (0\le i< n) the extra brackets in (R_i) must all be of type

( ) ) if (S_{i+1}) is '(',

• otherwise (i.e. if (S_{i+1}) is ')') they must all be of type (().

For the last gap (R_n) (after the last character) the only allowed type is (().

Once the forced type for each gap is determined, any solution is completely determined by how many red brackets are inserted in each gap. If we denote by (L_i) the number of extra brackets inserted in gap (i) (with (0 \le i \le n)), then the only requirement is that:

[ L_0 + L_1 + \cdots + L_{n} = m - n. ]

The number of nonnegative integer solutions to this equation is (\displaystyle \binom{(m-n)+(n+1)-1}{(n+1)-1} = \binom{m}{n}).

Your task is: Given (n), (m) and the original valid parentheses sequence S (of length (n)), compute (\binom{m}{n}) modulo (998244353).

It is guaranteed that (S) is a valid parentheses sequence and (m \ge n).

inputFormat

The first line contains two integers \(n\) and \(m\) (with \(m \ge n\)).

The second line contains a string S of length \(n\) consisting only of characters '(' and ')', which is a valid parentheses sequence.

outputFormat

Output a single integer: the number of ways to insert the extra brackets satisfying the uniqueness property, modulo \(998244353\).

sample

2 3
()

3

</p>