Description

Several positive integers are arranged into a sequence. The number of occurrences of integer $i$ is $c_i$. For each such sequence, define its weight as follows:

Connect the head and tail of the sequence to form a circle. Divide these numbers into several adjacent segments such that each segment consists of consecutive numbers on the circle, any two segments have no elements in common, all numbers within each segment are the same, and the numbers in adjacent segments are different. Then the weight of this sequence is defined as the product of the lengths of all segments.

Compute the sum of the weights of all sequences, modulo $998244353$.

Note: Although the weight is computed on a circular arrangement, sequences that are cyclic shifts of each other are still considered different. For example, $(1,2,1,2)$ and $(2,1,2,1)$ are considered different sequences.

Input Format

Multiple lines. The first line contains a positive integer $n$, the number of distinct values.

The second line contains $n$ positive integers $c_i$, where $c_i$ is the number of occurrences of the $i$-th value.

Output Format

One line, the sum of the weights of all sequences whose occurrence counts satisfy the conditions, modulo $998244353$.

2
2 2

18

6
7 8 9 10 11 12

515320459

Hint

Sample Explanation #1:

The valid sequences are $(1,1,2,2),(1,2,1,2),(1,2,2,1),(2,1,1,2),(2,1,2,1),(2,2,1,1)$. Their weights are $4,1,4,4,1,4$, and the sum is $18$.

Constraints:

$\sum c_i \le 2\times 10^5$

$2\le n\le 2\times 10^5$

Translated by ChatGPT 5