CF1967E2.Again Counting Arrays (Hard Version)

这是本问题的困难版，两个版本的区别在于 $n$、$m$ 和 $b_0$ 的具体限制，以及时间限制。只有当你解决了两个版本的问题后，你才能进行 hack。

小 R 之前数过很多集合，现在她打算数数组。

在小 R 看来，一个由非负数组成的数组 $b_0, \ldots, b_n$ 是否连续有一个判定条件：对于每个满足 $1 \leq i \leq n$ 的位置 $i$，需要满足 $\lvert b_i - b_{i-1} \rvert = 1$。小 R 特别偏好连续的数组，因此她只想生成这样的连续数组。

如果给定起始元素 $b_0$ 和数组 $a_1, \ldots, a_n$，小 R 会尝试生成一个与数组 $a$ 无相似性的非负连续数组 $b$。更具体地说，对于所有的 $1 \leq i \leq n$，都需要满足 $a_i \neq b_i$。

但现在，小 R 没有数组 $a$。相反，她给了你 $n$、$m$ 和 $b_0$。她希望找出符合下列条件的不同整数数组 $a_1, \ldots, a_n$ 的数目：

• 每个元素 $a_i$ 满足 $1 \leq a_i \leq m$；
• 至少能生成一个符合条件的非负连续数组 $b_0, \ldots, b_n$。

请注意，虽然 $b_i \geq 0$，但 $b_i$ 可以不受限制地大。

考虑到最终答案可能非常巨大，请输出答案对 $998\,244\,353$ 取模后的结果。

输入包含多组测试用例。第一行是测试用例的数量 $t\ (1 \leq t \leq 10^4)$。接下来是各个测试用例的详细描述。

每个测试用例的输入在一行中，包含三个整数 $n$、$m$ 和 $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$），分别代表数组 $a_1, \ldots, a_n$ 的长度，它们最大可能的值，以及数组 $b_0, \ldots, b_n$ 的起始元素。

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

对于每个测试用例，输出一个整数，表示符合条件的不同数组 $a_1, \ldots, a_n$ 的数目，并对 $998\,244\,353$ 取模。

举个例子，在第一个测试用例中，当 $a = [1, 2, 1]$ 时，可以设置 $b = [1, 0, 1, 0]$；当 $a = [1, 1, 2]$ 时，可以设置 $b = [1, 2, 3, 4]$。总共有 $6$ 种有效的 $a_1, \ldots, a_n$，事实上，只有 $a = [2, 1, 1]$ 和 $a = [2, 1, 2]$ 这两种情况下，我们无法构造出这样一个非负连续的 $b_0, \ldots, b_n$，所以答案是 $2^3 - 2 = 6$。

本翻译由 AI 自动生成