P16809 [Lanqiao Cup 2026 National Python A] Prefix Parity.

Xiao Lan has $n$ tasks in hand. The time costs of the tasks are all different: $1$ minute, $2$ minutes, $\cdots$, $n$ minutes. Xiao Lan needs to choose an order to complete these tasks one by one. Each time he finishes a task, he records the total accumulated time from the start up to the current moment. Suppose that in some execution order, the task times are $a_1, a_2, \ldots, a_n$. Then when finishing the $i$-th task, the recorded accumulated total time is: $$\begin{aligned} S_i = a_1 + a_2 + \dots + a_i \end{aligned}$$ If among the $n$ recorded times $S_1, S_2, \ldots, S_n$, exactly $k$ of them are even, then this execution order is considered valid. Now please help Xiao Lan compute how many different execution orders are valid in total. Since the answer may be very large, you only need to output the result modulo $998244353$.

Input one line containing two integers $n, k$.

Output one integer, representing the answer.

### Sample Explanation When $n = 3, k = 1$, the valid execution orders are: $$\begin{aligned} 1, 2, 3 \end{aligned}$$ and $$\begin{aligned} 3, 2, 1 \end{aligned}$$ Take the order $1, 2, 3$ as an example. The three completion times are $1, 3, 6$, and only $6$ is even. ### Constraints and Notes for Test Cases For $30\%$ of the test cases, $1 \le n \le 10$. For $60\%$ of the test cases, $1 \le n \le 5000$. For all test cases, $1 \le n \le 10^6$, $0 \le k \le n$. Translated by ChatGPT 5