{"raw_statement":[{"iden":"problem statement","content":"You are given integers $N$, $K$, and a correct bracket sequence $S$ of length $K$ consisting of `(` and `)`.\nFind the number, modulo $998244353$, of length-$N$ strings $T$ consisting of `(` and `)` that satisfy all of the following conditions:\n\n*   There exists a (not necessarily contiguous) subsequence of $T$ that is a correct bracket sequence of length $K$.\n*   Among all (not necessarily contiguous) subsequences of $T$ that are correct bracket sequences of length $K$, the lexicographically largest one is $S$.\n\nHere, concerning the lexicographical order of strings consisting of `(` and `)`, we consider `(` smaller than `)`.\nNotes 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.\n\n1.  $|S| < |T|$ and $S_1S_2\\ldots S_{|S|} = T_1T_2\\ldots T_{|S|}$.\n2.  There exists an integer $1 \\leq i \\leq \\min\\lbrace |S|, |T| \\rbrace$ such that:\n    *   $S_1S_2\\ldots S_{i-1} = T_1T_2\\ldots T_{i-1}$,\n    *   $S_i$ is a character smaller than $T_i$."},{"iden":"constraints","content":"*   $K \\leq N \\leq 10^7$\n*   $2 \\leq K \\leq 5 \\times 10^5$\n*   $N$ and $K$ are integers.\n*   $S$ is a correct bracket sequence of length $K$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $K$\n$S$"},{"iden":"sample input 1","content":"7 4\n(())"},{"iden":"sample output 1","content":"20\n\nFor 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.\nIf $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."},{"iden":"sample input 2","content":"20 4\n()()"},{"iden":"sample output 2","content":"1047225"},{"iden":"sample input 3","content":"71 10\n()(()())()"},{"iden":"sample output 3","content":"190654464"},{"iden":"sample input 4","content":"10000000 28\n(()()(()))(()((()))())()(())"},{"iden":"sample output 4","content":"769035381"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}