题目背景

来源：2019 集训队作业 Round4

题目描述

若干个正整数排成一个序列，其中数字 $i$ 的出现次数为 $c_i$，对于每一个这样的序列，定义他的权值如下：

把这个序列首尾相接放在一个圆上，把这些数字分成若干相邻的段，使得每段都是在圆上相邻的数字，任意两段没有公共的元素，每一段中的数字都相同，相邻段中的数字不同，则这个序列的权值定义为所有段的长度之积。

求所有的序列的权值和对 $998244353$ 取模。

注：虽然计算序列的权值的时候是圆排列，但互为循环排列的不同序列仍然被认为是不同的，如 $(1,2,1,2)$ 和 $(2,1,2,1)$ 被认为是不同的序列。

输入格式

若干行，第一行一个正整数 $n$ ，表示数字种类数。

第二行 $n$ 个正整数 $c_i$，表示第 $i$ 个数字的出现次数。

输出格式

一行，表示所有出现次数符合条件的序列的权值和对 $998244353$ 取模的值。

2
2 2

18

6
7 8 9 10 11 12

515320459

提示

样例解释 #1：

合法序列为 $(1,1,2,2),(1,2,1,2),(1,2,2,1),(2,1,1,2),(2,1,2,1),(2,2,1,1)$。 权值分别为 $4,1,4,4,1,4$，和为 $18$。

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

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