Description

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.

Input Format

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

Output Format

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

2 2

499122177

4 2 

873463811

1919 810

488346634

Hint

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