E. НОК - Непревзойдённый оракул количеств
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана последовательность $$$a$$$ длины $$$n$$$ и целое положительное число $$$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$$$ на целые числа из диапазона $$$[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$$$.

Пример
Входные данные
5
4 6
1 0 0 6
2 2
2 1
5 24
0 0 4 0 0
5 6
0 0 6 0 0
20 2000
1 0 0 0 0 14 0 0 0 0 0 0 0 0 0 514 0 0 0 0
Выходные данные
2
0
10
0
973702700
Примечание

В первом наборе входных данных есть $$$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$$$, что невозможно.