A96796.颜色配对

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

这些球可以被分成若干组。每组最多包含 $2$ 个球，并且每组中每种颜色的球最多只能出现 $1$ 个（也就是说：两球一组时必须是两种不同颜色）。

考虑所有 $2^n$ 种颜色集合。对某个颜色集合，只使用集合内这些颜色的球，把它们分组所需的最少组数定义为这个集合的值。

你的任务是计算所有 $2^n$ 个颜色集合的值之和。由于答案可能很大，请输出对 $998244353$ 取模的结果。

第一行包含一个整数 $n$，满足 $1 \le n \le 5000$。
第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，满足 $1 \le a_i \le 5000$。
额外保证：$\sum_{i=1}^n a_i \le 5000$。

输出一个整数，表示所有 $2^n$ 种颜色集合的值之和对 $998244353$ 取模的结果。

样例解释

样例 #1

输入：$n=3$，$a=[1,1,2]$。共有 $2^3=8$ 个颜色集合（把第 $i$ 种颜色是否选入当作开关）：

• 空集：没有球，值为 $0$
• $\{1\}$：只有 $1$ 个球，最少 $1$ 组，值为 $1$
• $\{2\}$：只有 $1$ 个球，最少 $1$ 组，值为 $1$
• $\{3\}$：只有 $2$ 个同色球，不能放同一组，只能分成 $2$ 组，值为 $2$
• $\{1,2\}$：两种颜色各 $1$ 个，可以两球一组，最少 $1$ 组，值为 $1$
• $\{1,3\}$：共有 $3$ 个球，其中最大单色数量为 $2$，最少组数为 $\max(2,\lceil 3/2\rceil)=2$，值为 $2$
• $\{2,3\}$：同理，值为 $2$
• $\{1,2,3\}$：共有 $4$ 个球，最大单色数量为 $2$，最少组数为 $\max(2,\lceil 4/2\rceil)=2$，值为 $2$

总和为 $0+1+1+2+1+2+2+2=11$。

样例 #2

输入：$n=1$，$a=[5]$。
只有两个颜色集合：空集值为 $0$，$\{1\}$ 有 $5$ 个同色球，必须分成 $5$ 组，和值为 $5$。

样例 #3

输入：$n=4$，$a=[1,3,3,7]$。
对任意选择的颜色集合，设总球数为 $T$，其中最大单色数量为 $M$，则最少组数为 $\max(M,\lceil T/2\rceil)$。把所有 $2^4$ 个集合的这个值加起来，得到输出 $76$。