AT_agc071_b [AGC071B] Maximum Bracket Subsequence

整数 $ N,K $ および `(`, `)` からなる長さ $ K $ の正しい括弧列 $ S $ が与えられます。 `(`, `)` からなる長さ $ N $ の文字列 $ T $ のうち、以下の条件をすべて満たすものの数を $ 998244353 $ で割った余りを求めてください。 - $ T $ の部分列であって、長さ $ K $ の正しい括弧列であるものが存在する - $ T $ の部分列であって、長さ $ K $ の正しい括弧列であるもののうち、辞書順で最大のものは $ S $ である なお、 `(`, `)` からなる文字列の辞書順について、 `(` は `)` より小さい文字であるものとします。 正しい括弧列とは 正しい括弧列とは、 `()` である部分文字列を削除することを $ 0 $ 回以上繰り返して空文字列にできる文字列を指します。 部分列とは 文字列 $ S $ の部分列とは、 $ S $ の文字を $ 0 $ 文字以上選んで削除し、残った文字を元の順序を保って結合することで得られる文字列のことを指します。 辞書順とは？文字列 $ S = S_1S_2\ldots S_{|S|} $ が文字列 $ T = T_1T_2\ldots T_{|T|} $ より**辞書順で小さい**とは、下記の 1. と 2. のどちらかが成り立つことを言います。 ここで、 $ |S|, |T| $ はそれぞれ $ S, T $ の長さを表します。 1. $ |S| \lt |T| $ かつ $ S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|} $ 。 2. ある整数 $ 1 \leq i \leq \min\lbrace |S|, |T| \rbrace $ が存在して、下記の $ 2 $ つがともに成り立つ。 - $ S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1} $ - $ S_i $ が $ T_i $ より小さい文字である。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ S $

答えを出力せよ。

### Sample Explanation 1 たとえば $ T= $ `((())))` の場合、 $ T $ の部分列であって、長さ $ 4 $ の正しい括弧列であるものは `(())` のみであり、これは $ S $ に等しいため条件を満たします。 $ T= $ `((())()` の場合、 $ T $ の部分列であって、長さ $ 4 $ の正しい括弧列であるものは `()()` と `(())` の $ 2 $ 種類存在し、辞書順で最大のものは `()()` であるため、条件を満たしません。 ### Constraints - $ K \leq N \leq 10^7 $ - $ 2 \leq K \leq 5 \times 10^5 $ - $ N,K $ は整数 - $ S $ は `(`, `)` からなる長さ $ K $ の正しい括弧列