Again Counting Arrays (Hard Version)
Contest: Codeforces Round 942 (Div. 1)
Difficulty rating: 3500
Tags: combinatorics, dp, math

This is the hard version of the problem. The differences between the two versions are the constraints on $$$n, m, b_0$$$ and the time limit. You can make hacks only if both versions are solved.

Little R has counted many sets before, and now she decides to count arrays.

Little R thinks an array $$$b_0, \ldots, b_n$$$ consisting of non-negative integers is continuous if and only if, for each $$$i$$$ such that $$$1 \leq i \leq n$$$, $$$\lvert b_i - b_{i-1} \rvert = 1$$$ is satisfied. She likes continuity, so she only wants to generate continuous arrays.

If Little R is given $$$b_0$$$ and $$$a_1, \ldots, a_n$$$, she will try to generate a non-negative continuous array $$$b$$$, which has no similarity with $$$a$$$. More formally, for all $$$1 \leq i \leq n$$$, $$$a_i \neq b_i$$$ holds.

However, Little R does not have any array $$$a$$$. Instead, she gives you $$$n$$$, $$$m$$$ and $$$b_0$$$. She wants to count the different integer arrays $$$a_1, \ldots, a_n$$$ satisfying:

- $$$1 \leq a_i \leq m$$$;
- At least one non-negative continuous array $$$b_0, \ldots, b_n$$$ can be generated.

Note that $$$b_i \geq 0$$$, but the $$$b_i$$$ can be arbitrarily large.

Since the actual answer may be enormous, please just tell her the answer modulo $$$998\,244\,353$$$.

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

The first and only line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$b_0$$$ ($$$1 \leq n \leq 2 \cdot 10^6$$$, $$$1 \leq m \leq 2 \cdot 10^6$$$, $$$0 \leq b_0 \leq 2\cdot 10^6$$$) — the length of the array $$$a_1, \ldots, a_n$$$, the maximum possible element in $$$a_1, \ldots, a_n$$$, and the initial element of the array $$$b_0, \ldots, b_n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceeds $$$10^7$$$.

Output format:
For each test case, output a single line containing an integer: the number of different arrays $$$a_1, \ldots, a_n$$$ satisfying the conditions, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first test case, for example, when $$$a = [1, 2, 1]$$$, we can set $$$b = [1, 0, 1, 0]$$$. When $$$a = [1, 1, 2]$$$, we can set $$$b = [1, 2, 3, 4]$$$. In total, there are $$$6$$$ valid choices of $$$a_1, \ldots, a_n$$$: in fact, it can be proved that only $$$a = [2, 1, 1]$$$ and $$$a = [2, 1, 2]$$$ make it impossible to construct a non-negative continuous $$$b_0, \ldots, b_n$$$, so the answer is $$$2^3 - 2 = 6$$$.

Example input:
6
3 2 1
5 5 3
13 4 1
100 6 7
100 11 3
1000 424 132

Example output:
6
3120
59982228
943484039
644081522
501350342

Editorial:
The definition of the function $$$f$$$ is the same as that in G1 editorial. Please read that first.
Consider the process of the reflection method. We don't need to enumerate the place from where the contribution is $$$0$$$. We can just consider the contribution of each path. Note that each step is either $$$x\gets x+1$$$ or $$$y\gets y\pm 1$$$ here, instead of rotating it by $$$45^\circ$$$.
Denote $$$\tt X$$$ as touching $$$y=m$$$ and $$$\tt Y$$$ as touching $$$y=-1$$$. Then we need to calculate the paths that either are empty or begin with $$$\tt X$$$. We can write down the equation of the answer: $$$f(\varnothing) - f(\texttt{Y}) + f(\texttt{XY}) - f(\texttt{YXY}) + f(\texttt{XYXY}) - \dots$$$.
Let's consider how to calculate $$$f(\varnothing)$$$. We can represent it as:
$$$$$$\sum_{x=b-n}^{b+n} (m - 1)^{(x - b + n)/2} {n \choose (x - b + n) / 2}$$$$$$
A point $$$(n,k)$$$ will be flipped at $$$(n,-2-k)$$$ after $$$\tt Y$$$, and will be flipped at $$$(n,2m+2+k)$$$ after $$$\tt XY$$$. So we only need to calculate:
$$$$$$\sum_{p \geq 0} \sum_{x = b - n}^{b + n} (m - 1)^{(x - b + n)/2} {n \choose (x - b + n + p(2m + 2))/2}\\-\sum_{p \geq 0} \sum_{x =b-n}^{b+n} (m - 1)^{(x - b + n)/2} {n \choose (-2 - x - b + n + p(2m + 2))/2}$$$$$$
There are still some small problems. The reflection method points out that, if the targeted point $$$T$$$ is between the two lines, then we can keep reflecting $$$T$$$ and get $$$T'$$$, every path to $$$T'$$$ bijects to a path to $$$T$$$ which contains reflections. But what if $$$T$$$ is not between the two lines? We must solve a problem — the path to $$$T'$$$ maybe doesn't touch the two lines at all and there won't be reflections, and these should not be included in the answer. So we should consider $$$x\ge 0$$$ part and $$$x\le -1$$$ part separately. The above equation is for the $$$x\ge 0$$$ part. For the $$$x\le -1$$$ part, we are sure that $$$\tt Y$$$ will occur, so the path should begin with $$$\tt X$$$, then it will be $$$f(\texttt{X})-f(\texttt{YX})+f(\texttt{XYX})-\dots$$$ and can be calculated in the same way.
The combinatorial number is hard to deal with, so let's maintain a coefficient sequence $$$c_0\cdots c_n$$$, that the answer is $$$\sum_i c_i\binom{n}{i}$$$. The sequence $$$c_i$$$ can be calculated using differentiation.
Time Complexity: $$$\mathcal O(n)$$$.