G. Точка остановки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ размера $$$n$$$ ($$$1 \leq a_i \leq m$$$).

Рассмотрим все $$$m!$$$ перестановок массива $$$[1, 2, \ldots, m]$$$. Для любой перестановки $$$p$$$ определим массив $$$b_p$$$ как массив, полученный конкатенацией массива $$$a$$$ и перестановки $$$p$$$. Более формально, $$$b_p = [a_1, a_2, \ldots, a_n, p_1, p_2, \ldots, p_m]$$$.

Пусть $$$f(i)$$$ обозначает количество перестановок $$$p$$$, таких что массив $$$b_p$$$ содержит ровно $$$i$$$ палиндромных$$$^{\text{∗}}$$$ подмассивов чётной длины.

Ваша задача — вычислить $$$$$$ \sum_{i=0}^{10^{100}} f(i)^{i+1}.$$$$$$

Так как ответ может быть большим, его следует вычислить по модулю $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$Массив $$$[c_1, c_2, \ldots, c_k]$$$ называется палиндромным, если $$$c_i = c_{k+1-i}$$$ для всех $$$1 \le i \le k$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le m \le n \le 10^6$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — элементы массива.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число на отдельной строке — $$$ \sum_{i=0}^{10^{100}} f(i)^{i+1}$$$ по модулю $$$998\,244\,353$$$.

Пример
Входные данные
5
4 3
3 1 2 1
1 1
1
9 4
4 1 2 1 3 3 1 2 1
6 3
1 1 3 1 1 1
10 6
4 4 1 2 1 3 3 1 2 1
Выходные данные
6
1
1248960
258
14006753
Примечание

В первом наборе входных данных $$$n=4$$$, $$$m=3$$$, и $$$a=[3,1,2,1]$$$.

Перечислим все перестановки и посчитаем количество палиндромных подмассивов чётной длины:

  • $$$p_1 = [1, 2, 3]$$$, $$$b_{p_1} = [3, 1, 2, 1, 1, 2, 3]$$$, и количество палиндромных подмассивов чётной длины равно $$$2$$$.
  • $$$p_2 = [1, 3, 2]$$$, $$$b_{p_2} = [3, 1, 2, 1, 1, 3, 2]$$$, и количество палиндромных подмассивов чётной длины равно $$$1$$$.
  • $$$p_3 = [2, 1, 3]$$$, $$$b_{p_3} = [3, 1, 2, 1, 2, 1, 3]$$$, и количество палиндромных подмассивов чётной длины равно $$$0$$$.
  • $$$p_4 = [2, 3, 1]$$$, $$$b_{p_4} = [3, 1, 2, 1, 2, 3, 1]$$$, и количество палиндромных подмассивов чётной длины равно $$$0$$$.
  • $$$p_5 = [3, 1, 2]$$$, $$$b_{p_5} = [3, 1, 2, 1, 3, 1, 2]$$$, и количество палиндромных подмассивов чётной длины равно $$$0$$$.
  • $$$p_6 = [3, 2, 1]$$$, $$$b_{p_6} = [3, 1, 2, 1, 3, 2, 1]$$$, и количество палиндромных подмассивов чётной длины равно $$$0$$$.

Таким образом, $$$f(0) = 4$$$, $$$f(1) = 1$$$, $$$f(2) = 1$$$, а $$$f(i) = 0$$$ для всех $$$i \gt 2$$$. Следовательно, ответ равен $$$4^1 + 1^2 + 1^3 = 6$$$.