E2. Again Counting Arrays (Hard Version) 再次统计数组（困难版）

时间限制：$3$ 秒 内存限制：$512$ 兆字节

这是本题的困难版本。两个版本的区别在于对 $n,m,b_0$ 的限制与时间限制。只有同时通过两个版本，才能进行 hack。

小 R 以前统计过很多集合，现在她想来统计数组。

小 R 认为一个由非负整数构成的数组 $b_0,b_1,\dots,b_n$ 是连续的，当且仅当： 对所有满足 $1\le i\le n$ 的 $i$，都有 $\boldsymbol{|b_i - b_{i-1}|=1}$。 她喜欢连续性，因此只想生成连续数组。

如果给定 $b_0$ 和数组 $a_1,\dots,a_n$，小 R 会尝试生成一个非负连续数组 $b$，满足 $b$ 与 $a$ 完全不冲突。 形式化地说：对所有 $1\le i\le n$，都必须满足 $\boldsymbol{a_i\neq b_i}$。

然而小 R 并没有给出数组 $a$，而是给了你 $n,m,b_0$。 你需要统计有多少个不同的数组 $a_1,\dots,a_n$ 满足：

1. $\boldsymbol{1\le a_i\le m}$
2. 至少存在一个非负连续数组 $b_0,\dots,b_n$ 满足上述条件

注意：$b_i\ge 0$，但 $b_i$ 可以无限大。

答案可能极大，请对 $\boldsymbol{998244353}$ 取模输出。

输入格式

多组测试用例。 第一行一个整数 $t$（$1\le t\le 10^4$），表示测试用例组数。

每组测试用例一行，包含三个整数：

• $n$：数组 $a$ 的长度，$1\le n\le 2\times 10^6$
• $m$：$a_i$ 的最大值，$1\le m\le 2\times 10^6$
• $b_0$：数组 $b$ 的初始值，$0\le b_0\le 2\times 10^6$

保证所有测试用例的 $\boldsymbol{\sum n\le 10^7}$。

输出格式

对每组测试用例，输出一个整数，表示合法数组 $a$ 的数量，对 $998244353$ 取模。

样例输入

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

样例输出

6
3120
59982228
943484039
644081522
501350342

样例解释

第一个样例： 总共有 $2^3=8$ 种 $a$ 数组。 其中只有 $a=[2,1,1]$ 和 $a=[2,1,2]$ 是非法的，无法构造出合法 $b$。 因此答案为 $8-2=6$。