Avoiding Balanced Prefixes and Suffixes

You are given balls of n different colors. The colors are numbered from \(1\) to \(n\) and for each \(i\) the number of balls of color \(i\) is given by \(a_i\). You are to arrange all the balls in a sequence (a permutation of the multiset) such that no non‐empty prefix or non‐empty suffix of the sequence is balanced.

A segment (prefix or suffix) is defined to be balanced if and only if all n colors occur the same number of times in it. In other words, a prefix (or suffix) of length \(m\cdot n\) (for some positive integer \(m\)) is balanced if every color appears exactly \(m\) times within it.

Note that the prefix (or suffix) of length \(len\) is the first (or last) \(len\) balls of the sequence, where \(len\ge 1\). Two sequences are considered essentially different if there exists at least one position where the colors differ.

Your task is to compute the number of essentially different sequences that satisfy the above condition, modulo \(998{,}244{,}353\). (In particular, if all \(a_i\)’s are equal then the entire sequence is balanced and the answer is 0.)

Important observations:

1. A balanced prefix (or suffix) must have a length that is a multiple of \(n\); i.e. of the form \(m\cdot n\) for some positive integer \(m\).
2. If the counts \(a_1,a_2,\dots,a_n\) are not all equal then the full sequence is not balanced.
3. It can be shown that the answer can be expressed in closed‐form. Let the total number of balls be \(T=\sum_{i=1}^{n}a_i\) and the total number of arrangements (ignoring the extra condition) is given by the multinomial coefficient \[ \frac{T!}{a_1!\,a_2!\,\cdots\,a_n!}. \] Moreover, if \(m=\min\{a_i\}\) and the minimum value appears exactly \(k\) times then one may prove that the final answer is:
   
   \[ \text{answer} = \begin{cases}\;0,&\text{if all }a_i\text{ are equal},\\[1mm] \frac{T!}{a_1!\,a_2!\,\cdots\,a_n!},&\text{if } k\ge2,\\[1mm] \frac{T!}{a_1!\,a_2!\,\cdots\,a_n!}\cdot\frac{(\,(\min_{\;a_i>m}a_i - m - 1)\;)}{(\min_{\;a_i>m}a_i - m)},&\text{if } k=1.\end{cases} \]
   (A full combinatorial justification is omitted.)

By convention, two sequences are considered different if they differ in at least one position.

inputFormat

The first line contains a single integer \(n\) (the number of colors).
The second line contains \(n\) positive integers \(a_1,a_2,\dots,a_n\) --- the counts of the balls of each color.

You may assume that \(1\le n\le 2\cdot10^5\) and \(1\le a_i\le 10^6\) (and thus \(T=\sum a_i\le 10^6\)).

outputFormat

Output one integer: the number of valid arrangements modulo \(998{,}244{,}353\).

sample

2
1 2

0