D. Цветные шары
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Существуют шары $$$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$$$.

Примеры
Входные данные
3
1 1 2
Выходные данные
11
Входные данные
1
5
Выходные данные
5
Входные данные
4
1 3 3 7
Выходные данные
76
Примечание

Рассмотрим первый пример. Есть $$$8$$$ множеств цветов:

  • значение пустого множества равно $$$0$$$;
  • значение множества $$$\{1\}$$$ равно $$$1$$$;
  • значение множества $$$\{2\}$$$ равно $$$1$$$;
  • значение множества $$$\{3\}$$$ равно $$$2$$$;
  • значение множества $$$\{1,2\}$$$ равно $$$1$$$;
  • значение множества $$$\{1,3\}$$$ равно $$$2$$$;
  • значение множества $$$\{2,3\}$$$ равно $$$2$$$;
  • значение множества $$$\{1,2,3\}$$$ равно $$$2$$$.

Таким образом, сумма значений по всем $$$2^n$$$ множествам цветов равна $$$11$$$.