Дан последовательный ряд из $n$ чисел. Сяо Мин собирается выполнить над ним $n - 1$ операцию: каждый раз он равновероятно выбирает пару соседних чисел и заменяет их на разность левого и правого чисел. После первой операции ряд превращается в последовательность из $n - 1$ числа, после второй — из $n - 2$ чисел, и так далее.

Сяо Мину интересно узнать математическое ожидание значения последнего оставшегося числа после выполнения $n - 1$ операции. Помогите ему. Пусть ответ равен $p/q$. Вам необходимо вывести результат $p \times q^{998244351} \pmod{998244353}$. В задаче несколько наборов входных данных.

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

В первой строке вводится целое положительное число $T$, количество запросов. Далее следуют $T$ наборов входных данных. В каждом наборе: Первая строка содержит целое положительное число $n$ — длину массива. Вторая строка содержит $n$ целых чисел $a_i$ — элементы последовательности.

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

Выведите $T$ строк, по одному числу в каждой строке, соответствующих ответу на каждый запрос.

Примеры

Примеры 1

2
2
2 1
3
3 2 1

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

1
1

Примечание 1

Для второго запроса: если сначала выбрать первые два числа, ответ будет $(3 - 2) - 1 = 0$; если сначала выбрать последние два числа, ответ будет $3 - (2 - 1) = 2$. Таким образом, математическое ожидание равно $2/2 = 1$.

Примеры 2

См. файлы aminusb/aminusb2.in и aminusb/aminusb2.ans в директории участника.

Подзадачи

Для 100% данных гарантируется $T = 5$, $1 \le n \le 10^5$, $0 \le a_i < 998244353$.