CF1967E1.Again Counting Arrays (Easy Version)

这是该问题的简单版本。两个版本的区别在于 $n, m, b_0$ 的约束条件和时间限制。只有在两个版本都解决后才能进行 hack。

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

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

如果小 R 给定了 $b_0$ 和 $a_1, \ldots, a_n$，她会尝试生成一个非负的连续数组 $b$，并且 $b$ 与 $a$ 没有相似之处。更正式地说，对于所有 $1 \leq i \leq n$，都有 $a_i \neq b_i$。

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

• $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^5$，$1 \leq m \leq 2 \cdot 10^5$，$0 \leq b_0 \leq 2\cdot 10^5$）——数组 $a_1, \ldots, a_n$ 的长度、$a_1, \ldots, a_n$ 的最大可能元素，以及数组 $b_0, \ldots, b_n$ 的初始元素。

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

对于每个测试用例，输出一行一个整数，表示满足条件的不同数组 $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$。

由 ChatGPT 4.1 翻译