CF1954D Colored Balls

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 $ .

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 $ .

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

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 $ .