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

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

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