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