彩色球

• 时间限制：2 秒
• 内存限制：1024 MiB

题目描述

有 $n$ 种不同颜色的球，第 $i$ 种颜色有 $a_i$ 个球。

这些球可以被分成若干组。每组至多包含 $2$ 个球，并且同一组内不能出现两个颜色相同的球。

考虑全部 $2^n$ 个颜色集合。对于一个颜色集合，只使用这些颜色的全部球，定义该集合的价值为所需的最少组数。例如，若选中的三种颜色分别有 $3$、$1$、$7$ 个球，则至少需要 $7$ 组，并且可以恰好分成 $7$ 组，所以这个集合的价值为 $7$。

求全部 $2^n$ 个颜色集合的价值之和。答案对 $998244353$ 取模。

输入格式

第一行包含一个整数 $n$，表示颜色数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 表示第 $i$ 种颜色的球数。

输出格式

输出一个整数，表示全部颜色集合的价值之和对 $998244353$ 取模后的结果。

样例输入 1

3
1 1 2

样例输出 1

11

样例输入 2

1
5

样例输出 2

5

样例输入 3

4
1 3 3 7

样例输出 3

76

样例说明

对于第一个样例，$8$ 个集合的价值依次为 $0,1,1,2,1,2,2,2$，总和为 $11$。

数据范围

对于所有测试数据：

• $1\le n\le5000$；
• $1\le a_i\le5000$；
• $\sum_{i=1}^{n}a_i\le5000$。