Farm Game
Contest: CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 2300
Tags: combinatorics, games

Farmer Nhoj has brought his cows over to Farmer John's farm to play a game! FJ's farm can be modeled by a number line with walls at points $$$0$$$ and $$$l + 1$$$. On the farm, there are $$$2n$$$ cows, with $$$n$$$ of the cows belonging to FJ and the other $$$n$$$ belonging to FN. They place each of their cows at a distinct point, and no two FJ's cows nor FN's cows are adjacent. Two cows are adjacent if there are no other cows between them.

Formally, if $$$a_1, a_2, \ldots, a_n$$$ represents the positions of FJ's cows and $$$b_1, b_2, \ldots, b_n$$$ represents the positions of FN's cows, then either $$$0 < a_1 < b_1 < a_2 < b_2 < \ldots < a_n < b_n < l + 1$$$ or $$$0 < b_1 < a_1 < b_2 < a_2 < \ldots < b_n < a_n < l + 1$$$.

In one move, a farmer chooses a number $$$k$$$ $$$(1 \leq k \leq n)$$$ and a direction (left or right). Then, that farmer chooses $$$k$$$ of his cows and moves them one position towards the chosen direction. A farmer cannot move any of his cows onto the walls or onto another farmer's cow. If a farmer cannot move any cows, then that farmer loses. FJ starts the game, making the first turn.

Given $$$l$$$ and $$$n$$$, find the number of possible game configurations for Farmer John to win if both farmers play optimally. It may be the case that the game will continue indefinitely, in which no farmer wins. A configuration is different from another if there is any $$$i$$$ such that $$$a_i$$$ or $$$b_i$$$ is different. Output the answer modulo $$$998\,244\,353$$$.

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

Each test case contains two integers $$$l$$$ and $$$n$$$ ($$$2 \leq l \leq 10^6, 1 \leq n \leq \lfloor \frac{l}{2} \rfloor$$$) — the length of the number line and the number of cows each farmer will place.

It is guaranteed the sum of $$$l$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case output an integer: the number of game configurations where Farmer John wins if both farmers play optimally, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Let J denote FJ's cow, N denote FN's cow, and _ denote an empty space.

For the first test case, the two possible configurations are JN or NJ. In both cases, since FJ makes the first turn and cannot make any moves, he cannot win.

For the second case there are two possible configurations for FJ to win: N_J and J_N.

Example input:
3
2 1
3 1
420 69

Example output:
0
2
870279412

Editorial:
Consider the gaps between $$$(a_1,b_1), (a_2,b_2), ... ,(a_n,b_n)$$$. In the example below, '$$$\texttt{a}$$$' represents FJ's cow, '$$$\texttt{b}$$$' represents FN's cow, and '$$$\texttt{.}$$$' represents an empty space. The gaps are $$$[2,3]$$$.
$$$$$$\texttt{|.a..b....a...b.|}$$$$$$
When all gaps become $$$0$$$, the player who has to move loses. Consider the example below. If it's player FJ's turn, then FJ must move a cow left and FN can just move the corresponding cow left. So player FJ has to keep moving a cow left each turn until they eventually lose.
$$$$$$\texttt{|.ab.....ab.|}$$$$$$
Consider the gaps $$$g_1,g_2,...,g_n$$$. An observation is that FJ will not push a cow left and FN will not push a cow right. Suppose FJ pushes a cow left. That is equivalent to increasing some $$$g_i$$$. FN can move some cow left to decrease that same $$$g_i$$$ so nothing changes except for the fact that now FJ has less room to push cows left.
So in one move FJ will push any set of cows right and FN will push any set of cows left. In other words, when a farmer moves, they choose some non-empty subset of non-zero $$$g_i$$$ and subtract 1 from every element in the subset. The farmer that cannot do so loses.
The winner of the game is determined as follows:
1) If all $$$g_i$$$ are even, then FN wins since FN can mirror whatever move FJ does.
2) Otherwise, FJ wins since he can subtract $$$1$$$ to all odd $$$g_i$$$ in his first move to make all elements even. Then it's FN's turn and all $$$g_i$$$ are even so by the reasoning above, FJ wins.
Let's use complementary counting and determine the number of ways FN wins (which is when all $$$g_i$$$ are even). We can iterate over the sum, $$$s$$$ ($$$s$$$ is even), of all $$$g_i$$$. At each $$$s$$$, we can use stars and bars to find how many such $$$g_1,g_2,...,g_n$$$ (all $$$g_i$$$ are even) sum to $$$s$$$. Specifically, the number of ways are $$$\frac{s}{2} + n - 1 \choose n - 1$$$. The number of ways to place the cows in the available positions given the gaps will be $$$2 \cdot {l - s - n \choose n}$$$. We multiply by $$$2$$$ since we can alternate starting with either FJ's cow or FN's cow.
Finally, we subtract this result from the total number of configurations, $$$2 \cdot {l \choose 2 \cdot n}$$$, to get the number of ways FJ wins. This runs in $$$\mathcal{O}(l)$$$ time.