给定一个长度为 $$$n$$$ 的序列 $$$a$$$ 和一个正整数 $$$m$$$。 $$$a$$$ 的每个元素都是 $$$[0, m]$$$ 范围内的整数。
考虑序列 $$$a$$$ 好 当且仅当以下两个条件成立:
- $$$a_1 \lt a_2 \lt a_3 \lt \ldots \lt a_n$$$,并且
- $$$\frac{1}{\operatorname{lcm}(a_1,a_2)}+\frac{1}{\operatorname{lcm}(a_2,a_3)}+\ldots+\frac{1}{\opera名称{lcm}(a_{n-1},a_n)}+\color{red}{\frac{1}{\operatorname{lcm}(a_n,a_1)}}\ge1$$$.$$$^{\text{*}}$$$
您需要将 $$$a$$$ 中的所有零替换为 $$$[1, m]$$$ 范围内的整数。计算替换零的不同方法的数量,使得结果序列 $$$a$$$ 为 好.
打印以 $$$998\,244\,353$$$ 为模的答案。
$$$^{\text{*}}$$$两个正整数的最小公倍数 ($$$\operatorname{lcm}$$$) 是两者的倍数的最小正整数。例如,$$$\operatorname{lcm}(2,3)=6,\operatorname{lcm}(4,6)=12$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n\le m \le 3000$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le m$$$)。
保证所有测试用例的 $$$m$$$ 总和不超过 $$$3000$$$。
输出
对于每个测试用例,输出一个整数 - 完成序列以使其变得良好的方法数量,以 $$$998\,244\,353$$$ 为模。
示例
输入复制
54 61 0 0 62 22 15 240 0 4 0 05 60 0 6 0 020 20001 0 0 0 0 14 0 0 0 0 0 0 0 0 0 514 0 0 0 0
输出复制
20100973702700
注意
在第一个测试用例中,有 $$$2$$$ 方法来替换零,以使序列变得良好:
- $$$[1, 2, 3, 6]$$$:总和为 $$$\frac{1}{\operatorname{lcm}(1, 2)} + \frac{1}{\operatorname{lcm}(2, 3)} + \frac{1}{\operatorname{lcm}(3, 6)} + \frac{1}{\operatorname{lcm}(6, 1)} = \frac{1}{2} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} = 1$$$。
- $$$[1, 2, 4, 6]$$$:总和为 $$$\frac{1}{\operatorname{lcm}(1, 2)} + \frac{1}{\operatorname{lcm}(2, 4)} + \frac{1}{\operatorname{lcm}(4, 6)} + \frac{1}{\operatorname{lcm}(6, 1)} = \frac{1}{2} + \frac{1}{4} + \frac{1}{12} + \frac{1}{6} = 1$$$。
在第二个测试用例中,初始序列是 $$$[2, 1]$$$。由于$$$2 \not \lt 1$$$,不满足严格递增条件,所以答案是$$$0$$$。
在第四个测试用例中,序列固定为 $$$[0, 0, 6, 0, 0]$$$,其中 $$$m=6$$$。第三个元素是$$$6$$$。由于序列必须严格递增,并且元素不能超过 $$$6$$$,因此我们需要 $$$6 \lt a_4 \lt a_5 \le 6$$$,这是不可能的。