Description

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$.

Input Format

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 Format

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

6
2 1 1
4 2 1
114 5 14
1919 8 10
19260 8 17
114514 1919 810

1
6
43944630
803733835
204764788
713170605

Hint

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