F. Кто станет свидетелем конца?
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перед своим последним вылетом Ктолли задает Виллему три вопроса.

Третий из них звучит так: когда наконец наступит конец, кто останется, чтобы стать его свидетелем?

Виллем не может ответить ей напрямую. Вместо этого он рисует на доске круг, называя его «кольцом всех вещей», и записывает $$$n$$$ пронумерованных целых чисел $$$a_1,a_2,\ldots,a_n$$$. Каждый возможный порядок вокруг кольца описывает свой путь, по которому мир может прийти к концу.

Рассмотрим перестановку $$$p_1,p_2,\ldots,p_n$$$ целых чисел от $$$1$$$ до $$$n$$$. Расположим соответствующие числа на окружности в этом порядке. Вес полученного кругового расположения равен

$$$$$$ \prod_{i=1}^{n}(a_{p_i}+a_{p_{i+1}}), $$$$$$

где $$$p_{n+1}=p_1$$$.

Две перестановки описывают одно и то же круговое расположение, если одну из них можно получить из другой путём циклического сдвига. Обращение расположения не делает его тем же самым; иными словами, зеркально отражённые расположения считаются разными, если они не совпадают также после циклического сдвига.

Найдите сумму весов всех различных круговых расположений. Поскольку ответ может быть большим, выведите его по модулю $$$998\,244\,353$$$.

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

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

В первой строке каждого набора входных данных содержится одно целое число $$$n$$$ ($$$3 \le n \le 2\cdot 10^5$$$) — количество чисел.

Во второй строке содержатся $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \lt 998\,244\,353$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — сумму весов всех различных круговых расположений, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
3
3
1 2 3
6
0 1 0 1 0 1
10
114514 1919810 350234 11831 314159265 271828182 123456789 998244352 5201314 23333333
Выходные данные
120
12
265885269
Примечание

В первом наборе входных данных существует два различных круговых расположения. Их можно представить перестановками $$$[1,2,3]$$$ и $$$[1,3,2]$$$. У обоих вес равен

$$$$$$ (1+2)(2+3)(3+1)=60, $$$$$$

поэтому ответ равен $$$120$$$.

Во втором наборе входных данных расположение имеет ненулевой вес только в том случае, если нули и единицы чередуются по кругу. Существует

$$$$$$ \frac{2\cdot3!\cdot3!}{6}=12 $$$$$$

таких круговых расположений: множитель $$$2$$$ определяет, начинается ли расположение с нуля или с единицы, а деление на $$$6$$$ выделяет циклические сдвиги. Каждое из этих расположений имеет вес $$$1$$$. Все остальные расположения имеют вес $$$0$$$, поэтому ответ равен $$$12$$$.