311238: CF1954D. Colored Balls

D. Colored Ballstime limit per test2 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

There are balls of $n$ different colors; the number of balls of the $i$-th color is $a_i$.

The balls can be combined into groups. Each group should contain at most $2$ balls, and no more than $1$ ball of each color.

Consider all $2^n$ sets of colors. For a set of colors, let's denote its value as the minimum number of groups the balls of those colors can be distributed into. For example, if there are three colors with $3$, $1$ and $7$ balls respectively, they can be combined into $7$ groups (and not less than $7$), so the value of that set of colors is $7$.

Your task is to calculate the sum of values over all $2^n$ possible sets of colors. Since the answer may be too large, print it modulo $998\,244\,353$.

Input

The first line contains a single integer $n$ ($1 \le n \le 5000$) — the number of colors.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 5000$) — the number of balls of the $i$-th color.

Additional constraint on input: the total number of balls doesn't exceed $5000$.

Output

Print a single integer — the sum of values of all $2^n$ sets of colors, taken modulo $998\,244\,353$.

ExamplesInput

3
1 1 2

Output

11

Input

1
5

Output

5

Input

4
1 3 3 7

Output

76

Note

Consider the first example. There are $8$ sets of colors:

• for the empty set, its value is $0$;
• for the set $\{1\}$, its value is $1$;
• for the set $\{2\}$, its value is $1$;
• for the set $\{3\}$, its value is $2$;
• for the set $\{1,2\}$, its value is $1$;
• for the set $\{1,3\}$, its value is $2$;
• for the set $\{2,3\}$, its value is $2$;
• for the set $\{1,2,3\}$, its value is $2$.

So, the sum of values over all $2^n$ sets of colors is $11$.

题目大意：
有n种不同颜色的球，第i种颜色的球有a_i个。球可以组合成小组，每个小组最多有2个球，且每种颜色的球最多只能有1个。考虑所有2^n种颜色组合。对于一种颜色组合，定义其值为将这些颜色的球分配到小组中的最小数量。例如，如果有三种颜色分别有3、1和7个球，它们可以组合成7个小组（不少于7个），所以这个颜色组合的值是7。任务是计算所有2^n种颜色组合的值之和。由于答案可能很大，请输出模998,244,353的结果。

输入数据格式：
第一行包含一个整数n（1≤n≤5000）——颜色的数量。
第二行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤5000）——每种颜色的球的数量。
输入数据的附加限制：球的总数不超过5000。

输出数据格式：
打印一个整数——所有2^n种颜色组合的值之和，模998,244,353的结果。

例：
输入
3
1 1 2
输出
11

输入
1
5
输出
5

输入
4
1 3 3 7
输出
76题目大意： 有n种不同颜色的球，第i种颜色的球有a_i个。球可以组合成小组，每个小组最多有2个球，且每种颜色的球最多只能有1个。考虑所有2^n种颜色组合。对于一种颜色组合，定义其值为将这些颜色的球分配到小组中的最小数量。例如，如果有三种颜色分别有3、1和7个球，它们可以组合成7个小组（不少于7个），所以这个颜色组合的值是7。任务是计算所有2^n种颜色组合的值之和。由于答案可能很大，请输出模998,244,353的结果。 输入数据格式： 第一行包含一个整数n（1≤n≤5000）——颜色的数量。 第二行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤5000）——每种颜色的球的数量。 输入数据的附加限制：球的总数不超过5000。 输出数据格式： 打印一个整数——所有2^n种颜色组合的值之和，模998,244,353的结果。 例： 输入 3 1 1 2 输出 11 输入 1 5 输出 5 输入 4 1 3 3 7 输出 76