{"problem":{"name":"Maximum Bracket Subsequence","description":{"content":"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 `)` th","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc071_b"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $K$\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc071_b","tags":[],"sample_group":[["7 4\n(())","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."],["20 4\n()()","1047225"],["71 10\n()(()())()","190654464"],["10000000 28\n(()()(()))(()((()))())()(())","769035381"]],"created_at":"2026-03-03 11:01:14"}}