D. Colored Ballstime limit per test2 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputThere 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.InputThe 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.OutputPrint a single integer — the sum of values of all 2^n sets of colors, taken modulo 998\,244\,353.ExamplesInput
31 1 2Output
11
Input
15Output
5
Input
41 3 3 7Output
76
NoteConsider 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.
31 1 2
11 
['combinatorics', 'dp', 'math', 'sortings', '*1800']