Problem Description

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 Format

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

Output Format

Output one integer, representing the answer.

3 1

2

Hint

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