AT_agc071_b [AGC071B] Maximum Bracket Subsequence

You are given integers $ N $ , $ K $ , and a correct bracket sequence $ S $ of length $ K $ consisting of `(` and `)`. Find the number, modulo $ 998244353 $ , of length- $ N $ strings $ T $ consisting of `(` and `)` that satisfy all of the following conditions: - There exists a (not necessarily contiguous) subsequence of $ T $ that is a correct bracket sequence of length $ K $ . - Among all (not necessarily contiguous) subsequences of $ T $ that are correct bracket sequences of length $ K $ , the lexicographically largest one is $ S $ . Here, concerning the lexicographical order of strings consisting of `(` and `)`, we consider `(` smaller than `)`. Notes on correct bracket sequences A correct bracket sequence is a string that can be transformed into the empty string by repeatedly deleting a substring that is `()` zero or more times. Notes on lexicographical orderA string $ S = S_1S_2\ldots S_{|S|} $ is said to be **lexicographically smaller** than a string $ T = T_1T_2\ldots T_{|T|} $ if either of the following holds. 1. $ |S| < |T| $ and $ S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|} $ . 2. There exists an integer $ 1 \leq i \leq \min\lbrace |S|, |T| \rbrace $ such that: - $ S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1} $ , - $ S_i $ is a character smaller than $ T_i $ .

The input is given from Standard Input in the following format: > $ N $ $ K $ $ S $

Print the answer.

### Sample Explanation 1 For example, if $ T= $ `((())))`, the only (not necessarily contiguous) subsequence of $ T $ that is a correct bracket sequence of length $ 4 $ is `(())`, which equals $ S $ , so it satisfies the conditions. If $ T= $ `((())()`, there are two (not necessarily contiguous) subsequences of $ T $ that are correct bracket sequences of length $ 4 $ : `()()` and `(())`. The lexicographically largest one is `()()`, so it does not satisfy the conditions. ### Constraints - $ K \leq N \leq 10^7 $ - $ 2 \leq K \leq 5 \times 10^5 $ - $ N $ and $ K $ are integers. - $ S $ is a correct bracket sequence of length $ K $ .