P6689 Sequence

Little C came up with a problem about a bracket sequence, but he is not very good at generating testdata, so he uses a random method. Little C fixes the length $N$ of a bracket sequence $S$. Initially, $S$ is all `(`. He also sets a parameter $K$ at the beginning, and then performs the following random process until $K=0$: 1. Uniformly randomly choose an integer in $[1,N]$, and flip the bracket at this position in $S$ (a left bracket becomes a right bracket, and a right bracket becomes a left bracket). 2. If this operation decreases the number of `(`, then decrease $K$ by $1$. Now the testdata is generated, and the problem is finished. Little C asks you to compute the expected length, modulo $998244353$, of the **longest valid bracket subsequence** (not necessarily contiguous) in $S$ after the above operations.

The first line contains two positive integers $N,K$, whose meanings are given in the statement.

Output one line containing one non-negative integer, which is the answer modulo $998244353$.

**Sample Explanation 1** In the end there are only $3$ possible bracket sequences: `))`, `()`, and `)(`. Their probabilities are $\frac{1}{2}$, $\frac{1}{4}$, and $\frac{1}{4}$, respectively. The lengths of their longest valid bracket subsequences are $0,2,0$, respectively. Therefore the final answer is $\frac{1}{2}$, i.e. $499122177$. **Constraints:** For the first $5\%$ of the testdata, $N=1$. For another $5\%$ of the testdata, $N=2$. For another $5\%$ of the testdata, $N\le 7$, $K\le 5$. For another $15\%$ of the testdata, $N\le 15$, $K\le 500$. For another $15\%$ of the testdata, $N\le 50$, $K\le 50$. For another $15\%$ of the testdata, $N\le 500$, $K\le 100$. For all the testdata, it is guaranteed that $1\le N,K\le 5000$. Translated by ChatGPT 5