CF2183E.LCM is Legendary Counting Master

You are given a sequence $a$ of length $n$ and a positive integer $m$. Each element of $a$ is an integer in the range $[0, m]$.

A sequence $a$ is considered good if and only if the following two conditions hold:

• $a_1 \lt a_2 \lt a_3 \lt \ldots \lt a_n$, and
• $\frac{1}{\operatorname{lcm}(a_1,a_2)}+\frac{1}{\operatorname{lcm}(a_2,a_3)}+\ldots+\frac{1}{\operatorname{lcm}(a_{n-1},a_n)}+\color{red}{\frac{1}{\operatorname{lcm}(a_n,a_1)}}\ge1$.$^{\text{∗}}$

You need to replace all zeros in $a$ with integers from the range $[1, m]$. Calculate the number of different ways to replace the zeros such that the resulting sequence $a$ is good.

Print the answer modulo $998\,244\,353$.

$^{\text{∗}}$The Least common multiple ($\operatorname{lcm}$) of two positive integers is the smallest positive integer that is a multiple of both. For example, $\operatorname{lcm}(2,3)=6, \operatorname{lcm}(4,6)=12$.

给你一个长度为 $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}{\operatorname{lcm}(a_{n-1},a_n)}+\color{red}{\frac{1}{\operatorname{lcm}(a_n,a_1)}}\ge1$.$^{\text{∗}}$

你需要将 $a$ 中所有 $0$ 替换为区间 $[1, m]$ 内的整数。求有多少种不同的替换方式，使得替换后得到的序列 $a$ 是好序列。

请输出答案对 $998\,244\,353$ 取模的结果。

$^{\text{∗}}$ 两个正整数的最小公倍数（$\operatorname{lcm}$）是指同时是这两个正整数的倍数的最小正整数。例如：$\operatorname{lcm}(2,3)=6$，$\operatorname{lcm}(4,6)=12$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2 \le n\le m \le 3000$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le m$).

It is guaranteed that the sum of $m$ over all test cases does not exceed $3000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output a single integer — the number of ways to complete the sequence so that it becomes good, modulo $998\,244\,353$.

对于每个测试用例，输出一个整数——使该序列变为“好”序列的补全方案数，对 $998\,244\,353$ 取模。

In the first test case, there are $2$ ways to replace the zeros such that the sequence becomes good:

• $[1, 2, 3, 6]$: The sum is $\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]$: The sum is $\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$.

In the second test case, the initial sequence is $[2, 1]$. Since $2 \not \lt 1$, the strictly increasing condition is not met, so the answer is $0$.

In the fourth test case, the sequence is fixed to be $[0, 0, 6, 0, 0]$ with $m=6$. The third element is $6$. Since the sequence must be strictly increasing and elements cannot exceed $6$, we would need $6 \lt a_4 \lt a_5 \le 6$, which is impossible.

在第一个测试用例中，有 $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$，这是不可能的。