E. MEXимизируйте счёт
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Предположим, что мы разбиваем элементы массива $$$b$$$ на $$$k$$$ непустых мультимножеств $$$S_1, S_2, \ldots, S_k$$$, где $$$k$$$ — произвольное целое положительное число. Определим счёт $$$b$$$ как максимальное значение $$$\operatorname{MEX}(S_1)$$$$$$^{\text{∗}}$$$$$$ + \operatorname{MEX}(S_2) + \ldots + \operatorname{MEX}(S_k)$$$ среди всех возможных разбиений $$$b$$$ для любого целого числа $$$k$$$.

Вашему завистнику дан массив $$$a$$$ длины $$$n$$$. Поскольку он знает, что вычислить счёт массива $$$a$$$ для вас слишком просто, он просит вас вычислить сумму счётов всех $$$2^n - 1$$$ непустых подпоследовательностей массива $$$a$$$.$$$^{\text{†}}$$$ Поскольку ответ может быть очень большим, выведите его по модулю $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$$$$\operatorname{MEX}$$$ набора целых чисел $$$c_1, c_2, \ldots, c_k$$$ определяется как наименьшее неотрицательное целое число $$$x$$$, которое не встречается в наборе $$$c$$$. Например, $$$\operatorname{MEX}([0,1,2,2]) = 3$$$ и $$$\operatorname{MEX}([1,2,2]) = 0$$$

$$$^{\text{†}}$$$Последовательность $$$x$$$ является подпоследовательностью последовательности $$$y$$$, если $$$x$$$ можно получить из $$$y$$$, удалив несколько (возможно, ноль или все) элементов.

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

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

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — длина $$$a$$$.

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

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

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

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

Пример
Входные данные
4
3
0 0 1
4
0 0 1 1
5
0 0 1 2 2
4
1 1 1 1
Выходные данные
11
26
53
0
Примечание

В первом наборе входных данных мы должны рассмотреть семь подпоследовательностей:

  • $$$[0]$$$: Счёт равен $$$1$$$.
  • $$$[0]$$$: Счёт равен $$$1$$$.
  • $$$[1]$$$: Счёт равен $$$0$$$.
  • $$$[0,0]$$$: Счёт равен $$$2$$$.
  • $$$[0,1]$$$: Счёт равен $$$2$$$.
  • $$$[0,1]$$$: Счёт равен $$$2$$$.
  • $$$[0,0,1]$$$: Счёт равен $$$3$$$.
Ответ для первого набора входных данных составляет $$$1+1+2+2+2+3=11$$$.

В последнем наборе входных данных все подпоследовательности имеют счёт $$$0$$$.