P6561 [SBCOI2020] Person

A dream. The same dream. A dream I have every day. A dream with no end...... Huh... where... is this? All around are fragments falling like snowflakes. The bright light in the sky sweeps across these fragments again, shining onto the ground. These fragments are like a scarf with no end, surrounding her, and stretching behind her to the end of the world, telling pieces of shattered memories...... ...... Th-this... just now... was it a dream? Looks like I had another dream... Without noticing, it has been so long since I left this town... But... it always feels like this town... I cannot forget it... What exactly did I see just now? Why?  I always feel I need to go back once, go back to...... the place where everything began......

In her dream, there are $2m$ memory fragments, numbered $1,2,\cdots,2m$, and there are $a$ white fragments and $b$ black fragments. She vaguely remembers that she needs to choose $a$ white fragments from the memory fragments with odd indices to form a memory, and choose $b$ black fragments from the memory fragments with even indices to form a memory, and the indices of the chosen fragments are pairwise non-adjacent. She wants to know how many ways there are to choose them. That is, choose $a$ odd numbers and $b$ even numbers from $1-2m$, and the chosen numbers are pairwise non-adjacent. Since the answer may be large, she only needs the result modulo $998244353$.

**This problem has multiple test cases.** The first line contains the number of test cases $T$. The next $T$ lines each contain three integers $m, a, b$.

Output $T$ lines, each line containing one integer representing the answer.

#### Sample Explanation For the first query, there are $4$ numbers in total. Choose one number from the odd set $\{1,3\}$ and one number from the even set $\{2,4\}$. The only way to choose two non-adjacent numbers is $1,4$. For the second query, there are $8$ numbers in total. Choose $2$ numbers from the odd set $\{1,3,5,7\}$ and $1$ number from the even set $\{2,4,6,8\}$. The $3$ chosen numbers must be pairwise non-adjacent. The valid choices are: $\{1,3,6\}$, $\{1,3,8\}$, $\{1,5,8\}$, $\{1,4,7\}$, $\{3,5,8\}$, $\{2,5,7\}$. There are $6$ ways in total. The ranges of the later queries are too large, so no sample explanation is provided. #### Constraints **This problem uses bundled testdata**, with $3$ subtasks. $Subtask 1 (10\%)$: $1 \le T \le 10$, $1 \le a,b \le m \le 10$. $Subtask 2 (40\%)$: $1 \le T \le 10^6$, $1 \le a,b \le m \le 100$. $Subtask 3 (50\%)$: $1 \le T \le 10^6$, $1 \le a,b \le m \le 10^6$. For $100\%$ of the testdata, it is guaranteed that $a+b \le m$. Translated by ChatGPT 5