Sum of Unicyclic Graph Weights

We are given a complete graph (K_n) with (n) vertices. Each vertex (i) is assigned an integer weight (a_i). For any edge connecting vertices (i) and (j) (with (i \neq j)), its weight is defined as (w_{i,j} = a_i + a_j). A unicyclic spanning subgraph of (K_n) is a connected subgraph which uses exactly (n) edges (thus having exactly one cycle) and no self‐loops or multiple edges. The weight of such a subgraph is defined as [ W(G') = \prod_{e \in E'} w_e = \prod_{e\in E'} (a_i+a_j) \quad (\text{if } e \text{ connects } i \text{ and } j), ] where (E') is the set of edges of the subgraph.

Your task is to compute the sum of the weights of all unicyclic spanning subgraphs of (K_n) modulo (998244353). Two unicyclic subgraphs are considered different if there exists an edge ({i,j}) that appears in one but not in the other.

Formally, given (n) and (a_1,a_2,\dots,a_n), let (P = {(V,E')}) be the set of all subgraphs with (|V|=n) and (|E'|=n) that are connected. For each such subgraph the weight is defined as [ \prod_{e\in E'} (a_i+a_j), . ] Output the sum of these weights modulo (998244353).

inputFormat

The first line contains a single integer (n) (the number of vertices).
The second line contains (n) space‐separated integers (a_1, a_2, \dots, a_n).
(1 \le n \le 7) (note: due to the combintorial nature of the problem, (n) is small).

outputFormat

Output a single integer, the sum of the weights of all unicyclic spanning subgraphs modulo (998244353).

sample

3
1 1 1

8