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

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 $ .

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 $ .

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< 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 < a_4 < a_5 \le 6 $ , which is impossible.