Sum of Circular Segment Weights

Consider a sequence of positive integers where, for every integer i, the number i appears exactly \(c_i\) times. Arrange these numbers in a sequence. Although the weight (defined below) is computed using a circular arrangement, sequences that are cyclic shifts of each other are considered different.

Place the sequence on a circle (i.e. connect the first and last elements) and partition it into several consecutive segments such that each segment consists of identical numbers and two adjacent segments have different numbers. Define the weight of the sequence as the product of the lengths of these segments. For example, consider the sequence \((1, 2, 1, 2)\): when arranged in a circle it is partitioned into two segments \([1,2]\) and \([1,2]\) if no adjacent same numbers occur, but if the same numbers appear consecutively then the segment length is larger.

Your task is to compute the sum of the weights of all sequences (i.e. all arrangements of the multiset given by \(\{1^{c_1},2^{c_2},\dots, m^{c_m}\}\)) modulo \(998244353\).

Note: Although the weight is computed using a circular arrangement, two sequences which are cyclic rotations of each other are counted as distinct. For instance, \((1,2,1,2)\) and \((2,1,2,1)\) are treated as different sequences.

Explanation of the weight: When the sequence is placed on a circle, let the boundaries between adjacent segments be at positions where consecutive numbers differ (with the convention that the first and last elements are also adjacent). If the segments have lengths \(L_1, L_2, \dots, L_k\) then the weight of the sequence is \(L_1\times L_2\times \cdots \times L_k\). In particular, if the first and last number are the same the two corresponding segments merge into one with length \(L_1+L_k\) (instead of \(L_1\) and \(L_k\) separately) for the purpose of computing the product.

inputFormat

The first line contains a single integer \(m\) (the number of distinct integers). The second line contains \(m\) space‐separated positive integers \(c_1, c_2, \dots, c_m\), where \(c_i\) denotes the count of number \(i\) in the sequence.

outputFormat

Output a single integer, the sum of weights of all sequences modulo \(998244353\).

sample

2
3 1

12