这是问题的简单版本。两个版本的区别在于$$$n、m、b_0$$$ 的约束和时间限制。只有两个版本都解决了,你才能进行黑客攻击。
小R之前已经数过很多组了,现在她决定数数组。
小R认为由非负整数组成的数组 $$$b_0, \ldots, b_n$$$ 是连续的,当且仅当对于每个 $$$i$$$ 满足 $$$1 \leq i \leq n$$$, $$$\lvert b_i - b_{i-1} \rvert = 1$$$ 。她喜欢连续性,所以她只想生成连续的数组。
如果给小R$$$b_0$$$和$$$a_1,\ldots,a_n$$$,她会尝试生成一个非负连续数组$$$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$$$。
示例
输入 #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]$$$。 $$$a_1, \ldots, a_n$$$总共有$$$6$$$个有效选择:事实上,可以证明,只有$$$a = [2, 1, 1]$$$和$$$a = [2, 1, 2]$$$无法构造非负连续$$$b_0, \ldots, b_n$$$,所以答案是$$$2^3 - 2 = 6$$$。