You are given $n$ types of balls, with colors numbered from $1$ to $n$. There are $a_i$ balls of the $i$-th color. Little L wants to arrange these balls into a sequence such that there is no non-empty prefix or non-empty suffix that is "neat". A prefix or suffix is defined as "neat" if and only if the occurrences of all $n$ colors within it are equal. Your task is to calculate the number of distinct sequences.

Some necessary clarifications provided by the kind temporaryDO:

1. A prefix (or suffix) of length $len$ of a sequence refers to the $len$ balls at the leftmost (or rightmost) positions of the sequence. A non-empty prefix or suffix refers to a prefix or suffix where $len \neq 0$.
2. For a sequence of balls $S$, let $S_i$ denote the color of the $i$-th ball from the left. Two sequences $S$ and $T$ are considered distinct if and only if there exists a position $i$ such that $S_i \neq T_i$.

To avoid the need for arbitrary-precision arithmetic, you only need to output the result modulo $998244353$.

Input

The first line contains an integer $n$, representing the number of color types.

The next line contains $n$ space-separated integers, where the $i$-th positive integer $a_i$ represents the number of balls of the $i$-th color.

Output

Output a single integer representing the number of distinct sequences modulo $998244353$.

Examples

Input 1

3
1 1 2

Output 1

2

Note 1

The two valid arrangements are: 1 3 3 2 and 2 3 3 1. Clearly, there are no other sequences that satisfy the condition.

Input 2

5
5 6 7 8 9

Output 2

322192262

Subtasks

For $100\%$ of the data, it is guaranteed that $n \le 100$ and all $a_i \le 200,000$.

After submitting your code, the pretest data will be evaluated and the results returned. This problem's pretest data consists of 10 test cases, where the $i$-th test case satisfies the constraints of the $i$-th row in the table above.

Note: The evaluation results of the pretest data have no relation to the final evaluation results.