这是问题的困难版本。两个版本之间的区别在于对 $n, m, b_0$ 的限制以及时间限制。只有当两个版本都解决时，你才能进行 hack。

小 R 以前数过很多集合，现在她决定来数数组。

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

如果给小 R $b_0$ 和 $a_1, \dots, a_n$，她会尝试生成一个非负连续数组 $b$，该数组与 $a$ 不相似。更正式地，对于所有 $1 \le i \le n$，满足 $a_i \neq b_i$。

然而，小 R 没有任何数组 $a$。相反，她给你 $n, m$ 和 $b_0$。她想统计满足以下条件的不同整数数组 $a_1, \dots, a_n$ 的数量：

• $1 \le a_i \le m$；
• 至少可以生成一个满足上述条件的非负连续数组 $b_0, \dots, b_n$。

注意 $b_i \ge 0$，但 $b_i$ 可以任意大。

由于实际答案可能非常大，请告诉她答案模 $998\,244\,353$ 的结果。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是测试用例的描述。

每个测试用例的第一行也是唯一的一行包含三个整数 $n, m$ 和 $b_0$（$1 \le n \le 2 \cdot 10^6$，$1 \le m \le 2 \cdot 10^6$，$0 \le b_0 \le 2 \cdot 10^6$）—— 分别表示数组 $a_1, \dots, a_n$ 的长度、数组 $a_1, \dots, a_n$ 中元素的最大可能值，以及数组 $b_0, \dots, b_n$ 的初始元素。

保证所有测试用例中 $n$ 的总和不超过 $10^7$。

输出格式

对于每个测试用例，输出一行包含一个整数：满足条件的不同的数组 $a_1, \dots, a_n$ 的数量，模 $998\,244\,353$。

样例

输入格式 1

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

输出格式 1

6
3120
59982228
943484039
644081522
501350342

说明

例如在第一个测试用例中，当 $a = [1, 2, 1]$ 时，我们可以设置 $b = [1, 0, 1, 0]$。当 $a = [1, 1, 2]$ 时，我们可以设置 $b = [1, 2, 3, 4]$。

总共有 $6$ 种合法的 $a_1, \dots, a_n$ 选择：事实上，可以证明只有 $a = [2, 1, 1]$ 和 $a = [2, 1, 2]$ 使得无法构造出非负连续的 $b_0, \dots, b_n$，因此答案为 $2^3 - 2 = 6$。