Существуют шары \(n\) различных цветов; количество шаров \(i\)-го цвета равно \(a_i\).
Шары можно объединять в группы. Каждая группа должна содержать не более \(2\) шаров и не более \(1\) шара каждого цвета.
Рассмотрим все \(2^n\) множеств цветов. Для множества цветов обозначим его значение как минимальное количество групп, на которые могут быть разделены шары этих цветов. Например, если есть три цвета с \(3\), \(1\) и \(7\) шарами соответственно, их можно объединить в \(7\) групп (и не менее \(7\)), поэтому значение этого множества цветов равно \(7\).
Ваша задача — вычислить сумму значений по всем \(2^n\) возможным множествам цветов. Поскольку ответ может быть слишком большим, выведите его по модулю \(998\,244\,353\).
Выходные данные
Выведите одно целое число — сумму значений всех \(2^n\) множеств цветов, взятую по модулю \(998\,244\,353\).
Примечание
Рассмотрим первый пример. Есть \(8\) множеств цветов:
- значение пустого множества равно \(0\);
- значение множества \(\{1\}\) равно \(1\);
- значение множества \(\{2\}\) равно \(1\);
- значение множества \(\{3\}\) равно \(2\);
- значение множества \(\{1,2\}\) равно \(1\);
- значение множества \(\{1,3\}\) равно \(2\);
- значение множества \(\{2,3\}\) равно \(2\);
- значение множества \(\{1,2,3\}\) равно \(2\).
Таким образом, сумма значений по всем \(2^n\) множествам цветов равна \(11\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 1 2
|
11
|
|
2
|
1
5
|
5
|
|
3
|
4
1 3 3 7
|
76
|