Maximum Weighted Even Subsequences

Given a sequence of length (n), we define the weight of a sequence of length (p) (with (p \ge 2)) as follows. First, consider any permutation of the sequence under the constraint that its first element equals the minimum element among all its elements. Then the weight is defined as the maximum possible value of [ \sum_{i=1}^{p-1} (a_{i+1} - a_i)^2 ] when computed over all valid rearrangements.

Now, given an array of (n) integers, your task is to compute the sum of weights over all non-empty subsequences (not necessarily contiguous) of even length (i.e. length 2, 4, 6, …) from the given sequence. Since the answer can be large, output the result modulo (998244353).

Note: For a given subsequence, one way to achieve the maximum weight is as follows. Let (x_0, x_1, \dots, x_{p-1}) be the sorted order (in increasing order) of the subsequence. Then choose the permutation: [ a_0 = x_0,\quad a_1 = x_{p-1},\quad a_2 = x_1,\quad a_3 = x_{p-2},\quad a_4 = x_2,\quad a_5 = x_{p-3}, \dots ] The weight is then computed as [ (x_{p-1} - x_0)^2 + \sum_{j=1}^{\frac{p}{2}-1} \Bigl[(x_{p-1} - x_j)^2 + (x_{p-1-j} - x_j)^2\Bigr]. ] It can be shown that this arrangement yields the maximum sum of squared differences under the given constraint.

inputFormat

The input consists of two lines. The first line contains an integer (n) ((1 \le n \le 15)). The second line contains (n) integers representing the sequence.

outputFormat

Output a single integer—the sum of weights of all even‑length non-empty subsequences modulo (998244353).

sample

2
1 3

4