Предположим, что мы разбиваем элементы массива \(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\).
Выходные данные
Для каждого набора входных данных выведите ответ по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных мы должны рассмотреть семь подпоследовательностей:
- \([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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|